login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; table; graph; refs; listen; history; text; internal format)
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
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt and Alois P. Heinz, Mar 11 2014
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)