A385123 Triangle Read by rows: T(n,k) is the number of rooted ordered trees with n non-root nodes with non-root node labels in {1,..,k} such that all labels appear at least once in all groups of sibling nodes.

1, 0, 1, 0, 2, 2, 0, 5, 6, 6, 0, 14, 22, 36, 24, 0, 42, 90, 150, 240, 120, 0, 132, 378, 648, 1560, 1800, 720, 0, 429, 1638, 3318, 8400, 16800, 15120, 5040, 0, 1430, 7278, 18180, 43128, 126000, 191520, 141120, 40320, 0, 4862, 32946, 98502, 238320, 834120, 1905120, 2328480, 1451520, 362880

Offset

0,5

Links

Table of n, a(n) for n=0..54.

Example

Triangle begins:
    k=0    1    2      3     4      5      6     7
 n=0 [1]
 n=1 [0,   1]
 n=2 [0,   2,   2]
 n=3 [0,   5,   6,     6]
 n=4 [0,  14,  22,    36,   24]
 n=5 [0,  42,  90,   150,  240,   120]
 n=6 [0, 132,  378,  648, 1560,  1800,   720]
 n=7 [0, 429, 1638, 3318, 8400, 16800, 15120, 5040]
...
T(3,2) = 6 counts the three leaf permutations of each of the following trees:
      __o__        __o__
     /  |  \      /  |  \
   (1) (1) (2)  (1) (2) (2)

Prog

(PARI)
subsets(S) = {my(s=List()); for(i=0, 2^(#S) -1, my(x=List()); for(j=1, #S, if(bitand(i, 1<<(j-1)), listput(x, S[j]))); listput(s, Vec(x))); Vec(s)}
C_aB(B) = {my(S = subsets(B)); sum(i=1, #S, (1/(1-x*z*#S[i]))*(-1)^(#B-#S[i]))}
D(k, N, B) = {if(k>N, 1, substpol(C_aB(B), z, 1 + D(k+1, N-#B+1, B)))}
Dx(N, B) = {Vec(1+D(1, N, B)+ O('x^(N+1)))}
T(max_row) = {my( N = max_row+1, v = vector(N, i, if(i==1, 1, 0))~); for(k=1, N, v=matconcat([v, Dx(N+1, vector(k, i, i))~])); vector(N, n, vector(n, k, v[n, k]))}
T(8)

Crossrefs

Cf. A000108 (column k=1), A000142 (main diagonal), A385125 (row sums).

Cf. A107429, A384685, A384747.

Sequence in context: A329687 A356035 A395009 * A396342 A321127 A222128

Adjacent sequences: A385120 A385121 A385122 * A385124 A385125 A385126

Keyword

nonn,tabl

Author

John Tyler Rascoe, Jun 18 2025

Status

approved