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

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.

Links

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

Formula

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

Example

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;

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

Crossrefs

Sequence in context: A351641 A291883 A361957 * A327127 A151824 A275514

Adjacent sequences: A239142 A239143 A239144 * A239146 A239147 A239148

Keyword

nonn,tabl

Author

Joerg Arndt and Alois P. Heinz, Mar 11 2014

Status

approved