A319376 -id:A319376 - cp's OEIS frontend

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312

Offset: 1

Andrew Howroyd, Dec 11 2020

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     3,      2;
    5,    17,     12,      5;
   12,    73,     95,     44,     12;
   33,   369,    721,    512,    168,     33;
   90,  1795,   5487,   5480,   2556,    625,    90;
  261,  9192,  41945,  58990,  36711,  12306,  2342,  261;
  766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
  ...
From _Gus Wiseman_, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
  (1111)      (1112)      (1123)      (1234)
  (1(111))    (1122)      (1(123))    (1(234))
  (11(11))    (1(112))    (11(23))    (12(34))
  ((11)(11))  (11(12))    (12(13))    ((12)(34))
  (1(1(11)))  (1(122))    (2(113))    (1(2(34)))
              (11(22))    (23(11))
              (12(11))    ((11)(23))
              (12(12))    (1(1(23)))
              (2(111))    ((12)(13))
              ((11)(12))  (1(2(13)))
              (1(1(12)))  (2(1(13)))
              ((11)(22))  (2(3(11)))
              (1(1(22)))
              (1(2(11)))
              ((12)(12))
              (1(2(12)))
              (2(1(11)))
(End)

Andrew Howroyd, PARI Functions for Combinatorial Species, v2, Dec 2020.
Wikipedia, Combinatorial species

The case with only one color is A000669.
Counting by nodes gives A318231.
A labeled version is A319376.
Row sums are A330470.
A000311 counts singleton-reduced phylogenetic trees.
A001678 counts unlabeled lone-child-avoiding rooted trees.
A005121 counts chains of set partitions, with maximal case A002846.
A005804 counts phylogenetic rooted trees with n labels.
A060356 counts labeled lone-child-avoiding rooted trees.
A141268 counts lone-child-avoiding rooted trees with leaves summing to n.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A316651 counts lone-child-avoiding rooted trees with normal leaves.
A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.
A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.
Cf. A196545, A213427, A281118, A289501, A292504, A318812, A319312, A330627.

\\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n,1..n]))}

A316651 Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

Original entry on oeis.org

1, 2, 12, 112, 1444, 24086, 492284, 11910790, 332827136, 10546558146, 373661603588, 14636326974270, 628032444609396, 29296137817622902, 1476092246351259964, 79889766016415899270, 4622371378514020301740, 284719443038735430679268, 18601385258191195218790756

Offset: 1

Gus Wiseman, Jul 09 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(3) = 12 trees:
  (1(11)), (111),
  (1(12)), (2(11)), (112),
  (1(22)), (2(12)), (122),
  (1(23)), (2(13)), (3(12)), (123).

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

