A245733 Number T(n,k) of endofunctions on [n] such that at least one preimage with cardinality k exists and, if j is the largest value with a nonempty preimage, the preimage cardinality of i is >=k for all i<=j and equal to k for at least one i<=j; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 1, 2, 1, 14, 12, 0, 1, 181, 68, 6, 0, 1, 2584, 520, 20, 0, 0, 1, 41973, 4542, 120, 20, 0, 0, 1, 776250, 46550, 672, 70, 0, 0, 0, 1, 16231381, 540136, 5516, 112, 70, 0, 0, 0, 1, 380333228, 7045020, 40140, 1848, 252, 0, 0, 0, 0, 1

Offset: 0

Author

Alois P. Heinz, Jul 30 2014

Keywords

• nonn
• tabl

Comments

T(0,0) = 1 by convention.

Examples

			T(2,0) = 1: (2,2).
T(2,1) = 2: (1,2), (2,1).
T(2,2) = 1: (1,1).
T(3,1) = 12: (1,1,2), (1,2,1), (1,2,2), (1,2,3), (1,3,2), (2,1,1), (2,1,2), (2,1,3), (2,2,1), (2,3,1), (3,1,2), (3,2,1).
T(3,3) = 1: (1,1,1).
Triangle T(n,k) begins:
0 :         1;
1 :         0,      1;
2 :         1,      2,    1;
3 :        14,     12,    0,   1;
4 :       181,     68,    6,   0,  1;
5 :      2584,    520,   20,   0,  0, 1;
6 :     41973,   4542,  120,  20,  0, 0, 1;
7 :    776250,  46550,  672,  70,  0, 0, 0, 1;
8 :  16231381, 540136, 5516, 112, 70, 0, 0, 0, 1;
     ...
		

Links

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

Crossrefs

Columns k=0-10 give: A133286 (for n>0), A245854, A245855, A245856, A245857, A245858, A245859, A245860, A245861, A245862, A245863.

Row sums give A000312.

T(2n,n) gives A000984(n).

Cf. A245732.

Programs

Maple

b:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n-j, k)*binomial(n, j), j=k..n))
    end:
g:= (n, k)-> `if`(k=0, n^n, `if`(n=0, 0, b(n, k))):
T:= (n, k)-> g(n, k) -g(n, k+1):
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}]]; g[n_, k_] := If[k == 0, n^n, If[n == 0, 0, b[n, k]]]; T[n_, k_] := g[n, k] - g[n, k+1]; T[0, 0] = 1; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)

Formula

E.g.f. of column k=0: 1 +1/(1+LambertW(-x)) -1/(2-exp(x)); e.g.f. of column k>0: 1/(1-Sum_{j>=k} x^j/j!) - 1/(1-Sum_{j>=k+1} x^j/j!).

T(n,k) = A245732(n,k) - A245732(n,k+1).