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,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

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

Sequence in context: A245411 A324807 A245412 * A245413 A344658 A226272

Adjacent sequences: A324805 A324806 A324807 * A324809 A324810 A324811

Keyword

nonn

Author

Benjamin Otto, Mar 25 2019

Status

approved