login
A374839
Triangle read by rows: T(n,k) is the number of strong subtrees of height k in the complete binary tree of height n.
0
1, 3, 1, 7, 7, 1, 15, 35, 23, 1, 31, 155, 403, 279, 1, 63, 651, 6603, 71827, 65815, 1, 127, 2667, 106299, 18394315, 4313323667, 4295033111, 1, 255, 10795, 1703451, 4709050939, 282677998234827, 18447026751295461523, 18446744078004584727, 1
OFFSET
1,2
COMMENTS
Informally, a strong subtree is one that preserves meets, the relative level of vertices, and the number of immediate successors to non-terminal vertices.
The collection of strong subtrees with height k of some tree T is often denoted by S_k(T). T(n,k) is the cardinality of S_k(2^(<n)).
There is a general expression for T(n,k) given in terms of an auxiliary function that can be eliminated for the diagonals, with the following examples:
T(m+1,m) = 3 + Sum_{j=1..m-1} 2^(2^i).
T(m+2,m) = 7 + 3*(Sum_{j=1..m-1} 2^(2^i)) + Sum_{1<=i,j<=m-1} 2^(2^i + 2^j).
T(m+3,m) = 15 + 7*(Sum_{j=1..m-1} 2^(2^i)) + 3*(Sum_{1<=i,j<=m-1} 2^(2^i + 2^j)) + Sum_{1<=i,j,k<=m-1} 2^(2^i + 2^j + 2^k).
LINKS
John V. Siratt, Some applications of formal mathematics, Doctoral dissertation, University of Notre Dame (2024).
FORMULA
T(n,k) = Sum_{1 <= x_1 < ... < x_k <= n} Product_{i=1..k} (2^(x_i - x_{i-1} - 1))^(2^(i - 1)), where x_0 = 0.
EXAMPLE
Triangle begins:
1;
3, 1;
7, 7, 1;
15, 35, 23, 1;
31, 155, 403, 279, 1;
63, 651, 6603, 71827, 65815, 1;
127, 2667, 106299, 18394315, 4313323667, 4295033111, 1;
...
Formatted as a transposed array:
T(n,k) | n=1 2 3 4 5 6 7 8
--------------------------------------------------------------------
k=1 | 1 3 7 15 31 63 127 255
2 | 0 1 7 35 155 651 2667 10795
3 | 0 0 1 23 403 6603 106299 1703451
4 | 0 0 0 1 279 71827 18394315 4709050939
5 | 0 0 0 0 1 65815 4313323667 282677998234827
6 | 0 0 0 0 0 1 4295033111 18447026751295461523
7 | 0 0 0 0 0 0 1 18446744078004584727
8 | 0 0 0 0 0 0 0 1
PROG
(PARI) T(n, k)={my(s=0); forvec(x=vector(k, i, [1, n]), s+=prod(i=1, k, (2^(x[i] - if(i>1, x[i-1]) - 1))^(2^(i - 1))), 2); s}
{ for(n=1, 8, print(vector(n, k, T(n, k)))) } \\ Andrew Howroyd, Jul 23 2024
CROSSREFS
Column 1 is A000225.
Column 2 appears to be A006095.
Sequence in context: A132307 A372968 A188463 * A369892 A359576 A319298
KEYWORD
nonn,tabl
AUTHOR
John V Siratt, Jul 21 2024
STATUS
approved