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,6

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

Links

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

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

Example

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;

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

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

Sequence in context: A240509 A344901 A330619 * A370374 A297866 A298133

Adjacent sequences: A245690 A245691 A245692 * A245694 A245695 A245696

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 29 2014

Status

approved