A004306 Rook polynomials. (Formerly M1670)

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,3

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).

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

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 *)

Prog

(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
(Magma) R<x>:=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
(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

Crossrefs

Cf. A000803. 4th column of A008305.

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

Sequence in context: A090755 A192196 A000496 * A092485 A113904 A099144

Adjacent sequences: A004303 A004304 A004305 * A004307 A004308 A004309

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved