|
|
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
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,18
|
|
LINKS
|
|
|
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).
|
|
EXAMPLE
|
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
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|