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.

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

Alois P. Heinz, Antidiagonals n = 0..36, flattened

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.

Main diagonal gives: A000166.

Cf. A259784.

Sequence in context: A174695 A337622 A165577 * A344649 A337620 A318515

Adjacent sequences: A259773 A259774 A259775 * A259777 A259778 A259779

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 05 2015

Status

approved