Increasing permutation trees

Question

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.

Task

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 code-golf 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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

BQN, 23 bytes^SBCS

Based on Peter Luschny's Sage function on OEIS.

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

Run online!

Answer 5

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ⁿ⁻¹.

Answer 6

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.

Answer 7

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.

Answer 8

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!

Answer 9

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.

Answer 10

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

Answer 11

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)

Answer 12

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).

Answer 13

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!

Answer 14

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\$.