A036776 a(n) is the number of labeled rooted trees on a set of size n where each node has at most 4 neighbors that are further away from the root than the node itself.

0, 1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

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.
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A036774, A036775, A036777. Column k=4 of A325201; see that entry for sequences related to other preimage constraints constructions.

Programs

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]];
a /@ Range[0, 20] (* Jean-François Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)

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

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

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