Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #27 Jul 08 2023 16:46:28
%S 1,1,10,343200,73082837755699200000,
%T 79548797573848497198355214730517854838277265162240000000000
%N 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.
%C 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.
%C 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.
%F a(n) = binomial(2^n - 2, 2^(n-1) - 1)*2^((4 - 5*n + n^2)/2)*a(n-1)^2.
%F a(n) = A076615(2^n - 1) / 2^(n*(n - 1)/2).
%e The 10 variants for a(3) are:
%e 1 1 1
%e / \ / \ / \
%e 5 2 4 2 4 2
%e / \ / \ / \ / \ / \ / \
%e 7 6 4 3 7 5 6 3 7 6 5 3
%e .
%e 1 1 1
%e / \ / \ / \
%e 4 2 3 2 3 2
%e / \ / \ / \ / \ / \ / \
%e 6 5 7 3 5 4 7 6 7 4 6 5
%e .
%e 1 1 1
%e / \ / \ / \
%e 3 2 3 2 3 2
%e / \ / \ / \ / \ / \ / \
%e 7 5 6 4 7 6 5 4 6 4 7 5
%e .
%e 1
%e / \
%e 3 2
%e / \ / \
%e 6 5 7 4
%e .
%t 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 *)
%o (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)
%Y Cf. A056972, A076615.
%K nonn
%O 1,3
%A _Thomas Scheuerle_, May 21 2023