A245693 Number T(n,k) of permutations 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, 0, 0, 2, 2, 0, 0, 4, 12, 2, 0, 0, 10, 72, 18, 4, 0, 0, 26, 480, 120, 36, 8, 0, 0, 76, 3600, 840, 264, 84, 20, 0, 0, 232, 30240, 6480, 1920, 648, 216, 52, 0, 0, 764, 282240, 55440, 15120, 4920, 1776, 612, 152, 0, 0, 2620, 2903040, 524160, 131040, 39600, 13920, 5232, 1848, 464, 0, 0, 9496

Offset: 0

Author

Alois P. Heinz, Jul 29 2014

Keywords

• nonn
• tabl

Comments

T(n,k) counts permutations p:{1,...,n}-> {1,...,n} with p(p(i))=i for all i in {1,...,k} and p(p(k+1))<>k+1 if k

Examples

			Triangle T(n,k) begins:
0 :      1;
1 :      0,    1;
2 :      0,    0,    2;
3 :      2,    0,    0,   4;
4 :     12,    2,    0,   0,  10;
5 :     72,   18,    4,   0,   0, 26;
6 :    480,  120,   36,   8,   0,  0, 76;
7 :   3600,  840,  264,  84,  20,  0,  0, 232;
8 :  30240, 6480, 1920, 648, 216, 52,  0,   0, 764;
		

Links

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

Crossrefs

Column k=0 give A062119(n-1) for n>1.

Row sums give A000142.

Main diagonal gives A000085.

Cf. A245692 (the same for endofunctions).

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-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[n_, k_] := Sum[Binomial[n - k, i]*Binomial[k, i]*i!*
     g[k - i]*(n - k - i)!, {i, 0, Min[k, n - k]}];
T[n_, k_] := H[n, k] - H[n, k + 1];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 10 2021, after Alois P. Heinz *)

Formula

T(n,k) = H(n,k) - H(n,k+1) with H(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i) * C(k,i) * i! * A000085(k-i) * (n-k-i)!.

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

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