|
| |
|
|
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.
|
|
7
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,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
|
Table of n, a(n) for n=1..66.
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.
|
|
|
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.
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
|
|
|
STATUS
|
approved
|
| |
|
|
