|
| |
|
|
A259776
|
|
Number A(n,k) of permutations p of [n] with no fixed points and displacement of elements restricted by k: 1 <= |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.
|
|
11
|
|
|
|
1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 4, 0, 0, 1, 0, 1, 2, 9, 6, 1, 0, 1, 0, 1, 2, 9, 24, 13, 0, 0, 1, 0, 1, 2, 9, 44, 57, 24, 1, 0, 1, 0, 1, 2, 9, 44, 168, 140, 45, 0, 0, 1, 0, 1, 2, 9, 44, 265, 536, 376, 84, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,19
|
|
|
COMMENTS
|
Conjecture: Column k > 0 has a linear recurrence (with constant coefficients) of order = A005317(k) = (2^k + C(2*k,k))/2. - Vaclav Kotesovec, Jul 07 2015
k c(k) d(k)
2 0.2840509026895102746628049030651... 1.8832035059135258641689474653620...
3 0.1678494211968692989590951622212... 2.6304414743928951523517253855770...
4 0.0973070675347403976445165510589... 3.3758288741377846847522960161445...
5 0.0552389982575367440330445172521... 4.1183824671958029895499633437571...
6 0.0309726120341077011398575643793... 4.8588208495640240252838055706997...
7 0.0172064353582683268003622374813... 5.5979905586951369718393573797927...
8 0.0094902135663231445267663712259... 6.3363450921766600853069060904417...
9 0.00520430877801650454166967632... 7.0741444217884608367707985...
10 0.0028405987031922... 7.811548995086...
(End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
A(n,k) = Sum_{j=0..k} A259784(n,j).
|
|
|
EXAMPLE
|
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 1, 1, 1, 1, 1, ...
0, 0, 2, 2, 2, 2, 2, 2, ...
0, 1, 4, 9, 9, 9, 9, 9, ...
0, 0, 6, 24, 44, 44, 44, 44, ...
0, 1, 13, 57, 168, 265, 265, 265, ...
0, 0, 24, 140, 536, 1280, 1854, 1854, ...
|
|
|
MAPLE
|
b:= proc(n, s, k) option remember; `if`(n=0, 1, `if`(n+k in s,
b(n-1, (s minus {n+k}) union `if`(n-k>1, {n-k-1}, {}), k),
add(`if`(j=n, 0, b(n-1, (s minus {j}) union
`if`(n-k>1, {n-k-1}, {}), k)), j=s)))
end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, {$max(1, n-k)..n}, k)):
seq(seq(A(n, d-n), n=0..d), d=0..12);
|
|
|
MATHEMATICA
|
b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, Join[s ~Complement~ {n+k}] ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n -1, Join[s ~Complement~ {j}] ~Union~ If[n-k>1, {n-k-1}, {}], k]], {j, s}]] ];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 29 2017, translated from Maple *)
|
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A059841, A033305, A079997, A259777, A259778, A259779, A259780, A259781, A259782, A259783.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
