A000271 Sums of ménage numbers.

1, 0, 0, 1, 3, 16, 96, 675, 5413, 48800, 488592, 5379333, 64595975, 840192288, 11767626752, 176574062535, 2825965531593, 48052401132800, 865108807357216, 16439727718351881, 328839946389605643, 6906458590966507696

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Permanent of the (0,1)-matrix having (i,j)-th entry equal to 0 iff this is on the diagonal or the first upper-diagonal. - Simone Severini, Oct 14 2004

Equivalently, number of permutations p of {1,2,...,n} such that p(i)-i not in {0,1}. - Andrew Howroyd, Sep 19 2017

From Vladimir Shevelev, Jun 21 2015: (Start)

Let 2*n!*V(n)=A137886(n) be the number of ways of seating n married couples at 2*n chairs arranged side-by-side in a straight line, men and women in alternate positions, so that no husband is next to his wife.

It is known [Riordan, Ch. 8, Th. 1, t=0] that, if 2*n!*U(n) is a solution of an analogous problem at a circular table, then U(n) = V(n) - V(n-1), n>=3, where U(n) = A000179(n). Thus V(n) = Sum_{i=3,...,n} A000179(i), n>=1, and comparing the initial conditions, we conclude that a(n) = V(n), n>=1. This gives a combinatorial interpretation for 2*n!*a(n).

(End)

Examples

			G.f. = 1 + x^3 + 3*x^4 + 16*x^5 + 96*x^6 + 675*x^7 + 5413*x^8 + ...
		

References

• W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 2, p. 79.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.
• 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).
• H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..100 from T. D. Noe)
• W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.
• J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122.
• J. D. H. Dickson, Discussion of two double series arising from the number of terms in determinants of certain forms, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]
• Dmitry Efimov, Determinants of generalized binary band matrices, arXiv:1702.05655 [math.RA], 2017.
• V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 222.
• Y. Li, Ménage Numbers and Ménage Permutations, J. Int. Seq. 18 (2015) 15.6.8
• H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]
• M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

Crossrefs

Cf. A000179, A000904, A001883, A137886, A292574. A diagonal of A058057.

Programs

Magma

[ &+[(-1)^(n-k)*Binomial(n+k, 2*k)*Factorial(k): k in [0..n]]: n in [0..21]]; // Bruno Berselli, Apr 11 2011

Maple

V := proc(n) local k; add( binomial(2*n-k,k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r,s) coeff( V(r),x,s ); end; A000271 := n->W(n-2,0);

Mathematica

Table[Sum[(-1)^(n - k) k! Binomial[n + k, 2 k], {k, 0, n}], {n, 0, 22}] (* Jean-François Alcover, Apr 11 2011, after Paul Barry *)
RecurrenceTable[{a[0] == 1, a[1] == a[2] == 0, a[n] == (n - 1) a[n - 2] + (n - 1) a[n - 1] +  a[n - 3]}, a, {n, 30}] (* Harvey P. Dale, Jun 01 2012 *)
Table[(-1)^n HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 20}] (* Michael Somos, May 28 2014 *)

PARI

a(n) = if(n, round( 2*exp(-2)*(besselk(n+1,2) + besselk(n,2)) ), 1) \\ Charles R Greathouse IV, May 11 2016

Formula

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

From Paul Barry, Feb 08 2009: (Start)

G.f.: 1/(1+x-x/(1+x-x/(1+x-2x/(1+x-2x/(1+x-3x/(1+x-3x/(1+x-4x/(1+... (continued fraction);

a(n) = Sum_{k=0..n} binomial(2n-k,k)*(n-k)!*(-1)^k. (End)

a(n) = (-1)^n*hypergeom([1, -n, n+1],[1/2],1/4). - Mark van Hoeij, Nov 12 2009

a(n) = round( 2*exp(-2)*(BesselK(1+n,2) + BesselK(n,2)) ) for n>0. - Mark van Hoeij, Nov 12 2009

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k,2*k)*k!. - Paul Barry, Jun 23 2010

G.f.: Sum_{n>=0} n!*x^n/(1+x)^(2*n+1). - Ira M. Gessel, Jan 15 2013

a(n) ~ exp(-2)*n!. - Vaclav Kotesovec, Mar 10 2014

a(-1 - n) = -a(n) for all n in Z. - Michael Somos, May 28 2014

a(n) = Sum_{i=3..n} A000179(i), n>=1. - Vladimir Shevelev, Jun 21 2015

0 = a(n)*(-a(n+2) - a(n+3)) + a(n+1)*(+a(n+1) + 2*a(n+2) + a(n+3) - a(n+4)) + a(n+2)*(+a(n+2) + 2*a(n+3) - a(n+4)) + a(n+3)*(+a(n+3)) for all n in Z. - Michael Somos, Oct 16 2016

Extensions

More terms from James Sellers, Aug 21 2000

More terms from Simone Severini, Oct 14 2004