OFFSET
0,3
COMMENTS
a(n) is the number of unordered rooted labeled trees such that each node has outdegree <= 4. - Geoffrey Critzer, Mar 23 2013
From pp. 3-4 in Takacs (1993), we see that n is the number of nodes in a labeled rooted tree such that each node has outdegree <= 3, and (as noted above by G. Critzer), a(n) is the number of such unordered rooted labeled trees (with n nodes). Apparently, the author of this sequence and other contributors exclude the node at the root, and thus the offset here is 0 (rather than 1). - Petros Hadjicostas, Jun 09 2019
LINKS
B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (14) with r = 4.
FORMULA
From Vladimir Kruchinin, Nov 22 2011: (Start)
E.g.f. A(x) satisfies: A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3 + (1/24)*A(x)^4.
a(n) = n!*Sum_{r=0..n+1} binomial(n+1,r)*Sum_{m=0..r} binomial(r,m)*Sum_{j=0..m} binomial(j,-r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m,j)*3^(-j). (End)
a(n) = (n-1)! * [x^(n-1)] e_4(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The Otto link above yields explicit constants c_k, r_k so that the columns are asymptotically c_4 * n^(-3/2) * r_4^-n. - Benjamin Otto, Apr 11 2019
MATHEMATICA
nn=18; f[x_]:=Sum[a[n]x^n/n!, {n, 0, nn}]; s=SolveAlways[0==Series[f[x]-x(1+f[x]+f[x]^2/2+f[x]^3/3!+f[x]^4/4!), {x, 0, nn}], x]; Table[a[n], {n, 0, nn}]/.s (* Geoffrey Critzer, Mar 23 2013 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n-1][f[4, n]][0]];
PROG
(Maxima)
a(n):=(n!*sum(binomial(n+1, r)*sum(binomial(r, m)*sum(binomial(j, -r+n-m-j)*2^(2*r-2*n+m+2*j)*binomial(m, j)*(3)^(-j), j, 0, m), m, 0, r), r, 0, n+1)); /* Vladimir Kruchinin, Nov 22 2011 */
(Python)
# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=4; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0, 1]; curr_pow = eP
for term in range(1, num_entries-1):
curr_pow=(curr_pow*eP).expand()
r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r) # Benjamin Otto, Apr 11 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Edited by N. J. A. Sloane, Jul 13 2019 using data from a duplicate of this entry that was submitted by Benjamin Otto, Apr 08 2019
STATUS
approved