A319590 -id:A319590 - cp's OEIS frontend

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.

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

A318230 Number of inequivalent leaf-colorings of binary rooted trees with 2n + 1 nodes.

Original entry on oeis.org

1, 2, 4, 18, 79, 474, 3166, 24451, 208702, 1958407, 19919811, 217977667, 2547895961, 31638057367, 415388265571, 5743721766718, 83356613617031, 1265900592208029, 20064711719120846, 331153885800672577, 5679210649417608867, 101017359002718628295, 1860460510677429522171

Offset: 0

Gus Wiseman, Aug 21 2018

nonn

			Inequivalent representatives of the a(3) = 18 leaf-colorings of binary rooted trees with 7 nodes:
  (1(1(11)))  ((11)(11))
  (1(1(12)))  ((11)(12))
  (1(1(22)))  ((11)(22))
  (1(1(23)))  ((11)(23))
  (1(2(11)))  ((12)(12))
  (1(2(12)))  ((12)(13))
  (1(2(13)))  ((12)(34))
  (1(2(22)))
  (1(2(23)))
  (1(2(33)))
  (1(2(34)))

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

Cf. A000081, A001190, A001678, A003238, A004111, A111299, A290689, A304486.

Cf. A318226, A318227, A318228, A318229, A318231, A318234, A319590, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, my(p=x*Ser(v[1..n-1])); v[n]=polcoef(p^2 + if(n%2==0, sRaise(p,2)), n)/2); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(20)) \\ Andrew Howroyd, Dec 11 2020

Terms a(5) and beyond from Andrew Howroyd, Dec 10 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

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

A318230 Number of inequivalent leaf-colorings of binary rooted trees with 2n + 1 nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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