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

1, 0, 1, 1, 1, 2, 12, 7, 4, 4, 144, 62, 28, 12, 10, 2000, 695, 264, 100, 40, 26, 32400, 9504, 3126, 1050, 370, 130, 76, 605052, 154007, 44716, 13458, 4256, 1366, 456, 232, 12845056, 2891776, 751872, 204776, 58784, 17292, 5272, 1624, 764

Offset: 0

Author

Alois P. Heinz, Jul 29 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} and f(f(k+1))<>k+1 if k

Examples

			T(3,1) = 7: (1,1,1), (1,1,2), (1,1,3), (1,3,1), (1,3,3), (3,1,1), (3,3,1).
T(3,2) = 4: (1,2,1), (1,2,2), (2,1,1), (2,1,2).
T(3,3) = 4: (1,2,3), (1,3,2), (2,1,3), (3,2,1).
Triangle T(n,k) begins:
0 :       1;
1 :       0,      1;
2 :       1,      1,     2;
3 :      12,      7,     4,     4;
4 :     144,     62,    28,    12,   10;
5 :    2000,    695,   264,   100,   40,   26;
6 :   32400,   9504,  3126,  1050,  370,  130,  76;
7 :  605052, 154007, 44716, 13458, 4256, 1366, 456, 232;
     ...
		

Links

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

Crossrefs

Column k=0 gives A076728 for n>1.

Row sums give A000312.

Main diagonal gives A000085.

Cf. A245348, A245693 (the same for permutations).

Programs

Maple

g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
H:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*
             g(k-i)*n^(n-k-i), i=0..min(k, n-k)):
T:= (n, k)-> H(n, k) -H(n, k+1):
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]]; H[0, 0] = 1; H[n_, k_] := Sum[Binomial[n-k, i]*Binomial[k, i]*i!*g[k-i]*n^(n-k-i), {i, 0, Min[k, n-k]}]; T[n_, k_] := H[n, k] - H[n, k+1]; 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) = A245348(n,k) - A245348(n,k+1).

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.