login
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.
13

%I #29 Dec 16 2021 16:46:39

%S 1,0,1,1,2,1,14,12,0,1,181,68,6,0,1,2584,520,20,0,0,1,41973,4542,120,

%T 20,0,0,1,776250,46550,672,70,0,0,0,1,16231381,540136,5516,112,70,0,0,

%U 0,1,380333228,7045020,40140,1848,252,0,0,0,0,1

%N 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.

%C T(0,0) = 1 by convention.

%H Alois P. Heinz, <a href="/A245733/b245733.txt">Rows n = 0..140, flattened</a>

%F 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!).

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

%e T(2,0) = 1: (2,2).

%e T(2,1) = 2: (1,2), (2,1).

%e T(2,2) = 1: (1,1).

%e 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).

%e T(3,3) = 1: (1,1,1).

%e Triangle T(n,k) begins:

%e 0 : 1;

%e 1 : 0, 1;

%e 2 : 1, 2, 1;

%e 3 : 14, 12, 0, 1;

%e 4 : 181, 68, 6, 0, 1;

%e 5 : 2584, 520, 20, 0, 0, 1;

%e 6 : 41973, 4542, 120, 20, 0, 0, 1;

%e 7 : 776250, 46550, 672, 70, 0, 0, 0, 1;

%e 8 : 16231381, 540136, 5516, 112, 70, 0, 0, 0, 1;

%e ...

%p b:= proc(n, k) option remember; `if`(n=0, 1,

%p add(b(n-j, k)*binomial(n, j), j=k..n))

%p end:

%p g:= (n, k)-> `if`(k=0, n^n, `if`(n=0, 0, b(n, k))):

%p T:= (n, k)-> g(n, k) -g(n, k+1):

%p seq(seq(T(n, k), k=0..n), n=0..12);

%t 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_ *)

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

%Y Row sums give A000312.

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

%Y Cf. A245732.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Jul 30 2014