A339649 -id:A339649 - cp's OEIS frontend

A339650 Triangle read by rows: T(n,k) is the number of trees with n leaves of exactly k colors and all non-leaf nodes having degree 3.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 6, 3, 0, 1, 10, 30, 36, 15, 0, 2, 27, 140, 310, 300, 105, 0, 2, 74, 663, 2376, 3990, 3150, 945, 0, 4, 226, 3186, 17304, 44850, 59805, 39690, 10395, 0, 6, 710, 15642, 123508, 462735, 925890, 1018710, 582120, 135135

Offset: 0

Andrew Howroyd, Dec 14 2020

See table 4.2 in the Johnson reference.

			Triangle begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,    1;
  0, 1,   4,    6,     3;
  0, 1,  10,   30,    36,    15;
  0, 2,  27,  140,   310,   300,   105;
  0, 2,  74,  663,  2376,  3990,  3150,   945;
  0, 4, 226, 3186, 17304, 44850, 59805, 39690, 10395;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.

Columns k=1..4 are A129860, A220829, A220830, A220831.
Main diagonal is A001147(n-2) for n >= 2.
Row sums are A339651.
Cf. A319541 (rooted), A339649, A339780.

\\ here U(n,k) is column k of A339649 as a vector.
R(n, k)={my(v=vector(n)); v[1]=k; for(n=2, n, v[n]=sum(j=1, (n-1)\2, v[j]*v[n-j]) + if(n%2, 0, binomial(v[n/2]+1, 2))); v}
U(n, k)={my(g=x*Ser(R(n, k))); Vec(1 + g + (subst(g + O(x*x^(n\3)), x, x^3) - g^3)/3)}
M(n, m=n)={my(v=vector(m+1, k, U(n, k-1)~)); Mat(vector(m+1, k, k--; sum(i=0, k, (-1)^(k-i)*binomial(k, i)*v[1+i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

T(n,k) = Sum_{i=0..k} (-1)^(k-i)*binomial(k,i)*A339649(n,i).

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

Original entry on oeis.org

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, 36, 30, 7, 0, 1, 7, 21, 35, 90, 144, 105, 13, 0, 1, 8, 28, 56, 190, 476, 706, 380, 32, 0, 1, 9, 36, 84, 357, 1251, 3034, 3774, 1555, 73, 0, 1, 10, 45, 120, 616, 2814, 9845, 21380, 22140, 6650, 190, 0

Offset: 0

Andrew Howroyd, Dec 16 2020

Homeomorphically irreducible trees are trees without vertices of degree 2. All non-leaf nodes then have degree >= 3.
Not all colors need to be used.
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.

			Array begins:
============================================================
n\k| 0  1    2      3       4       5        6         7
---+--------------------------------------------------------
0  | 1  1    1      1       1       1        1         1 ...
1  | 0  1    2      3       4       5        6         7 ...
2  | 0  1    3      6      10      15       21        28 ...
3  | 0  1    4     10      20      35       56        84 ...
4  | 0  2   11     36      90     190      357       616 ...
5  | 0  3   30    144     476    1251     2814      5656 ...
6  | 0  7  105    706    3034    9845    26383     61572 ...
7  | 0 13  380   3774   21380   85995   274800    744556 ...
8  | 0 32 1555  22140  163670  812160  3086481   9692480 ...
9  | 0 73 6650 137096 1322960 8092945 36550458 132954360 ...
     ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012. [Table 4.3 is an incorrect version of this table].

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

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

\\ here R(n,k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
U(n, k)={my(g=x*Ser(R(n,k))); Vec(1 + g + k*x*g - g^2)}
{my(T=Mat(vector(9, k, U(8, k-1)~))); for(n=1, #T~, print(T[n, ]))}

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

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.

A220826 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [2].

Original entry on oeis.org

2, 3, 4, 6, 12, 31, 78, 234, 722, 2376, 8046, 28263, 101226, 370389, 1375728, 5182107, 19743204, 75994993, 295110996, 1155128397, 4553360558, 18063221619, 72069527418, 289053637621, 1164871141254, 4714973350560, 19161577759814, 78162897838290, 319940064689142

Offset: 1

N. J. A. Sloane, Dec 22 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

Column 2 of A339649.

Cf. A083563, A220829.

U(30,2) \\ See A339649 for U(n,k). - Andrew Howroyd, Dec 14 2020

Terms a(11) and beyond from Andrew Howroyd, Dec 14 2020

A220827 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [3].

Original entry on oeis.org

3, 6, 10, 21, 63, 227, 891, 3876, 17790, 85536, 424926, 2169376, 11312838, 60065901, 323746095, 1767667332, 9760149468, 54422364834, 306101712771, 1735044593418, 9902940693084, 56876247586827, 328516343529525, 1907316302027081, 11125942281844011, 65182572852807465

Offset: 1

N. J. A. Sloane, Dec 22 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

Column 3 of A339649.

Terms a(11) and beyond from Andrew Howroyd, Dec 14 2020

A220828 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [4].

Original entry on oeis.org

4, 10, 20, 55, 220, 1040, 5480, 31420, 190360, 1202930, 7848720, 52543935, 359182620, 2498614620, 17640615900, 126142316865, 912047139460, 6658803466730, 49035674140240, 363881247076930, 2718918248334300, 20442286928323170, 154564065790535680, 1174669811887063830

Offset: 1

N. J. A. Sloane, Dec 22 2012

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

Column 4 of A339649.

Terms a(11) and beyond from Andrew Howroyd, Dec 14 2020

cp's OEIS Frontend

A339650 Triangle read by rows: T(n,k) is the number of trees with n leaves of exactly k colors and all non-leaf nodes having degree 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A220826 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [2].

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A220827 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [3].

Views

Author

Keywords

Links

Crossrefs

Extensions

A220828 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [4].

Views

Author

Keywords

Links

Crossrefs

Extensions