|
|
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
|
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 53.
|
|
LINKS
|
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|