A360985 Triangle read by rows: T(n,k) is the number of full binary trees with n leaves, each internal node having the heights of its two subtrees weakly increasing left to right, and with k internal nodes having two subtrees of equal height.
1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 4, 3, 2, 2, 0, 0, 1, 6, 7, 6, 3, 0, 1, 0, 1, 9, 13, 14, 9, 3, 1, 0, 0, 1, 12, 27, 27, 22, 14, 3, 1, 0, 0, 1, 16, 47, 59, 54, 32, 16, 7, 0, 0, 0, 1, 20, 81, 117, 125, 91, 44, 20, 8, 1, 0
Offset: 1
Examples
The table for T(n,k) begins: n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 0 1 3 0 1 0 4 0 1 0 1 5 0 1 1 1 0 6 0 1 2 2 1 0 7 0 1 4 3 2 2 0 8 0 1 6 7 6 3 0 1 9 0 1 9 13 14 9 3 1 0 10 0 1 12 27 27 22 14 3 1 0 11 0 1 16 47 59 54 32 16 7 0 0 12 0 1 20 81 117 125 91 44 20 8 1 0 13 0 1 25 128 233 272 228 143 61 23 8 2 0 14 0 1 30 197 439 573 555 389 206 90 21 10 2 0 15 0 1 36 287 801 1178 1275 1014 621 303 109 32 4 4 0 16 0 1 42 410 1383 2367 2841 2522 1727 962 421 138 36 7 0 1
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50).
Programs
-
PARI
T(n)={my(p=x+O(x*x^n), q=p); for(n=2, n, p=y*p^2 + p*(q-p); q+=p); my(v=Vec(q)); vector(#v, n, Vecrev(v[n], n))} { my(A=T(12)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Mar 24 2023
Formula
T(n,2) = A002620(n-3) for all n>=3.
T(n,n-1) = 1 if n is a power of 2, and T(n,n) = 0 otherwise.
T(n,n-2) != 0 if and only if n-1 has exactly one maximal group of consecutive zeros in its binary representation, and in this case T(n,n-2) = 2^(a-1) where a is the number of 1s at the beginning of the binary representation of n-1.
Sum_{k=0..n-1} T(n,k)*2^(n-k-1) = A000108(n-1).