# Increasing permutation trees

For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left and right children there isn't a distinction between them and mirroring the tree or a sub-tree does not produce a new tree.

In this challenge you will be given an integer $$\n\$$ and you will be asked to determine the number of binary trees with each node labeled from $$\1\$$ to $$\2n+1\$$ such that no child node is less than its parent.

For example the following tree with 7 nodes is valid:

     1
2    7
3  4
5 6


but the following tree is not:

     1
2    7
6  4
5 3


Since 3 is a child of 4.

Given $$\n\$$ calculate the number of binary trees labeled from $$\1\$$ to $$\2n+1\$$ such that no child node is less than its parent.

This is so the goal is to minimize the size of your source code as measured in bytes.

# Test cases

I've calculated the first 11 solutions on my own:

1, 1, 4, 34, 496, 11056, 349504, 14873104, 819786496, 56814228736, 4835447317504


and the OEIS has more terms at: A002105

# Python NumPy, 72 bytes

lambda n:(mat(tril(cumsum(r_[1:n+3]),1),"O")**n)[0,0]
from numpy import*

Attempt This Online!

Same as below but as a function (no outer loop):

# Python NumPy, 85 bytes

from numpy import*
a=1,
for s,in r_:print((mat(tril(a,1),"O")**s).A1[0]);a+=a[s]+s+2,

Attempt This Online!

Uses the production matrix approach from the OEIS page. Preamble doctors print to cut short the infinite loop (otherwise ato swallows the output). Uses this trick to set up the infinite loop.

• Welcome to Code Golf, and nice first answer! Commented Jun 4, 2022 at 15:13

# Python 3.8 (pre-release), 85 80 bytes

def f(n,s=1,*a):
for _ in"__"*~-n:a=s,*[s:=s+x for x in a[::-1]]
print(s>>~-n)


Try it online! Link includes test cases. Explanation: Based on the relation A002105(n) = A000111(2n-1)/2ⁿ⁻¹, calculates A000111 using @dingledooper's approach to Count alternating permutations. Edit: Saved 5 bytes with help from @pexger.

• for _ in range(n+n-2) -> for _ in"_"*~-n*2 for 81 bytes: Try it online! Commented Jun 4, 2022 at 19:32
• @pxeger Even I know a golfier way of saying "_"*2...
– Neil
Commented Jun 4, 2022 at 21:45
• Heh, good point. Commented Jun 5, 2022 at 6:04

# SageMath, 44 42 36 bytes

lambda n:2*(-2)**n*polylog(1-2*n,-1)


Try it online!

Saved 2 8 bytes thanks to alephalpha!!!

Uses a port of the Mathematica code by Vladimir Reshetnikov on the OEIS A002105 page.

• -2 byte: lambda n:(-2)**n*(1-4**n)*bernoulli(2*n)/n Commented Jun 5, 2022 at 1:13
• Or shorter using the Mathematica code by Vladimir Reshetnikov on OEIS: lambda n:2*(-2)**n*polylog(1-2*n,-1). Commented Jun 5, 2022 at 1:16

# BQN, 23 bytesSBCS

Based on Peter Luschny's Sage function on OEIS.

1⊑(0∾2×+∘⌽⍟2)⍟⊑∘⥊÷2××˜


Run online!

# Charcoal, 31 bytes

Ｎθ⊞υ¹Ｆ⊖⊗θ≔⊞Ｏ⮌ＥυΣ…υ⊕λ⁰υＩ÷§υ⁰Ｘ²⊖θ


Try it online! Link is to verbose version of code. Explanation: Combining two formulas on A110501 gives A002105 in terms of A000111, which we did a couple of days ago: A002105(n) = A000111(2n-1)/2ⁿ⁻¹.

Ｎθ


Input n.

⊞υ¹Ｆ⊖⊗θ≔⊞Ｏ⮌ＥυΣ…υ⊕λ⁰υ


Calculate A000111(2n-1). See my answer to Count alternating permutations.

Ｉ÷§υ⁰Ｘ²⊖θ


Divide by 2ⁿ⁻¹.

# Wolfram Language (Mathematica), 21 bytes

