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
KEYWORD
nonn
AUTHOR
STATUS
approved