A339780 -id:A339780 - 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.

A339785 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 2 colors.

Original entry on oeis.org

0, 1, 2, 7, 24, 91, 354, 1491, 6504, 29711, 139616, 674696, 3328798, 16730955, 85382210, 441571216, 2310003732, 12206975528, 65082858008, 349756996762, 1892980028014, 10310987833049, 56489307860860, 311112321625754, 1721692801914844, 9569930999155801, 53410232801675436

Offset: 1

Andrew Howroyd, Dec 16 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column k=2 of A339780.

Cf. A007827, A339782.

my(N=25); (U(N,2)-2*U(N,1))[2..1+N] \\ See A339780 for U(n,k).

a(n) = A339782(n) - 2*A007827(n).

A339786 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 3 colors.

Original entry on oeis.org

0, 0, 1, 9, 63, 412, 2673, 17571, 117365, 798819, 5530122, 38908380, 277750749, 2009160864, 14707923021, 108835512411, 813241695330, 6130521151377, 46584949832013, 356571373433217, 2747371943624943, 21296479544449677, 165994877608025730, 1300408539157086640

Offset: 1

Andrew Howroyd, Dec 18 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column k=3 of A339780.

Cf. A007827, A339782, A339783, A339785.

my(N=25); (U(N,3) - 3*U(N,2) + 3*U(N,1))[2..1+N] \\ See A339780 for U(n, k).

a(n) = A339783(n) - 3*A339782(n) + 3*A007827(n).

A339781 Number of homeomorphically irreducible trees with n integer labeled leaves covering an initial interval of positive integers.

Original entry on oeis.org

1, 1, 2, 4, 22, 184, 2278, 37076, 747830, 17938120, 498221046, 15716127456, 554857740936, 21672428437044, 927792029298550, 43195423181912812, 2172838098801762500, 117433517088859845912, 6786305674234003471552, 417560119759063983102136, 27254276361313006814819076

Offset: 0

Andrew Howroyd, Dec 16 2020

nonn

Homeomorphically irreducible trees are trees without vertices of degree 2.

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

Row sums of A339780.

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)}
seq(n)={sum(k=0, n, U(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) )}

A339787 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 4 colors.

Original entry on oeis.org

0, 0, 0, 4, 68, 812, 8512, 84312, 814184, 7781712, 74182124, 708344640, 6790655496, 65440865012, 634347822304, 6186652422650, 60707391493004, 599283097168488, 5950282272766412, 59408426130151164, 596269843123151304, 6014472189177940224, 60952019560703982452

Offset: 1

Andrew Howroyd, Dec 18 2020

nonn

			There are 2 homeomorphically reduced trees with 4 leafs:
            o          o   o
            |          |   |
        o---o---o      o---o
            |          |   |
            o          o   o
The leaves of the first tree can be colored in 1 way using all four colors and the second can be colored in 3 ways, so a(4) = 1 + 3 = 4.

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column k=4 of A339780.

Cf. A339785, A339786.

my(N=25); M(N,4)[2..1+N, 5]~ \\ See A339780 for M(n, m).

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

A339785 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 2 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A339786 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 3 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A339781 Number of homeomorphically irreducible trees with n integer labeled leaves covering an initial interval of positive integers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A339787 Number of homeomorphically irreducible leaf colored trees with n leaves using exactly 4 colors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI