A324808 a(n) is the number of endofunctions on a set of size n with preimage constraint {0, 1, 2, 3, 4, 5, 6, 7, 8}.

1, 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420480, 9999999090, 285311608890, 8916096836988, 302874907278372, 11111996007290178, 437893300069054830, 18446711285575475760, 827238394513348062960, 39346298554172667026112, 1978413024254468818876002

Offset: 0

Author

Benjamin Otto, Mar 25 2019

Keywords

• nonn

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.

Crossrefs

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

Programs

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 *)

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)

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.