OFFSET
1,3
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.
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).
EXAMPLE
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
.
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 *)
PROG
(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)
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Scheuerle, May 21 2023
STATUS
approved