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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A029855 Number of rooted trees where root has degree 4. 2
1, 1, 3, 7, 19, 46, 124, 320, 858, 2282, 6161, 16647, 45352, 123861, 340000, 936098, 2586518, 7166394, 19911638, 55456892, 154814055, 433081632, 1213901668, 3408659401, 9587879987, 27011564035, 76212078500 (list; graph; refs; listen; history; text; internal format)
OFFSET

5,3

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 53.

LINKS

Washington Bomfim, Table of n, a(n) for n = 5..200

Frank Ruskey, Combinatorial Generation Algorithm 4.26, p. 96

Eric Weisstein's World of Mathematics, Frequency Representation

Eric Weisstein's World of Mathematics, Rooted Tree

Index entries for sequences related to rooted trees

FORMULA

a(n)= Sum_(P){ Prod_(1^a1 2^a2 3^a3 ...){ binomial(f(i)+a_i -1, a_i) } }, where P is the set of the partitions of n with four parts, and f = A000081. - Washington Bomfim, Jul 10 2012

MATHEMATICA

Needs["Combinatorica`"];

nn=30; s[n_, k_]:=s[n, k]=a[n+1-k]+If[n<2k, 0, s[n-k, k]]; a[1]=1; a[n_]:=a[n]=Sum[a[i]s[n-1, i]i, {i, 1, n-1}]/(n-1); rt=Table[a[i], {i, 1, nn}]; Drop[Take[CoefficientList[CycleIndex[SymmetricGroup[4], s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], nn], 4]  (* Geoffrey Critzer, Oct 14 2012, after code by Robert A. Russell in A000081 *)

PROG

(PARI)

max_n = 200; f=vector(max_n);            \\ f[n] = A000081[n], n=1..max_n

sum2(k) = {local(s); s=0; fordiv(k, d, s += d*f[d]); return(s)};

Init_f()={f[1]=1;

for(n =1, max_n -2, s=0; for(k=1, n, s+=sum2(k)*f[n-k+1]); f[n+1]=s/n)};

S=0; P=[0, 1, 1, 1, 1, 0];

visit4() = {i = 3; k = 2; p = P[2]; Pr = 1;

while(1, while(P[i]==p, i++); c=i-k; Pr*=binomial(f[P[k]]+c-1, c);

if(P[i] == 0, S += Pr; return); p = P[i]; k = i; i++)};

                                         \\ F. Ruskey partition generator

Part(n, k, s, t) = { P[t] = s;

if((k == 1) || (n == k), visit4(), L = max(1, ceil((n - s)/(k - 1)));

for(j = L, min(s, n-s-k+2), Part(n-s, k-1, j, t+1))); P[t] = 1; };

\\

a(n) = {S=0; n--; Part(2*n, 4+1, n, 1); return(S)}

Init_f(); for(n=5, max_n, print(n, " ", a(n)))           \\ b-file format

\\ # Washington Bomfim, Jul 10 2012

CROSSREFS

Cf. A000226 (root degree 3), A000081.

Sequence in context: A185696 A141344 A280756 * A209397 A110014 A026581

Adjacent sequences:  A029852 A029853 A029854 * A029856 A029857 A029858

KEYWORD

nonn

AUTHOR

Christian G. Bower

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 19:17 EST 2018. Contains 299469 sequences. (Running on oeis4.)