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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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 * A296207 A253628 A102728

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 19:49 EST 2019. Contains 319206 sequences. (Running on oeis4.)