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

0, 1, 2, 9, 64, 625, 7776, 117649, 2097152, 43046721, 1000000000, 25937424590, 743008369224, 23298084997044, 793714764270428, 29192925433321650, 1152921466989795360, 48661189511753527280, 2185911410555033096364, 104127340753401006230046, 5242879377215160617336400

Offset: 0

Author

Benjamin Otto, Jul 05 2019

Keywords

• easy
• nonn

Comments

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 non-root 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 9 entries.

Links

• B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.

Crossrefs

Column k=9 of A325201; see that entry for sequences related to other preimage constraints constructions.

Programs

Mathematica

e[k_][x_] := Sum[x^j/j!, {j, 0, k}];
a[0] = 0; a[n_] := (n - 1)! Coefficient[e[9][x]^n, x, n - 1];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 06 2019 *)

Python

# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=9; 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)

Formula

a(n) = (n-1)! * [x^(n-1)] e_9(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. The link above yields explicit constants c_k, r_k so that the columns are asymptotically c_9 * n^(-3/2) * r_9^-n.