

A036775


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


4



0, 1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000, 204621522793150838094720000
(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 <= 3.  Geoffrey Critzer, Mar 22 2013
A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every nonroot node to its neighbor that is closer to the root and sending the root to itself. Thus a(n) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most 3 entries.  Benjamin Otto, Apr 08 2019
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).  Petros Hadjicostas, Jun 09 2019


LINKS

Table of n, a(n) for n=0..21.
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 = 3.
Index entries for sequences related to rooted trees


FORMULA

E.g.f.: (for shifted sequence a(0)=0, a(1)=1, ...) A(x) satisfies A(x) = 1 + x*A(x) + (1/2)*x^2*A(x)^2 + (1/6)*x^3*A(x)^3.
a(n) = 3*n!*Sum_{j=0..n+1} binomial(n+1, j)*Sum_{i=j..n+j} binomial(j, ij)*2^(4*j2*ni2)*6^(n+i+1)*binomial(nj+1, 3*jni2)/6^(3*j).  Vladimir Kruchinin, Nov 21 2011
a(n) ~ sqrt(s/(1+r*s)) * n^n / (r^(n+1) * exp(n)), where r = 0.37589405207806352... is the root of the equation 8 + 21*r + 2*r^3 = 0 and s = 2.86947048655283754... is the root of the equation 12 + 36*s  57*s^2 + 16*s^3 = 0.  Vaclav Kotesovec, Jan 08 2014
a(n) = (n1)! * [x^(n1)] e_3(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_3 * n^(3/2) * r_3^n.  Benjamin Otto, Apr 08 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!), {x, 0, nn}], x]; Table[a[n], {n, 0, nn}]/.s (* Geoffrey Critzer, Mar 22 2013 *)
Table[3*n!*Sum[Binomial[n+1, j]*Sum[Binomial[j, ij]*2^(4*j2*ni2)*6^(n+i+1)*Binomial[nj+1, 3*jni2], {i, j, n+j}]/6^(3*j), {j, 0, n+1}], {n, 0, 20}] (* Vaclav Kotesovec after Vladimir Kruchinin, Jan 08 2014 *)
f[r_, n_][x_] := Sum[x^k/k!, {k, 0, r}]^n;
a[n_] := If[n == 1, 1, Derivative[n  1][f[3, n]][0]];
a /@ Range[0, 21] (* JeanFrançois Alcover, Apr 20 2020, after Petros Hadjicostas in A036777 *)


PROG

(Maxima) a(n):=3*n!*sum((binomial(n+1, j)*sum(binomial(j, ij)*2^(4*j2*ni2)*6^(n+i+1)*binomial(nj+1, 3*jni2), i, j, n+j))/6^(3*j), j, 0, (n+1)); /* Vladimir Kruchinin, Nov 21 2011 */
(Python, from Benjamin Otto, Apr 08 2019)
# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=3; 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, A036776, A036777.
Column k=3 of A325201; see that entry for sequences related to other preimage constraints constructions.  Benjamin Otto, Apr 08 2019
Sequence in context: A331658 A269487 A179199 * A141209 A269770 A269649
Adjacent sequences: A036772 A036773 A036774 * A036776 A036777 A036778


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



