A339650 -id:A339650 - cp's OEIS frontend

A339780 Triangle read by rows: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves using exactly k colors.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 2, 7, 9, 4, 0, 3, 24, 63, 68, 26, 0, 7, 91, 412, 812, 720, 236, 0, 13, 354, 2673, 8512, 13100, 9672, 2752, 0, 32, 1491, 17571, 84312, 199820, 248904, 156492, 39208, 0, 73, 6504, 117365, 814184, 2782970, 5194580, 5408620, 2953792, 660032

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.

			Triangle begins:
  1;
  0,  1;
  0,  1,    1;
  0,  1,    2,     1;
  0,  2,    7,     9,     4;
  0,  3,   24,    63,    68,     26;
  0,  7,   91,   412,   812,    720,    236;
  0, 13,  354,  2673,  8512,  13100,   9672,   2752;
  0, 32, 1491, 17571, 84312, 199820, 248904, 156492, 39208;
  ...

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 A007827(n>0), A339785, A339786, A339787.
Main diagonal is A000311(n>0).
Row sums are A339781.
Cf. A319376 (planted), A339650 (degree <= 3), A339779.

\\ here U(n,k) is A339779 as vector.
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)}
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(8)); for(n=1, #T~, print(T[n,1..n])); }

A339649 Array read by antidiagonals: T(n,k) is the number of leaf colored trees with n leaves of k colors and all non-leaf nodes having degree 3.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 4, 1, 0, 1, 5, 10, 10, 6, 1, 0, 1, 6, 15, 20, 21, 12, 2, 0, 1, 7, 21, 35, 55, 63, 31, 2, 0, 1, 8, 28, 56, 120, 220, 227, 78, 4, 0, 1, 9, 36, 84, 231, 600, 1040, 891, 234, 6, 0, 1, 10, 45, 120, 406, 1386, 3530, 5480, 3876, 722, 11, 0

Offset: 0

Andrew Howroyd, Dec 14 2020

Not all k colors need to be used. The total number of nodes will be 2n-1.

See table 4.1 in the Johnson reference.

			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 1   6    21     55     120     231      406 ...
5  | 0 1  12    63    220     600    1386     2842 ...
6  | 0 2  31   227   1040    3530    9772    23366 ...
7  | 0 2  78   891   5480   23250   77112   214718 ...
8  | 0 4 234  3876  31420  165510  655599  2122099 ...
9  | 0 6 722 17790 190360 1243825 5878446 22102577 ...
     ...

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.

Columns k=1..4 are A129860, A220826, A220827, A220828.

Cf. A319539 (rooted), A339650, A339779.

\\ here U(n,k) gives column k 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)}
{my(T=Mat(vector(8, k, U(8, k-1)~))); for(n=1, #T~, print(T[n,]))}

G.f. of column k: 1 + R(x) + (R(x^3) - R(x)^3)/3 where R(x) is the g.f. of column k of A319539.

A220829 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [2], with each label used at least once.

Original entry on oeis.org

0, 1, 2, 4, 10, 27, 74, 226, 710, 2354, 8010, 28189, 101094, 370119, 1375198, 5181003, 19740940, 75990173, 295100800, 1155106357, 4553312866, 18063117153, 72069297826, 289053128879, 1164870009786, 4714970819402, 19161572076550, 78162885020942, 319940035684684, 1313799822309748

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

Cf. A129860, A220826.

my(N=30); U(N,2) - 2*U(N,1) \\ See A339650 for U(n,k). - Andrew Howroyd, Dec 14 2020

a(n) = A220826(n) - 2*A129860(n). - Andrew Howroyd, Dec 14 2020

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

A220830 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [3], with each label used at least once.

Original entry on oeis.org

0, 0, 1, 6, 30, 140, 663, 3186, 15642, 78441, 400842, 2084698, 11009358, 58955139, 319619706, 1752122667, 9700923252, 54194387085, 305216395077, 1731579241287, 9889280682948, 56822058078669, 328300135291659, 1906449141877331, 11122447670117451, 65168427936552522

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

Cf. A129860, A220826, A220827, A220829.

a(n) = A220827(n) - 3*A220826(n) + 3*A129860(n). - Andrew Howroyd, Dec 14 2020

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

A220831 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [4], with each label used at least once.

Original entry on oeis.org

0, 0, 0, 3, 36, 310, 2376, 17304, 123508, 874998, 6197220, 44035861, 314538360, 2260572810, 16353884828, 119102737971, 873124996284, 6441569967712, 47813037934740, 356947999429560, 2679333805629928, 20214890317096644, 153250432833122904, 1167042280999763748

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

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

A339651 Number of trees with n integer labeled leaves spanning an initial interval of positive integers and all non-leaf nodes having degree 3.

Original entry on oeis.org

1, 1, 2, 4, 14, 92, 884, 11200, 175460, 3264456, 70251004, 1715832180, 46881727360, 1416695166888, 46909359288468, 1688908328539092, 65689047712686678, 2744769306400145168, 122618498876673122160, 5832010466617354498700, 294228096306408399225374

Offset: 0

Andrew Howroyd, Dec 14 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row sums of A339650.

Cf. A319590 (rooted).

\\ here U(n,k) is k-th column of A339650 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) }
seq(n)={sum(k=0, n, U(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) )}

cp's OEIS Frontend

A339780 Triangle read by rows: T(n,k) is the number of homeomorphically irreducible leaf colored trees with n leaves using exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A339649 Array read by antidiagonals: T(n,k) is the number of leaf colored trees with n leaves of k colors and all non-leaf nodes having degree 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A220829 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [2], with each label used at least once.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A220830 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [3], with each label used at least once.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A220831 Number of unrooted binary leaf-multi-labeled trees with n leaves on the label set [4], with each label used at least once.

Views

Author

Keywords

Links

Crossrefs

Extensions

A339651 Number of trees with n integer labeled leaves spanning an initial interval of positive integers and all non-leaf nodes having degree 3.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI