[go: up one dir, main page]

login
A245732
Number T(n,k) of endofunctions on [n] such that at least one preimage with cardinality >=k exists and a nonempty preimage of j implies that all i<=j have preimages with cardinality >=k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
22
1, 1, 1, 4, 3, 1, 27, 13, 1, 1, 256, 75, 7, 1, 1, 3125, 541, 21, 1, 1, 1, 46656, 4683, 141, 21, 1, 1, 1, 823543, 47293, 743, 71, 1, 1, 1, 1, 16777216, 545835, 5699, 183, 71, 1, 1, 1, 1, 387420489, 7087261, 42241, 2101, 253, 1, 1, 1, 1, 1
OFFSET
0,4
COMMENTS
T(0,0) = 1 by convention.
In general, column k > 1 is asymptotic to n! / ((1+r^(k-1)/(k-1)!) * r^(n+1)), where r is the root of the equation 2 - exp(r) + Sum_{j=1..k-1} r^j/j! = 0. - Vaclav Kotesovec, Aug 02 2014
LINKS
FORMULA
E.g.f. (for column k > 0): 1/(2 -exp(x) +Sum_{j=1..k-1} x^j/j!) -1. - Vaclav Kotesovec, Aug 02 2014
EXAMPLE
Triangle T(n,k) begins:
0 : 1;
1 : 1, 1;
2 : 4, 3, 1;
3 : 27, 13, 1, 1;
4 : 256, 75, 7, 1, 1;
5 : 3125, 541, 21, 1, 1, 1;
6 : 46656, 4683, 141, 21, 1, 1, 1;
7 : 823543, 47293, 743, 71, 1, 1, 1, 1;
8 : 16777216, 545835, 5699, 183, 71, 1, 1, 1, 1;
MAPLE
b:= proc(n, k) option remember; `if`(n=0, 1,
add(b(n-j, k)*binomial(n, j), j=k..n))
end:
T:= (n, k)-> `if`(k=0, n^n, `if`(n=0, 0, b(n, k))):
seq(seq(T(n, k), k=0..n), n=0..12);
MATHEMATICA
b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n-j, k]*Binomial[n, j], {j, k, n}]]; T[n_, k_] := If[k == 0, n^n, If[n == 0, 0, b[n, k]]]; T[0, 0] = 1; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 05 2015, after Alois P. Heinz *)
CROSSREFS
Column k=0 gives A000312.
Columns k=1-10 give (for n>0): A000670, A032032, A102233, A232475, A245790, A245791, A245792, A245793, A245794, A245795.
T(2n,n) gives A244174(n) or 1+A007318(2n,n) = 1+A000984(n) for n>0.
Cf. A245733.
Sequence in context: A350528 A208057 A298673 * A039621 A142158 A203412
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 30 2014
STATUS
approved