John V Siratt - cp's OEIS frontend

User: John V Siratt

John V Siratt has authored 1 sequences.

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

John V Siratt, Jul 21 2024

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

			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

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

Column 1 is A000225.

Column 2 appears to be A006095.

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

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.

cp's OEIS Frontend

User: John V Siratt

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula