login
Number of permutations p of [n] with no fixed points and cyclic displacement of elements restricted by two: p(i)<>i and (i-p(i) mod n <= 2 or p(i)-i mod n <= 2).
11

%I #25 Jul 15 2019 15:27:23

%S 1,0,1,2,9,44,80,144,260,448,808,1456,2640,4788,8744,16016,29444,

%T 54268,100304,185824,344996,641664,1195400,2230176,4165904,7790244,

%U 14581640,27316240,51209124,96060300,180291280,338538480,635940356,1195021888,2246289704

%N Number of permutations p of [n] with no fixed points and cyclic displacement of elements restricted by two: p(i)<>i and (i-p(i) mod n <= 2 or p(i)-i mod n <= 2).

%C a(n) = A000166(n) for n <= 5.

%H Alois P. Heinz, <a href="/A260074/b260074.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,1,-1,-4,3,-1,2,1,-1).

%F G.f.: -(27*x^14 -13*x^13 -61*x^12 -4*x^11 -70*x^10 +50*x^9 +44*x^8 +10*x^7 +38*x^6 -24*x^5 -6*x^4 +2*x^3 -3*x^2 +3*x-1) / ((x-1) *(x+1) *(x^2+1) *(x^2+x-1) *(x^4-2*x^3+x^2-2*x+1)).

%e a(6) = 80: 214365, 214635, 215364, 215634, 231564, 231645, 234561, 234615, 235614, 235641, 241365, 241635, 245361, 245631, 261345, 261534, 264315, 264531, 265314, 265341, 312564, 312645, 314265, 314562, 315264, 315642, 341265, 341562, 342561, 342615, 345261, 345612, 361245, 361542, 362514, 362541, 364215, 364512, 365214, 365241, 512364, 512634, 514362, 514632, 531264, 531642, 532614, 532641, 534261, 534612, 541362, 541632, 542361, 542631, 561234, 561342, 562314, 562341, 564231, 564312, 612345, 612534, 614235, 614532, 615234, 615342, 631245, 631542, 632514, 632541, 634215, 634512, 635214, 635241, 641235, 641532, 642315, 642531, 645231, 645312.

%p gf:= -(27*x^14 -13*x^13 -61*x^12 -4*x^11 -70*x^10 +50*x^9 +44*x^8 +10*x^7 +38*x^6 -24*x^5 -6*x^4 +2*x^3 -3*x^2 +3*x-1) / ((x-1) *(x+1) *(x^2+1) *(x^2+x-1) *(x^4-2*x^3+x^2-2*x+1)):

%p a:= n-> coeff(series(gf, x, n+1), x, n):

%p seq(a(n), n=0..50);

%t LinearRecurrence[{3,-2,1,-1,-4,3,-1,2,1,-1},{1,0,1,2,9,44,80,144,260,448,808,1456,2640,4788,8744},50] (* _Harvey P. Dale_, Jul 15 2019 *)

%Y Cf. A000166, A000804, A260081, A260092, A260094, A260111, A260091, A260115, A257953, A260216.

%Y Cf. A033305.

%K nonn,easy

%O 0,4

%A _Alois P. Heinz_, Jul 14 2015