

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.


4



0, 1, 2, 9, 64, 625, 7770, 117390, 2088520, 42771960, 991090800, 25635767850, 732235165200, 22890759391500, 777398836414200, 28501053507927000, 1121908690738836000, 47194400446765572000, 2112854517933207048000, 100302903229033765260000, 5032863920347902999360000
(list;
graph;
refs;
listen;
history;
text;
internal format)



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. 34 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

Table of n, a(n) for n=0..20.
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), 110, esp. Eq. (14) with r = 4.
Index entries for sequences related to rooted trees


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+nmj)*2^(2*r2*n+m+2*j)*binomial(m,j)*3^(j). (End)
a(n) = (n1)! * [x^(n1)] 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[n1][f[4, n]][0]];
a /@ Range[0, 20] (* JeanFrançois Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)


PROG

(Maxima)
a(n):=(n!*sum(binomial(n+1, r)*sum(binomial(r, m)*sum(binomial(j, r+nmj)*2^(2*r2*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, from Benjamin Otto, Apr 11 2019 )
# 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_entries1):
...curr_pow=(curr_pow*eP).expand()
...r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r)


CROSSREFS

Cf. A036774, A036775, A036777. Column k=4 of A325201; see that entry for sequences related to other preimage constraints constructions.
Sequence in context: A128577 A052514 A274395 * A036777 A325205 A325206
Adjacent sequences: A036773 A036774 A036775 * A036777 A036778 A036779


KEYWORD

nonn


AUTHOR

N. J. A. Sloane


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



