A306800 Square array whose entry A(n,k) is the number of endofunctions on a set of size n with preimage constraint {0,1,...,k}, for n >= 0, k >= 0, read by descending antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 4, 6, 0, 1, 1, 4, 24, 24, 0, 1, 1, 4, 27, 204, 120, 0, 1, 1, 4, 27, 252, 2220, 720, 0, 1, 1, 4, 27, 256, 3020, 29520, 5040, 0, 1, 1, 4, 27, 256, 3120, 44220, 463680, 40320, 0, 1, 1, 4, 27, 256, 3125, 46470, 765030, 8401680, 362880, 0

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.

Sequence in context: A292712 A331571 A247504 * A235955 A077762 A244677

Adjacent sequences: A306797 A306798 A306799 * A306801 A306802 A306803

Keyword

easy,nonn,tabl

Author

Benjamin Otto, Mar 10 2019

Extensions

Offset changed to 0 by Alois P. Heinz, Jun 28 2023

Status

approved