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

Author

Alois P. Heinz, Jul 05 2015

Keywords

• nonn
• tabl

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)

Examples

			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, ...
		

Links

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

Crossrefs

Columns k=0-10 give: A000007, A059841, A033305, A079997, A259777, A259778, A259779, A259780, A259781, A259782, A259783.

Main diagonal gives: A000166.

Cf. A259784.

Programs

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 *)

Formula

A(n,k) = Sum_{j=0..k} A259784(n,j).