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
Examples
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 ... ...
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.
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.
Programs
-
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 *) -
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)
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
Extensions
Offset changed to 0 by Alois P. Heinz, Jun 28 2023
Comments