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.

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

Author

John V Siratt, Jul 21 2024

Keywords

• nonn
• tabl

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^(

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).

Examples

			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
		

Links

• John V. Siratt, Some applications of formal mathematics, Doctoral dissertation, University of Notre Dame (2024).

Crossrefs

Column 1 is A000225.

Column 2 appears to be A006095.

Programs

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

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.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.