Increasing permutation trees

Question 1

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 \2ドルn+1\$ such that no child node is less than its parent.

For example the following tree with 7 nodes is valid:

but the following tree is not:

Since 3 is a child of 4.

Task

Given \$n\$ calculate the number of binary trees labeled from \1ドル\$ to \2ドルn+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

Question 2

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.

Question 3

Welcome to Code Golf, and nice first answer!

Question 4

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)/2n−1, calculates A000111 using @dingledooper's approach to Count alternating permutations. Edit: Saved 5 bytes with help from @pexger.

Question 5

for _ in range(n+n-2) -> for _ in"_"*~-n*2 for 81 bytes: Try it online!

Question 6

@pxeger Even I know a golfier way of saying "_"*2...

Question 7

Heh, good point.

Question 8

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.

Question 9

-2 byte: lambda n:(-2)**n*(1-4**n)*bernoulli(2*n)/n

Question 10

Or shorter using the Mathematica code by Vladimir Reshetnikov on OEIS: lambda n:2*(-2)**n*polylog(1-2*n,-1).

Question 11

BQN, 23 bytes^SBCS

Based on Peter Luschny's Sage function on OEIS.

1⊑(×ばつ+`∘⌽⍟2)×ばつ ̃

Run online!

Question 12

Charcoal, 31 bytes

Nθ⊞υ1F⊖⊗θ≔⊞O⮌EυΣ...υ⊕λ0υI÷§υ0X2⊖θ

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)/2n−1.

Nθ

Input n.

⊞υ1F⊖⊗θ≔⊞O⮌EυΣ...υ⊕λ0υ

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

I÷§υ0X2⊖θ

Divide by 2n−1.

Question 13

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.

Question 14

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.

Question 15

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!

Question 16

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.

Question 17

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

Question 18

@ovs I'm not sure if this is exactly what you meant?

Question 19

This is close, I had 99 bytes

Question 20

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

Question 21

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)

Question 22

The f= can be excluded for -2 bytes

Question 23

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)/2n−1 trick found by @Neil, and my answer to Count alternating permutations (calculating A000111).

Question 24

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!

Question 25

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

Albert.Lang 6,0347 silver badges29 bronze badges · Answer 1 · 2022-06-04 15:11:17Z

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.

2

\$\begingroup\$ Welcome to Code Golf, and nice first answer! \$\endgroup\$

pxeger
– pxeger

2022年06月04日 15:13:47 +00:00
Commented Jun 4, 2022 at 15:13

Neil 184k12 gold badges76 silver badges290 bronze badges · Answer 2 · 2022-06-04 16:32:03Z

6

\$\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)/2n−1, calculates A000111 using @dingledooper's approach to Count alternating permutations. Edit: Saved 5 bytes with help from @pexger.

Share

Improve this answer

edited Jun 4, 2022 at 21:45

answered Jun 4, 2022 at 16:32

Neil's user avatar

Neil

184k12 gold badges76 silver badges290 bronze badges

\$\endgroup\$

3

\$\begingroup\$ for _ in range(n+n-2) -> for _ in"_"*~-n*2 for 81 bytes: Try it online! \$\endgroup\$

pxeger
– pxeger

2022年06月04日 19:32:30 +00:00
Commented Jun 4, 2022 at 19:32
3

\$\begingroup\$ @pxeger Even I know a golfier way of saying "_"*2... \$\endgroup\$

Neil
– Neil

2022年06月04日 21:45:35 +00:00
Commented Jun 4, 2022 at 21:45
\$\begingroup\$ Heh, good point. \$\endgroup\$

pxeger
– pxeger

2022年06月05日 06:04:42 +00:00
Commented Jun 5, 2022 at 6:04

Add a comment |

Noodle9 20.4k3 gold badges23 silver badges47 bronze badges · Answer 3 · 2022-06-04 18:16:04Z

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.

Share

Improve this answer

edited Jun 5, 2022 at 10:11

answered Jun 4, 2022 at 18:16

Noodle9's user avatar

Noodle9

20.4k3 gold badges23 silver badges47 bronze badges

\$\endgroup\$

2

\$\begingroup\$ -2 byte: lambda n:(-2)**n*(1-4**n)*bernoulli(2*n)/n \$\endgroup\$

alephalpha
– alephalpha

2022年06月05日 01:13:06 +00:00
Commented Jun 5, 2022 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
– alephalpha

2022年06月05日 01:16:12 +00:00
Commented Jun 5, 2022 at 1:16

Add a comment |

ovs 61.2k3 gold badges49 silver badges164 bronze badges · Answer 4 · 2022-06-04 15:13:35Z

3

\$\begingroup\$

BQN, 23 bytes^SBCS

Based on Peter Luschny's Sage function on OEIS.

1⊑(×ばつ+`∘⌽⍟2)×ばつ ̃

Run online!

Share

Improve this answer

answered Jun 4, 2022 at 15:13

