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

Author

Alois P. Heinz, Jul 18 2014

Keywords

• nonn
• tabl

Comments

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

Examples

			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;
     ...
		

Links

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

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.

Programs

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 *)

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