login
Array read by antidiagonals: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves of k colors.
6

%I #20 Apr 20 2023 14:56:30

%S 1,1,0,1,1,0,1,2,1,0,1,3,3,1,0,1,4,6,4,2,0,1,5,10,10,11,3,0,1,6,15,20,

%T 36,30,7,0,1,7,21,35,90,144,105,13,0,1,8,28,56,190,476,706,380,32,0,1,

%U 9,36,84,357,1251,3034,3774,1555,73,0,1,10,45,120,616,2814,9845,21380,22140,6650,190,0

%N Array read by antidiagonals: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves of k colors.

%C Homeomorphically irreducible trees are trees without vertices of degree 2. All non-leaf nodes then have degree >= 3.

%C Not all colors need to be used.

%C The Johnson reference has a mistake in formula 4.3. In particular, the final term should be subtracted rather than added. Compare with the first formula given here. The table of results given in the reference is consequently also incorrect.

%H Andrew Howroyd, <a href="/A339779/b339779.txt">Table of n, a(n) for n = 0..1325</a>

%H Virginia Perkins Johnson, <a href="https://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, Ph. D. Dissertation, Univ. South Carolina, 2012. [Table 4.3 is an incorrect version of this table].

%F T(n,k) = k*g(n-1,k) + g(n,k) - Sum_{j=1..n-1} g(j,k)*g(n-j,k) for n > 1 where g(n,k) is A319254(n,k).

%F G.f. of k-th column: 1 + k*x*r(x) + r(x) - r(x)^2 where r(x) is the g.f. of the k-th column of A319254.

%e Array begins:

%e ============================================================

%e n\k| 0 1 2 3 4 5 6 7

%e ---+--------------------------------------------------------

%e 0 | 1 1 1 1 1 1 1 1 ...

%e 1 | 0 1 2 3 4 5 6 7 ...

%e 2 | 0 1 3 6 10 15 21 28 ...

%e 3 | 0 1 4 10 20 35 56 84 ...

%e 4 | 0 2 11 36 90 190 357 616 ...

%e 5 | 0 3 30 144 476 1251 2814 5656 ...

%e 6 | 0 7 105 706 3034 9845 26383 61572 ...

%e 7 | 0 13 380 3774 21380 85995 274800 744556 ...

%e 8 | 0 32 1555 22140 163670 812160 3086481 9692480 ...

%e 9 | 0 73 6650 137096 1322960 8092945 36550458 132954360 ...

%e ...

%o (PARI) \\ here R(n,k) is k-th column of A319254.

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

%o R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}

%o U(n, k)={my(g=x*Ser(R(n,k))); Vec(1 + g + k*x*g - g^2)}

%o {my(T=Mat(vector(9, k, U(8, k-1)~))); for(n=1, #T~, print(T[n, ]))}

%Y Columns k=1..4 are A007827, A339782, A339783, A339784.

%Y Cf. A319254 (planted), A339649 (degree <= 3), A339780.

%K nonn,tabl

%O 0,8

%A _Andrew Howroyd_, Dec 16 2020