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

Author

Christian G. Bower

Keywords

• nonn

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

Crossrefs

Cf. A000226 (root degree 3), A000081, A033185.

Programs

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 *)

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

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