EulerE[2#-1,0](-2)^#&


Try it online!

This is basically the Mathematica code by Vladimir Reshetnikov on OEIS, but golfed down.

# PARI/GP, 27 bytes

n->(-2)^n*eulerpol(2*n-1)%x

Attempt This Online!

Based on the Mathematica code by Vladimir Reshetnikov on OEIS.

# Python, 125 bytes

C=lambda n,k:n==k or C(n-1,k)*n//(n-k)
def f(n):
s=i=0
while(i<n)*n:j=n-i-1;s+=f(i)*f(j)*C(2*n,2*i+1);i+=1
return s//2or 1

Attempt This Online!

# Python 2, 99 bytes

D=[1]
i=0
while 1:exec"D[::-1]=D\nfor k in range(i):D[k+1]+=D[k]\n"*2;D+=0,;print(D[i]<<i)/-~i;i+=1

Attempt This Online!

-14 bytes thanks to @ovs

Based on Peter Luschny's program on the OEIS page.

Full program which prints the sequence infinitely.

exec"..."*2 performs two cumulative sums on D, first backwards, then forwards.

A backwards cumulative sum is equivalent to:

D.reverse()
D.normal_cumulative_sum()
D.unreverse()


Since "unreverse" is the same as reverse, the overall sequence of operations becomes:

D.reverse()
D.normal_cumulative_sum()
D.reverse()
D.normal_cumulative_sum()


and this can be extracted into a snippet of code which we just call twice.

D[::-1]=D is a horrible way of reversing D in-place, which is two bytes shorter than D.reverse(). Unlike the more obvious D=D[::-1], it doesn't reassign D (it mutates it in-place), which means it can be done in a function without having to use the global keyword.

• exec saves a couple bytes over defining a function, and you can actually start with D=[1] with some rearrangements. And range(i) saves a bit over R
– ovs
Commented Jun 4, 2022 at 15:32
• @ovs I'm not sure if this is exactly what you meant? Commented Jun 4, 2022 at 16:13
• This is close, I had 99 bytes
– ovs
Commented Jun 4, 2022 at 17:55

# JavaScript (Node.js), 51 bytes

f=(n,s=0,l=1)=>n?s*f(n-=.5,s-1,l+1)+l*f(n,s+1,l):!s


Try it online!

This program output true for n=0. 1 more byte is required to convert it into 1.

f=(
n,    // nodes: 2*n is number of nodes remaining
s=0,  // slots: how many nodes with 1 child currently
l=1   // leaves: how many leaf nodes currently
)=>
n? // is all nodes placed on the tree?
s*f(n-=.5,s-1,l+1)+ // chose a non-leaf node, place it as an child
l*f(n,s+1,l):       // chose a leaf node, place it as an child
!s // make sure all non-leaf nodes have 2 children


# Python, 58 56 bytes

-2 jezza_99

lambda n:2*(-2)**n*polylog(1-2*n,-1)
from mpmath import*


Attempt This Online!

Ported from code by Vladimir Reshetnikov from the OEIS page (A002105)

• The f= can be excluded for -2 bytes Commented Jun 6, 2022 at 22:33

# R, 55 51 bytes

\(n){for(i in 2:(2*n))T=rev(diffinv(T));T[1]/2^n*2}

Attempt This Online!

Uses the A002105(n) = A000111(2n-1)/2ⁿ⁻¹ trick found by @Neil, and my answer to Count alternating permutations (calculating A000111).

# JavaScript (ES6),  66  65 bytes

Returns the $$\n\$$-th term, 0-indexed.

Uses @Neil's method.

n=>(g=a=>i<2*n?g([s,...a.map(_=>s+=a[--j],j=i++)]):s>>n)([i=s=1])


Try it online!

# Factor + math.extras, 54 51 bytes

[| n | n 2^ 4 n ^ 1 - * n 2 * bernoulli abs * n / ]
`

Try it online!

Uses the following formula from the title of OEIS A002105:

$$\large\frac{2^n\times(2^{2n}-1)\times|\text{bernoulli}(2n)|}{n}$$

-3 bytes from peeking at @Noodle9's SageMath answer which combines $$\2^{2n}\$$ into $$\4^n\$$.