A000271 - OEIS

%I M3020 N1222 #123 Sep 08 2022 08:44:27

%S 1,0,0,1,3,16,96,675,5413,48800,488592,5379333,64595975,840192288,

%T 11767626752,176574062535,2825965531593,48052401132800,

%U 865108807357216,16439727718351881,328839946389605643,6906458590966507696

%N Sums of ménage numbers.

%C 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

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

%C From _Vladimir Shevelev_, Jun 21 2015: (Start)

%C 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.

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

%C (End)

%D W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 2, p. 79.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 198.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.

%H Seiichi Manyama, <a href="/A000271/b000271.txt">Table of n, a(n) for n = 0..450</a> (terms 0..100 from T. D. Noe)

%H W. Ahrens, <a href="https://archive.org/stream/mathunterhaltung00ahrerich#page/n287/mode/2up">Mathematische Unterhaltungen und Spiele</a>, Leipzig: B. G. Teubner, 1901.

%H J. D. H. Dickson, <a href="http://plms.oxfordjournals.org/content/s1-10/1/120.extract">Discussion of two double series arising from the number of terms in determinants of certain forms</a>, Proc. London Math. Soc., 10 (1879), 120-122.

%H J. D. H. Dickson, <a href="/A002775/a002775.pdf">Discussion of two double series arising from the number of terms in determinants of certain forms</a>, Proc. London Math. Soc., 10 (1879), 120-122. [Annotated scanned copy]

%H Dmitry Efimov, <a href="https://arxiv.org/abs/1702.05655">Determinants of generalized binary band matrices</a>, arXiv:1702.05655 [math.RA], 2017.

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 222.

%H Y. Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Li2/li51.html">Ménage Numbers and Ménage Permutations</a>, J. Int. Seq. 18 (2015) 15.6.8

%H H. M. Taylor, <a href="/A000179/a000179.pdf">A problem on arrangements</a>, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]

%H M. Wyman and L. Moser, <a href="http://dx.doi.org/10.4153/CJM-1958-045-6">On the problème des ménages</a>, Canad. J. Math., 10 (1958), 468-480.

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

%F From _Paul Barry_, Feb 08 2009: (Start)

%F 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);

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

%F a(n) = (-1)^n*hypergeom([1, -n, n+1],[1/2],1/4). - _Mark van Hoeij_, Nov 12 2009

%F a(n) = round( 2*exp(-2)*(BesselK(1+n,2) + BesselK(n,2)) ) for n>0. - _Mark van Hoeij_, Nov 12 2009

%F a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n+k,2*k)*k!. - _Paul Barry_, Jun 23 2010

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

%F a(n) ~ exp(-2)*n!. - _Vaclav Kotesovec_, Mar 10 2014

%F a(-1 - n) = -a(n) for all n in Z. - _Michael Somos_, May 28 2014

%F a(n) = Sum_{i=3..n} A000179(i), n>=1. - _Vladimir Shevelev_, Jun 21 2015

%F 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

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

%p 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);

%t 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_ *)

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

%t Table[(-1)^n HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 20}] (* _Michael Somos_, May 28 2014 *)

%o (Magma) [ &+[(-1)^(n-k)*Binomial(n+k, 2*k)*Factorial(k): k in [0..n]]: n in [0..21]]; // _Bruno Berselli_, Apr 11 2011

%o (PARI) a(n) = if(n, round( 2*exp(-2)*(besselk(n+1,2) + besselk(n,2)) ), 1) \\ _Charles R Greathouse IV_, May 11 2016

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

%K nonn,easy,nice

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Aug 21 2000

%E More terms from _Simone Severini_, Oct 14 2004