A239145 Number T(n,k) of self-inverse permutations p on [n] where the minimal transposition distance equals k (k=0 for the identity permutation); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 13, 8, 3, 1, 0, 1, 39, 22, 10, 3, 1, 0, 1, 120, 65, 32, 10, 3, 1, 0, 1, 401, 208, 103, 37, 10, 3, 1, 0, 1, 1385, 703, 344, 136, 37, 10, 3, 1, 0, 1, 5069, 2517, 1206, 501, 151, 37, 10, 3, 1, 0, 1, 19170, 9390, 4421, 1890, 622, 151, 37, 10, 3, 1, 0

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Mar 11 2014

Keywords

• nonn
• tabl

Comments

Columns k=0 and k=1 respectively give A000012 and A000085(n)-A170941(n).

Row sums give A000085.

Diagonal T(2n,n) gives A005493(n-1) for n>0.

Reversed rows converge to A005493.

Examples

			T(4,0) = 1: 1234.
T(4,1) = 5: 1243, 1324, 2134, 2143, 4321.
T(4,2) = 3: 1432, 3214, 3412.
T(4,3) = 1: 4231.
Triangle T(n,k) begins:
00:   1;
01:   1,    0;
02:   1,    1,    0;
03:   1,    2,    1,    0;
04:   1,    5,    3,    1,   0;
05:   1,   13,    8,    3,   1,   0;
06:   1,   39,   22,   10,   3,   1,  0;
07:   1,  120,   65,   32,  10,   3,  1,  0;
08:   1,  401,  208,  103,  37,  10,  3,  1, 0;
09:   1, 1385,  703,  344, 136,  37, 10,  3, 1, 0;
10:   1, 5069, 2517, 1206, 501, 151, 37, 10, 3, 1, 0;
		

Links

• Joerg Arndt and Alois P. Heinz, Rows n = 0..30, flattened

Programs

Maple

b:= proc(n, k, s) option remember; `if`(n=0, 1, `if`(n in s,
      b(n-1, k, s minus {n}), b(n-1, k, s) +add(`if`(i in s, 0,
      b(n-1, k, s union {i})), i=1..n-k-1)))
    end:
T:= (n, k)-> `if`(k=0, 1, b(n, k-1, {})-b(n, k, {})):
seq(seq(T(n, k), k=0..n), n=0..14);

Mathematica

b[n_, k_, s_List] := b[n, k, s] = If[n == 0, 1, If[MemberQ[s, n], b[n-1, k, s ~Complement~ {n}], b[n-1, k, s] + Sum[If[MemberQ[s, i], 0, b[n-1, k, s ~Union~ {i}]], {i, 1, n - k - 1}]]] ; T[n_, k_] := If[k == 0, 1, b[n, k-1, {}] - b[n, k, {}]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 22 2015, after Maple *)

Formula

T(n,k) = A239144(n,k-1) - A239144(n,k) for k>0, T(n,0) = 1.