1,3

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

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

J. Riordan, The numbers of labeled colored and chromatic trees.

C(n,1) is the number of rooted trees with n points (A81). 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.

Contribution from Robert A. Russell (russell(AT)post.harvard.edu), Sep 03 2008: (Start)

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

(End)

C(n,1) is A000081. C(n,n) is A000169. [From Robert A. Russell (russell(AT)post.harvard.edu), Sep 03 2008]

Sequence in context: A094359 A129898 A135996 this_sequence A019241 A032005 A147801

Adjacent sequences: A141607 A141608 A141609 this_sequence A141611 A141612 A141613

nonn,tabl

Robert A. Russell (russell(AT)post.harvard.edu), Aug 22 2008, Aug 27 2008