login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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: A272728 A174695 A165577 * A116422 A130161 A115672

Adjacent sequences:  A259773 A259774 A259775 * A259777 A259778 A259779

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 05 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 12 16:38 EST 2017. Contains 295949 sequences.