A363197 a(n) is the number of ways the labels 1 to 2^n-1 can be assigned to a perfect binary tree with n levels such that there is an ordering between children and parents and also an ordering between the left and the right child.

1, 1, 10, 343200, 73082837755699200000, 79548797573848497198355214730517854838277265162240000000000

Offset: 1

Author

Thomas Scheuerle, May 21 2023

Keywords

• nonn

Comments

We choose one order relation like left > right, parent < child and keep this relation the same while counting all variants which will fit this relation.

Number of permutations {1,2,...,2^n-1} which generate a binary search tree with minimum possible height such that each parent receives the left child first.

Examples

			The 10 variants for a(3) are:
    1          1          1
   / \        / \        / \
  5   2      4   2      4   2
 / \ / \    / \ / \    / \ / \
7  6 4  3  7  5 6  3  7  6 5  3
.
    1          1          1
   / \        / \        / \
  4   2      3   2      3   2
 / \ / \    / \ / \    / \ / \
6  5 7  3  5  4 7  6  7  4 6  5
.
    1          1          1
   / \        / \        / \
  3   2      3   2      3   2
 / \ / \    / \ / \    / \ / \
7  5 6  4  7  6 5  4  6  4 7  5
.
    1
   / \
  3   2
 / \ / \
6  5 7  4
.
		

Crossrefs

Cf. A056972, A076615.

Programs

Mathematica

RecurrenceTable[{a[n + 1] == Binomial[2^(n + 1) - 2, 2^n - 1]*2^((n^2 - 3*n)/2)*a[n]^2, a[1] == 1}, a, {n, 1, 6}] (* Amiram Eldar, May 21 2023 *)

PARI

a(n) = if(n==0,1,binomial(2^n-2, 2^(n-1)-1)*2^((4 - 5*n + n^2)/2)*a(n-1)^2)

Formula

a(n) = binomial(2^n - 2, 2^(n-1) - 1)*2^((4 - 5*n + n^2)/2)*a(n-1)^2.

a(n) = A076615(2^n - 1) / 2^(n*(n - 1)/2).