A239144 Number T(n,k) of self-inverse permutations p on [n] such that all transposition distances (if any) are larger than k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 10, 5, 2, 1, 1, 26, 13, 5, 2, 1, 1, 76, 37, 15, 5, 2, 1, 1, 232, 112, 47, 15, 5, 2, 1, 1, 764, 363, 155, 52, 15, 5, 2, 1, 1, 2620, 1235, 532, 188, 52, 15, 5, 2, 1, 1, 9496, 4427, 1910, 704, 203, 52, 15, 5, 2, 1, 1

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Mar 11 2014

Keywords

• nonn
• tabl

Comments

T(n,k) is defined for all n, k >= 0: T(n,k) = 1 for k >= n.

Columns k=0 and k=1 respectively give A000085 and A170941 (involutions on [n] without adjacent transpositions).

Diagonal T(2n,n) gives A000110(n).

Examples

			T(4,0) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
T(4,1) = 5: 1234, 1432, 3214, 3412, 4231.
T(4,2) = 2: 1234, 4231.
T(4,3) = 1: 1234.
Triangle T(n,k) begins:
00:      1;
01:      1,    1;
02:      2,    1,    1;
03:      4,    2,    1,   1;
04:     10,    5,    2,   1,   1;
05:     26,   13,    5,   2,   1,  1;
06:     76,   37,   15,   5,   2,  1,  1;
07:    232,  112,   47,  15,   5,  2,  1, 1;
08:    764,  363,  155,  52,  15,  5,  2, 1, 1;
09:   2620, 1235,  532, 188,  52, 15,  5, 2, 1, 1;
10:   9496, 4427, 1910, 704, 203, 52, 15, 5, 2, 1, 1;
		

Links

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

Crossrefs

Cf. A239145.

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)-> 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_] := b[n, k, {}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 19 2015, after Alois P. Heinz *)