A141610 Number of rooted trees with n points and exactly k specified colors: C(n,k), 1<=n, 1<=k<=n.

1, 1, 2, 2, 10, 9, 4, 44, 102, 64, 9, 196, 870, 1304, 625, 20, 876, 6744, 18200, 20080, 7776, 48, 4020, 50421, 218260, 416500, 362322, 117649, 115, 18766, 371676, 2427600, 7133655, 10465290, 7503328, 2097152, 286, 89322, 2731569, 25919692, 110136425, 242427438, 288002582, 175481056, 43046721

Offset

1,3

Comments

The number of rooted trees with n points having any of c colors is Sum_k C(n,k) {c choose k}.

Links

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

John Riordan, The numbers of labeled colored and chromatic trees, Acta Mathematica, 97 (1957), 211-225.

John Riordan, The numbers of labeled colored and chromatic trees [Dead link]

Example

C(n,1) is the number of rooted trees with n points (A000081). C(n,n)=n^{n-1}. C(3,2)=10 is the number of rooted trees with three points and two colors: AAB, ABB, ABA, BAA, BAB, BBA, A(BB), A(AB), B(AA), B(AB), where ABC is a rooted tree with A the root, B attached to A and C; A(BC) is a rooted tree with A the root, A attached to B and C.
   1;
   1,   2;
   2,  10,    9;
   4,  44,  102,    64;
   9, 196,  870,  1304,   625;
  20, 876, 6744, 18200, 20080, 7776;
  ...

Maple

b:= proc(n, k) option remember; `if`(n<2, k*n, (add(add(b(d, k)*
      d, d=numtheory[divisors](j))*b(n-j, k), j=1..n-1))/(n-1))
    end:
C:= (n, k)-> add(b(n, k-j)*binomial(k, j)*(-1)^j, j=0..k):
seq(seq(C(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Dec 11 2020

Mathematica

p[a_List]:=a; p[a_List, b_List, c___List]:=If[Length[a]
<=Length[b], p[PadRight[a, Length[b]]+b, c], p[b, a, c]];
c[i_, j_]:=If[i<j, c[j, i], PadLeft[Table
[Binomial[j, k]Binomial[i+k, j], {k, 0, j}], i+j]];
t[a_List, b_List]:=Apply[p, Outer[c, Range[Length[a]],
Range[Length[b]]]Outer[Times, a, b], {0, 1}];
s[n_, k_]:=s[n, k]=p[If[n<2k, {0}, s[n-k, k]], a[n+1-k]];
a[1]={1}; a[n_]:=a[n]=Apply[p, Table
[t[a[i], s[n-1, i]]i, {i, 1, n-1}]]/(n-1);
Flatten[Table[a[i], {i, 1, 10}]]
(* Second program: *)
b[n_, k_] := b[n, k] = If[n<2, k*n, (Sum[Sum[b[d, k]*d, {d, Divisors[j]}]* b[n-j, k], {j, 1, n-1}])/(n-1)];
c[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}];
Table[Table[c[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

Prog

(PARI) \\ here U(N, m) is adaptation of A000081 for m colors.
U(N, m)={my(A=vector(N, j, m)); for(n=1, N-1, A[n+1] = sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1])/n); A}
M(n)={my(v=vector(n, i, U(n, i)~)); 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]))} \\ Andrew Howroyd, Sep 15 2018

Crossrefs

Columns 1..3 are A000081, A339642, A339643.

C(n,n) is A000169.

Row sums are A339644.

Cf. A256064.

Sequence in context: A293061 A129898 A135996 * A019241 A168295 A309751

Adjacent sequences: A141607 A141608 A141609 * A141611 A141612 A141613

Keyword

nonn,tabl

Author

Robert A. Russell, Aug 22 2008, Aug 27 2008

Status

approved