A000382 Restricted permutations.

6, 11, 20, 36, 65, 119, 218, 400, 735, 1351, 2484, 4568, 8401, 15451, 28418, 52268, 96135, 176819, 325220, 598172, 1100209, 2023599, 3721978, 6845784, 12591359, 23159119, 42596260, 78346736, 144102113, 265045107, 487493954

Offset: 4

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

The fourth column of A008305, divided by 4.

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 4..1000
• N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Crossrefs

Cf. A008305, A000496 divided by 4, A020992.

Programs

Maple

A000382:=-(-6+z+2*z**2+4*z**3+z**4)/(z-1)/(z**3+z**2+z-1); [Conjectured by Simon Plouffe in his 1992 dissertation.]
a:= n-> if n<4 then 0 elif n=4 then 6 else (Matrix([[11,7,4,2]]). Matrix(4, (i,j)-> if (i=j-1) then 1 elif j=1 then [2,0,0,-1][i] else 0 fi)^(n-2))[1,4] fi: seq(a(n), n=4..30); # Alois P. Heinz, Aug 26 2008

Mathematica

a[n_] := Which[n<4, 0, n == 4, 6, True, {11, 7, 4, 2}.MatrixPower[Table[Which[i == j-1, 1, j == 1, {2, 0, 0, -1}[[i]], True, 0], {i, 1, 4}, {j, 1, 4}], n-2] // Last]; Table[a[n], {n, 4, 27}] (* Jean-François Alcover, Mar 12 2014, after Alois P. Heinz *)

Formula

a(n) = a(n-1)+a(n-2)+a(n-3)-2 (conjectured).

Extensions

More terms from Vincenzo Librandi, Mar 14 2014