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!)
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).
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: A369324 A004248 A034373 * A296207 A253628 A102728
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)