12
\$\begingroup\$

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

\$\endgroup\$

14 Answers 14

6
\$\begingroup\$

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.

\$\endgroup\$
1
5
\$\begingroup\$

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.

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ -2 byte: lambda n:(-2)**n*(1-4**n)*bernoulli(2*n)/n \$\endgroup\$
    – alephalpha
    Jun 5 at 1:13
  • \$\begingroup\$ Or shorter using the Mathematica code by Vladimir Reshetnikov on OEIS: lambda n:2*(-2)**n*polylog(1-2*n,-1). \$\endgroup\$
    – alephalpha
    Jun 5 at 1:16
3
\$\begingroup\$

BQN, 23 bytesSBCS

Based on Peter Luschny's Sage function on OEIS.

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

Run online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 31 bytes

Nθ⊞υ¹F⊖⊗θ≔⊞O⮌EυΣ…υ⊕λ⁰υI÷§υ⁰X²⊖θ

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

Nθ

Input n.

⊞υ¹F⊖⊗θ≔⊞O⮌EυΣ…υ⊕λ⁰υ

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

I÷§υ⁰X²⊖θ

Divide by 2ⁿ⁻¹.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Jun 4 at 15:32
  • \$\begingroup\$ @ovs I'm not sure if this is exactly what you meant? \$\endgroup\$
    – pxeger
    Jun 4 at 16:13
  • \$\begingroup\$ This is close, I had 99 bytes \$\endgroup\$
    – ovs
    Jun 4 at 17:55
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The f= can be excluded for -2 bytes \$\endgroup\$
    – jezza_99
    Jun 6 at 22:33
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.