|
| |
|
|
A238888
|
|
Number A(n,k) of self-inverse permutations p on [n] with displacement of elements restricted by k: |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.
|
|
10
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4, 5, 1, 1, 1, 2, 4, 8, 8, 1, 1, 1, 2, 4, 10, 15, 13, 1, 1, 1, 2, 4, 10, 22, 29, 21, 1, 1, 1, 2, 4, 10, 26, 48, 56, 34, 1, 1, 1, 2, 4, 10, 26, 66, 103, 108, 55, 1, 1, 1, 2, 4, 10, 26, 76, 158, 225, 208, 89, 1, 1, 1, 2, 4, 10, 26, 76, 206, 376, 492, 401, 144, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,9
|
|
|
COMMENTS
|
A(n,k) is exactly the number of matchings of the k-th power of the path on n vertices. Here is A(4,1): o o o o (1234); o o o--o (1243); o o--o o (1324); o--o o o (2134); o--o o--o (2143). - Pietro Codara, Feb 17 2015
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} A238889(n,i).
|
|
|
EXAMPLE
|
A(4,0) = 1: 1234.
A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(4,2) = 8: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412.
A(4,3) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 2, 2, 2, 2, 2, 2, 2, ...
1, 3, 4, 4, 4, 4, 4, 4, 4, ...
1, 5, 8, 10, 10, 10, 10, 10, 10, ...
1, 8, 15, 22, 26, 26, 26, 26, 26, ...
1, 13, 29, 48, 66, 76, 76, 76, 76, ...
1, 21, 56, 103, 158, 206, 232, 232, 232, ...
1, 34, 108, 225, 376, 546, 688, 764, 764, ...
|
|
|
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>n, A(n, n), b(n, k, {})):
seq(seq(A(n, d-n), n=0..d), d=0..12);
|
|
|
MATHEMATICA
|
b[n_, k_, s_] := 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>n, A[n, n], b[n, k, {}]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Mar 12 2014, translated from Maple *)
|
|
|
CROSSREFS
|
Columns k=0-10 give: A000012, A000045(n+1), A000078(n+3), A239075, A239076, A239077, A239078, A239079, A239080, A239081, A239082.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
