OFFSET
0,3
COMMENTS
A preimage constraint 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.
Thus, a(n) is the number of endofunctions on a set of size n such that each preimage has at most 8 elements. Equivalently, it is the number of n-letter words from an n-letter alphabet such that no letter appears more than 8 times.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..386
B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.6 and 7.8.
FORMULA
a(n) = n! * [x^n] e_8(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_8 * n^(-1/2) * r_8^-n.
MAPLE
b:= proc(n, i) option remember; `if`(n=0 and i=0, 1, `if`(i<1, 0,
add(b(n-j, i-1)*binomial(n, j), j=0..min(8, n))))
end:
a:= n-> b(n$2):
seq(a(n), n=0..20); # Alois P. Heinz, Apr 01 2019
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0 && i == 0, 1, If[i<1, 0, Sum[b[n-j, i-1]* Binomial[n, j], {j, 0, Min[8, n]}]]];
a[n_] := b[n, n];
a /@ Range[0, 19] (* Jean-François Alcover, Feb 29 2020, after Alois P. Heinz *)
PROG
(Python)
# print first num_entries entries in the sequence
import math, sympy; x=sympy.symbols('x')
k=8; num_entries = 64
P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [1]; curr_pow = 1
for term in range(1, num_entries):
curr_pow=(curr_pow*eP).expand()
r.append(curr_pow.coeff(x**term)*math.factorial(term))
print(r)
CROSSREFS
KEYWORD
nonn
AUTHOR
Benjamin Otto, Mar 25 2019
STATUS
approved