The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 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 COMMENTS Fourth column of A033185. - Michael Somos, Aug 20 2018 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 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 a(n) ~ c * A051491^n / n^(3/2), where c = 0.036592912312268101787903577... - Vaclav Kotesovec, Dec 26 2020 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, A033185. Sequence in context: A185696 A141344 A280756 * A209397 A110014 A026581 Adjacent sequences:  A029852 A029853 A029854 * A029856 A029857 A029858 KEYWORD nonn AUTHOR 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.

Last modified June 18 23:16 EDT 2021. Contains 345125 sequences. (Running on oeis4.)