ovs's user avatar

ovs

61.2k3 gold badges49 silver badges164 bronze badges

\$\endgroup\$

Add a comment |

Neil 184k12 gold badges76 silver badges290 bronze badges · Answer 5 · 2022-06-04 16:16:31Z

Charcoal, 31 bytes

Nθ⊞υ1F⊖⊗θ≔⊞O⮌EυΣ...υ⊕λ0υI÷§υ0X2⊖θ

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)/2n−1.

Nθ

Input n.

⊞υ1F⊖⊗θ≔⊞O⮌EυΣ...υ⊕λ0υ

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

I÷§υ0X2⊖θ

Divide by 2n−1.

naffetS 13.1k2 gold badges22 silver badges54 bronze badges · Answer 6 · 2022-06-04 18:28:04Z

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.

Share

Improve this answer

edited Jun 4, 2022 at 18:55

answered Jun 4, 2022 at 18:28

naffetS's user avatar

naffetS

13.1k2 gold badges22 silver badges54 bronze badges

\$\endgroup\$

Add a comment |

alephalpha 51.9k7 gold badges75 silver badges196 bronze badges · Answer 7 · 2022-06-04 14:54:31Z

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.

Share

Improve this answer

answered Jun 4, 2022 at 14:54

alephalpha's user avatar

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

\$\endgroup\$

Add a comment |

matteo_c 7,20616 silver badges28 bronze badges · Answer 8 · 2022-06-04 15:03:18Z

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!

pxeger 25.3k4 gold badges59 silver badges146 bronze badges · Answer 9 · 2022-06-04 14:39:46Z

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

tsh 36.2k2 gold badges36 silver badges133 bronze badges · Answer 10 · 2022-06-06 03:36:44Z

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

Alice F 4455 silver badges10 bronze badges · Answer 11 · 2022-06-05 14:07:16Z

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)

Share

Improve this answer

edited Jun 9, 2022 at 7:02

answered Jun 5, 2022 at 14:07

Alice F's user avatar

Alice F

4455 silver badges10 bronze badges

\$\endgroup\$

1

1

\$\begingroup\$ The f= can be excluded for -2 bytes \$\endgroup\$

jezza_99
– jezza_99

2022年06月06日 22:33:57 +00:00
Commented Jun 6, 2022 at 22:33

Add a comment |

pajonk 19.4k5 gold badges29 silver badges78 bronze badges · Answer 12 · 2022-06-04 19:53:45Z

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)/2n−1 trick found by @Neil, and my answer to Count alternating permutations (calculating A000111).

Arnauld 206k21 gold badges187 silver badges670 bronze badges · Answer 13 · 2022-06-04 20:02:06Z

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!

chunes 27.8k3 gold badges32 silver badges55 bronze badges · Answer 14 · 2022-06-04 18:16:55Z

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

Stack Exchange Network

Increasing permutation trees

Task

Test cases

14 Answers 14

Python NumPy, 72 bytes

Python NumPy, 85 bytes

Python 3.8 (pre-release), (削除) 85 (削除ここまで) 80 bytes

SageMath, ^{(削除) 44 (削除ここまで) (削除) 42 (削除ここまで)} 36 bytes

BQN, 23 bytes^SBCS

Charcoal, 31 bytes

Wolfram Language (Mathematica), 21 bytes

PARI/GP, 27 bytes

Python, 125 bytes

Python 2, 99 bytes

JavaScript (Node.js), 51 bytes

Python, (削除) 58 (削除ここまで) 56 bytes

R, (削除) 55 (削除ここまで) 51 bytes

JavaScript (ES6), (削除) 66 (削除ここまで) 65 bytes

Factor + `math.extras`, (削除) 54 (削除ここまで) 51 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Hot Network Questions

Increasing permutation trees

Task

Test cases

14 Answers 14

Python NumPy, 72 bytes

Python NumPy, 85 bytes

Python 3.8 (pre-release), (削除) 85 (削除ここまで) 80 bytes

SageMath, (削除) 44 (削除ここまで) (削除) 42 (削除ここまで) 36 bytes

BQN, 23 bytesSBCS

Charcoal, 31 bytes

Wolfram Language (Mathematica), 21 bytes

PARI/GP, 27 bytes

Python, 125 bytes

Python 2, 99 bytes

JavaScript (Node.js), 51 bytes

Python, (削除) 58 (削除ここまで) 56 bytes

R, (削除) 55 (削除ここまで) 51 bytes

JavaScript (ES6), (削除) 66 (削除ここまで) 65 bytes

Factor + math.extras, (削除) 54 (削除ここまで) 51 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Linked

Related

Hot Network Questions

SageMath, ^{(削除) 44 (削除ここまで) (削除) 42 (削除ここまで)} 36 bytes

BQN, 23 bytes^SBCS

Factor + `math.extras`, (削除) 54 (削除ここまで) 51 bytes