|
| |
|
|
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.
|
|
3
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
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).
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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;
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
