login
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
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
From Vaclav Kotesovec, Jul 07 2015: (Start) For k > 1, A(n,k) ~ c(k) * d(k)^n
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
Main diagonal gives: A000166.
Cf. A259784.
Sequence in context: A174695 A337622 A165577 * A344649 A337620 A318515
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 05 2015
STATUS
approved