login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141610 Number of rooted trees with n points and exactly k specified colors: C(n,k), 0<n, 0<k<=n. 3
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 (list; table; graph; refs; listen; history; text; internal format)
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

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.

EXAMPLE

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.

1;

1, 2;

2, 10, 9;

4, 44, 102, 64;

9, 196, 870, 1304, 625;

20, 876, 6744, 18200, 20080, 7776

MATHEMATICA

Contribution from Robert A. Russell, 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)

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

C(n, 1) is A000081. C(n, n) is A000169.

Cf. A256064.

Sequence in context: A293061 A129898 A135996 * A019241 A168295 A249152

Adjacent sequences:  A141607 A141608 A141609 * A141611 A141612 A141613

KEYWORD

nonn,tabl

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 17:16 EDT 2019. Contains 324222 sequences. (Running on oeis4.)