A245348 Number T(n,k) of endofunctions f on [n] that are self-inverse on [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 4, 3, 2, 27, 15, 8, 4, 256, 112, 50, 22, 10, 3125, 1125, 430, 166, 66, 26, 46656, 14256, 4752, 1626, 576, 206, 76, 823543, 218491, 64484, 19768, 6310, 2054, 688, 232, 16777216, 3932160, 1040384, 288512, 83736, 24952, 7660, 2388, 764

Offset

0,4

Comments

T(n,k) counts endofunctions f:{1,...,n}-> {1,...,n} with f(f(i))=i for all i in {1,...,k}.

Links

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

Formula

T(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i)*C(k,i)*i!*A000085(k-i)*n^(n-k-i).

Example

T(3,1) = 15: (1,1,1), (2,1,1), (3,1,1), (1,2,1), (3,2,1), (1,3,1), (3,3,1), (1,1,2), (2,1,2), (1,2,2), (1,3,2), (1,1,3), (2,1,3), (1,2,3), (1,3,3).
T(3,2) = 8: (2,1,1), (1,2,1), (3,2,1), (2,1,2), (1,2,2), (1,3,2), (2,1,3), (1,2,3).
T(3,3) = 4: (3,2,1), (1,3,2), (2,1,3), (1,2,3).
Triangle T(n,k) begins:
0 :       1;
1 :       1,      1;
2 :       4,      3,     2;
3 :      27,     15,     8,     4;
4 :     256,    112,    50,    22,   10;
5 :    3125,   1125,   430,   166,   66,   26;
6 :   46656,  14256,  4752,  1626,  576,  206,  76;
7 :  823543, 218491, 64484, 19768, 6310, 2054, 688, 232;
     ...

Maple

g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
T:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*
             g(k-i)*n^(n-k-i), i=0..min(k, n-k)):
seq(seq(T(n, k), k=0..n), n=0..10);

Mathematica

g[n_] := g[n] = If[n<2, 1, g[n-1] + (n-1)*g[n-2]]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-k, i]*Binomial[k, i]*i!*g[k-i]*n^(n-k-i), {i, 0, Min[k, n-k]}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

Crossrefs

Columns k=0-1 give: A000312, A089945(n-1) for n>0.

Main diagonal gives A000085.

T(2n,n) gives A245141.

Cf. A239771, A245692.

Sequence in context: A330778 A061312 A019130 * A174551 A349811 A239799

Adjacent sequences: A245345 A245346 A245347 * A245349 A245350 A245351

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 18 2014

Status

approved