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.

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

Alois P. Heinz, Rows n = 0..140, flattened

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

Adjacent sequences: A245729 A245730 A245731 * A245733 A245734 A245735

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 30 2014

Status

approved