A029855 Number of rooted trees where root has degree 4.

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

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

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

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

Christian G. Bower

Status

approved