login
This site is supported by donations 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: A263339 A244372 A119331 * A151824 A275514 A180782

Adjacent sequences:  A239142 A239143 A239144 * A239146 A239147 A239148

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 25 10:24 EDT 2017. Contains 287026 sequences.