A238915 Number of self-inverse permutations p on [n] where the maximal displacement of an element equals 4.

0, 0, 0, 0, 0, 4, 18, 55, 151, 399, 1061, 2792, 7252, 18572, 47051, 118291, 295718, 735776, 1823183, 4501151, 11077398, 27187053, 66567357, 162655518, 396728446, 966109074, 2349342360, 5705883591, 13842565488, 33549053111, 81238182806, 196560818348

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Mar 07 2014

Keywords

• nonn

Examples

			a(5) = 4: 52341, 52431, 53241, 54321.
a(6) = 18: 163452, 163542, 164352, 165432, 361452, 361542, 463152, 465132, 523416, 523614, 524316, 526413, 532416, 532614, 543216, 546213, 563412, 564312.
a(7) = 55: 1274563, 1274653, 1275463, ..., 5637124, 5643127, 5674123.
		

Links

• Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3, 0, -3, 1, 2, -7, -16, -7, -21, -12, -9, 1, 16, 7, 11, 0, 3, 2, 1, 1, -2, -1, -1).

Crossrefs

Column k=4 of A238889.

Programs

Maple

gf:= (x^12 -x^9 -x^8 +2*x^7 -x^6 +3*x^5 -4*x^4 -2*x^3 +x^2 +6*x +4)*x^5 /
     ((x+1)*(x^6 -x^5 +x^4 -3*x^3 +3*x^2 -3*x+1) *(x^16 +x^15 +2*x^14 +x^13 +x^12 +2*x^11 +x^10 +3*x^9 -4*x^8 -5*x^7 -9*x^6 -6*x^5 -x^4 -x^3 -2*x^2 -x+1)):
a:= n-> coeff(series(gf, x, n+1), x, n):
seq(a(n), n=0..40);

Mathematica

CoefficientList[Series[(x^12 - x^9 - x^8 + 2 x^7 - x^6 + 3 x^5 - 4 x^4 - 2 x^3 + x^2 + 6 x + 4) x^5/((x + 1) (x^6 - x^5 + x^4 - 3 x^3 + 3 x^2 - 3 x + 1) (x^16 + x^15 + 2 x^14 + x^13 + x^12 + 2 x^11 + x^10 + 3 x^9 - 4 x^8 - 5 x^7 - 9 x^6 - 6 x^5 - x^4 - x^3 - 2 x^2 - x + 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 09 2014 *)
LinearRecurrence[{3,0,-3,1,2,-7,-16,-7,-21,-12,-9,1,16,7,11,0,3,2,1,1,-2,-1,-1},{0,0,0,0,0,4,18,55,151,399,1061,2792,7252,18572,47051,118291,295718,735776,1823183,4501151,11077398,27187053,66567357},40] (* Harvey P. Dale, Mar 09 2023 *)

Formula

G.f.: (x^12 -x^9 -x^8 +2*x^7 -x^6 +3*x^5 -4*x^4 -2*x^3 +x^2 +6*x +4)*x^5 / ((x+1)*(x^6 -x^5 +x^4 -3*x^3 +3*x^2 -3*x+1) *(x^16 +x^15 +2*x^14 +x^13 +x^12 +2*x^11 +x^10 +3*x^9 -4*x^8 -5*x^7 -9*x^6 -6*x^5 -x^4 -x^3 -2*x^2 -x+1)).