login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A238889 Number T(n,k) of self-inverse permutations p on [n] where the maximal displacement of an element equals k: k = max_{i=1..n} |p(i)-i|; triangle T(n,k), n>=0, 0<=k<=n, read by rows. 11
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 2, 0, 1, 7, 7, 7, 4, 0, 1, 12, 16, 19, 18, 10, 0, 1, 20, 35, 47, 55, 48, 26, 0, 1, 33, 74, 117, 151, 170, 142, 76, 0, 1, 54, 153, 284, 399, 515, 544, 438, 232, 0, 1, 88, 312, 675, 1061, 1471, 1826, 1846, 1452, 764, 0, 1, 143, 629, 1575, 2792, 4119, 5651, 6664, 6494, 5008, 2620, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

Main diagonal and lower diagonal give: A000007, A000085(n-1).

Columns k=0-10 give: A000012, A000071(n+1), A238913, A238914, A238915, A238916, A238917, A238918, A238919, A238920, A238921.

Row sums give A000085.

LINKS

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

FORMULA

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

EXAMPLE

T(4,0) = 1: 1234.

T(4,1) = 4: 1243, 1324, 2134, 2143.

T(4,2) = 3: 1432, 3214, 3412.

T(4,3) = 2: 4231, 4321.

Triangle T(n,k) begins:

00: 1;

01: 1,   0;

02: 1,   1,   0;

03: 1,   2,   1,   0;

04: 1,   4,   3,   2,    0;

05: 1,   7,   7,   7,    4,    0;

06: 1,  12,  16,  19,   18,   10,    0;

07: 1,  20,  35,  47,   55,   48,   26,    0;

08: 1,  33,  74, 117,  151,  170,  142,   76,    0;

09: 1,  54, 153, 284,  399,  515,  544,  438,  232,   0;

10: 1,  88, 312, 675, 1061, 1471, 1826, 1846, 1452, 764,  0;

...

The 26 involutions of 5 elements together with their maximal displacements are:

01:  [ 1 2 3 4 5 ]   0

02:  [ 1 2 3 5 4 ]   1

03:  [ 1 2 4 3 5 ]   1

04:  [ 1 2 5 4 3 ]   2

05:  [ 1 3 2 4 5 ]   1

06:  [ 1 3 2 5 4 ]   1

07:  [ 1 4 3 2 5 ]   2

08:  [ 1 4 5 2 3 ]   2

09:  [ 1 5 3 4 2 ]   3

10:  [ 1 5 4 3 2 ]   3

11:  [ 2 1 3 4 5 ]   1

12:  [ 2 1 3 5 4 ]   1

13:  [ 2 1 4 3 5 ]   1

14:  [ 2 1 5 4 3 ]   2

15:  [ 3 2 1 4 5 ]   2

16:  [ 3 2 1 5 4 ]   2

17:  [ 3 4 1 2 5 ]   2

18:  [ 3 5 1 4 2 ]   3

19:  [ 4 2 3 1 5 ]   3

20:  [ 4 2 5 1 3 ]   3

21:  [ 4 3 2 1 5 ]   3

22:  [ 4 5 3 1 2 ]   3

23:  [ 5 2 3 4 1 ]   4

24:  [ 5 2 4 3 1 ]   4

25:  [ 5 3 2 4 1 ]   4

26:  [ 5 4 3 2 1 ]   4

There is one involution with no displacements, 7 with one displacement, etc. giving row 4: [1, 7, 7, 7, 4, 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=max(1, n-k)..n-1)))

    end:

A:= (n, k)-> `if`(k<0, 0, b(n, k, {})):

T:= (n, k)-> A(n, k) -A(n, k-1):

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, DeleteCases[s, n]], b[n-1, k, s] + Sum[If[MemberQ[s, i], 0, b[n-1, k, s ~Union~ {i}]], {i, Max[1, n-k], n-1}]]]; A[n_, k_] := If[k<0, 0, b[n, k, {}]]; T[n_, k_] := A[n, k] - A[n, k-1]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 14}] // Flatten (* Jean-Fran├žois Alcover, Jan 08 2015, translated from Maple *)

CROSSREFS

Sequence in context: A088455 A004248 A034373 * A253628 A102728 A262495

Adjacent sequences:  A238886 A238887 A238888 * A238890 A238891 A238892

KEYWORD

nonn,tabl

AUTHOR

Joerg Arndt and Alois P. Heinz, Mar 06 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 April 27 04:48 EDT 2017. Contains 285507 sequences.