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

Author

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

Keywords

• nonn
• tabl

Comments

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

Examples

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

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]

Crossrefs

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

C(n,n) is A000169.

Row sums are A339644.

Cf. A256064.

Programs

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[iJean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

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