A004306 Rook polynomials.

1, 1, 2, 6, 24, 44, 80, 144, 264, 484, 888, 1632, 3000, 5516, 10144, 18656, 34312, 63108, 116072, 213488, 392664, 722220, 1328368, 2443248, 4493832, 8265444, 15202520, 27961792, 51429752, 94594060, 173985600, 320009408, 588589064, 1082584068, 1991182536

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n) is the number of perfect matchings in the circulant graph with 2*n vertices with jumps 1 and 3. - Robert Israel, Jan 24 2019

References

• D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..400
• N. Metropolis, M. L. Stein, and P. R. Stein, Permanents of cyclic (0,1) matrices, Journal of Combinatorial Theory, Volume 7, Issue 4, December 1969, Pages 291-321.
• Earl Glen Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. Ser. A 28 (1979), no. 3, 369-377.
• Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Crossrefs

Cf. A000803. 4th column of A008305.

Equals 2 * (A001644(n) + 1), n>3.

Programs

Magma

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x+ 2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1-2*x+x^4) )); // G. C. Greubel, Apr 22 2019

Mathematica

Join[{1,1,2,6},LinearRecurrence[{2,0,0,-1},{24,44,80,144},40]] (* or *) CoefficientList[ Series[ (1-x+2x^3+13x^4- 3x^5- 6x^6- 10x^7)/ (1-2x+ x^4),{x,0,40}],x] (* Harvey P. Dale, Dec 13 2011 *)

PARI

my(x='x+O('x^40)); Vec((1-x+2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1 -2*x+x^4)) \\ G. C. Greubel, Apr 22 2019

Sage

((1-x+2*x^3+13*x^4-3*x^5-6*x^6-10*x^7)/(1-2*x+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

Formula

G.f.: (1 - x + 2*x^3 + 13*x^4 - 3*x^5 - 6*x^6 - 10*x^7)/(1 - 2*x + x^4).

a(n) = 2*a(n-1) - a(n-4); a(0)=1, a(1)=1, a(2)=2, a(3)=6, a(4)=24, a(5)=44, a(6)=80, a(7)=144. - Harvey P. Dale, Dec 13 2011