Cf. A000081, A000311, A000669, A001678, A005804, A034691, A141268, A292504.
Cf. A316652, A316653, A316654, A316655, A316656, A319369.
Row sums of A319376.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> add(add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20);  # Alois P. Heinz, Sep 18 2018

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=If[Length[m]==1,m,Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])]];
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Sum[Length[gro[m]],{m,allnorm[n]}],{n,5}]
(* Second program: *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
     Sum[Binomial[A[i, k] + j - 1, j] b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := Sum[Sum[A[n, k-j]*(-1)^j*Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

\\ here R(n,k) is A000669, A050381, A220823, ...
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}
seq(n)={sum(k=1, n, R(n,k)*sum(r=k, n, binomial(r,k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Sep 14 2018

From Vaclav Kotesovec, Sep 18 2019: (Start)
a(n) ~ c * d^n * n^(n-1), where d = 1.37392076830840090205551979... and c = 0.41435722857311602982846...
a(n) ~ 2*log(2)*A326396(n)/n. (End)

Terms a(9) and beyond from Andrew Howroyd, Sep 14 2018

A319254 Array read by antidiagonals: T(n,k) is the number of series-reduced rooted trees with n leaves of k colors.

Original entry on oeis.org

1, 2, 1, 3, 3, 2, 4, 6, 10, 5, 5, 10, 28, 40, 12, 6, 15, 60, 156, 170, 33, 7, 21, 110, 430, 948, 785, 90, 8, 28, 182, 965, 3396, 6206, 3770, 261, 9, 36, 280, 1890, 9376, 28818, 42504, 18805, 766, 10, 45, 408, 3360, 21798, 97775, 256172, 301548, 96180, 2312

Offset: 1

Andrew Howroyd, Sep 15 2018

Not all colors need to be used.

See table 2.3 in the Johnson reference.

			Array begins:
==================================================================
n\k|   1     2       3        4         5         6          7
---+--------------------------------------------------------------
1  |   1     2       3        4         5         6          7 ...
2  |   1     3       6       10        15        21         28 ...
3  |   2    10      28       60       110       182        280 ...
4  |   5    40     156      430       965      1890       3360 ...
5  |  12   170     948     3396      9376     21798      44856 ...
6  |  33   785    6206    28818     97775    269675     642124 ...
7  |  90  3770   42504   256172   1068450   3496326    9632960 ...
8  | 261 18805  301548  2357138  12081605  46897359  149491104 ...
9  | 766 96180 2195100 22253672 140160650 645338444 2379859608 ...
...

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

Columns 1..5 are A000669, A050381, A220823, A220824, A220825.
Main diagonal is A319369.
Cf. A141610, A242249, A255517, A256064, A256068, A319376.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Sep 17 2018

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
Table[A[n, 1 + d - n], {d, 1, 12}, {n, 1, d}] // Flatten (* Jean-François Alcover, Sep 11 2019, after Alois P. Heinz *)

\\ here R(n,k) gives k'th column as a 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}
{my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n,]))} \\ Andrew Howroyd, Sep 15 2018

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

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 2, 14, 27, 15, 3, 48, 180, 240, 105, 6, 171, 1089, 2604, 2625, 945, 11, 614, 6333, 24180, 42075, 34020, 10395, 23, 2270, 36309, 207732, 554820, 755370, 509355, 135135, 46, 8518, 207255, 1710108, 6578550, 13408740, 14963130, 8648640, 2027025

Offset: 1

Andrew Howroyd, Sep 22 2018

See table 2.2 in the Johnson reference.

			Triangle begins:
   1;
   1,    1;
   1,    4,     3;
   2,   14,    27,     15;
   3,   48,   180,    240,    105;
   6,  171,  1089,   2604,   2625,    945;
  11,  614,  6333,  24180,  42075,  34020,  10395;
  23, 2270, 36309, 207732, 554820, 755370, 509355, 135135;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. South Carolina, 2012.

Columns 1..5 are A001190, A220819, A220820, A220821, A220822.
Main diagonal is A001147.
Row sums give A319590.
Cf. A241555, A319376, A319539.

A:= proc(n, k) option remember; `if`(n<2, k*n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(A(n/2, k)))+add(A(i, k)*A(n-i, k), i=1..n/2))
    end:
T:= (n, k)-> add((-1)^i*binomial(k, i)*A(n, k-i), i=0..k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Sep 23 2018

A[n_, k_] := A[n, k] = If[n<2, k n, If[OddQ[n], 0, (#(1-#)/2)&[A[n/2, k]]] + Sum[A[i, k] A[n - i, k], {i, 1, n/2}]];
T[n_, k_] := Sum[(-1)^i Binomial[k, i] A[n, k - i], {i, 0, k}];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 02 2019, after Alois P. Heinz *)

\\ here R(n,k) is k-th column of A319539 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}
M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

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

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

Original entry on oeis.org

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])); }

A319377 Number of series-reduced rooted trees with n leaves of exactly two colors.

Original entry on oeis.org

1, 6, 30, 146, 719, 3590, 18283, 94648, 497757, 2652898, 14307845, 77958746, 428588051, 2374676854, 13247984959, 74357762790, 419604029622, 2379243477538, 13549087798391, 77458553063930, 444383895880897, 2557639072274418, 14763596994726379, 85449948037167684

Offset: 2

Andrew Howroyd, Sep 17 2018

nonn

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

Column 2 of A319376.

Cf. A000669, A050381.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> A(n, 2) -2*A(n, 1):
seq(a(n), n=2..30);  # Alois P. Heinz, Sep 18 2018

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n*k, b[n, n - 1, k]];
a[n_] := A[n, 2] - 2*A[n, 1];
a /@ Range[2, 30] (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)

\\ 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}
seq(n)={(R(n,2)-2*R(n,1))[2..n]}

a(n) = A050381(n) - 2*A000669(n).

A326396 Total number of colors in all series-reduced rooted trees with n leaves where colors span an initial interval of the color palette.

Original entry on oeis.org

1, 3, 26, 322, 5210, 104421, 2491498, 68907073, 2166242180, 76266794945, 2972079029674, 126987589678185, 5902427979920102, 296484317531254557, 16003975713659818226, 923838934059255332723, 56788871072327503930862, 3703444074072753204057172

Offset: 1

Alois P. Heinz, Sep 11 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..200

Cf. A316651, A319376.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
a:= n-> add(k*add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1), k=1..n):
seq(a(n), n=1..20);

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0,
    Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A [n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
a[n_] := Sum[k Sum[A[n, k-j](-1)^j Binomial[k, j], {j, 0, k-1}], {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} k * A319376(n,k).
From Vaclav Kotesovec, Sep 18 2019: (Start)
a(n) ~ c * d^n * n^n, where d = 1.37392076830840090205551979... and c = 0.29889555940946459367729...
a(n) ~ n*A316651(n)/(2*log(2)). (End)

cp's OEIS Frontend

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A316651 Number of series-reduced rooted trees with n leaves spanning an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A319254 Array read by antidiagonals: T(n,k) is the number of series-reduced rooted trees with n leaves of k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A319377 Number of series-reduced rooted trees with n leaves of exactly two colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A326396 Total number of colors in all series-reduced rooted trees with n leaves where colors span an initial interval of the color palette.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica