cp's OEIS Frontend

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.

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