OFFSET
0,9
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,k) is the number of endofunctions on a set of size n such that each preimage has at most k entries. Equivalently, A(n,k) is the number of n-letter words from an n-letter alphabet such that no letter appears more than k times.
LINKS
Alois P. Heinz, Antidiagonals n = 0..140, flattened
B. Otto, Coalescence under Preimage Constraints, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.6 and 7.8.
FORMULA
A(n,k) = n! * [x^n] e_k(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. When k>1, the link above yields explicit constants c_k, r_k so that the columns are asymptotically c_k * n^(-1/2) * r_k^-n. Stirling's approximation gives column k=1, and column k=0 is 0.
A(n,k) = Sum_{j=1..min(k,n)} A019575(n,j) for n>=1. - Alois P. Heinz, Jun 28 2023
EXAMPLE
Array begins:
1 1 1 1 1 ...
0 1 1 1 1 ...
0 2 4 4 4 ...
0 6 24 27 27 ...
0 24 204 252 256 ...
0 120 2220 3020 3120 ...
0 720 29520 44220 46470 ...
...
MAPLE
b:= proc(n, i, k) option remember; `if`(n=0 and i=0, 1, `if`(i<1, 0,
add(b(n-j, i-1, k)*binomial(n, j), j=0..min(k, n))))
end:
A:= (n, k)-> b(n$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..12); # Alois P. Heinz, Apr 05 2019
MATHEMATICA
b[n_, i_, k_] := b[n, i, k] = If[n==0 && i==0, 1, If[i<1, 0, Sum[b[n-j, i-1, k] Binomial[n, j], {j, 0, Min[k, n]}]]];
A[n_, k_] := b[n, n, k];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 29 2019, after Alois P. Heinz *)
PROG
(Python)
# print first num_entries entries in column k
import math, sympy; x=sympy.symbols('x')
k=5; 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
Columns 0-9: A000007, A000142, A012244, A239368, A324804, A324805, A324806, A324807, A324808, A324809.
A(n,n) gives A000312.
Similar array for preimage condition {i>=0 | i!=k}: A245413.
Number of functions with preimage condition given by the even nonnegative integers: A209289.
Sum over all k of the number of functions with preimage condition {0,k}: A231812.
Cf. A019575.
KEYWORD
AUTHOR
Benjamin Otto, Mar 10 2019
EXTENSIONS
Offset changed to 0 by Alois P. Heinz, Jun 28 2023
STATUS
approved