|
|
A000271
|
|
Sums of ménage numbers.
(Formerly M3020 N1222)
|
|
19
|
|
|
1, 0, 0, 1, 3, 16, 96, 675, 5413, 48800, 488592, 5379333, 64595975, 840192288, 11767626752, 176574062535, 2825965531593, 48052401132800, 865108807357216, 16439727718351881, 328839946389605643, 6906458590966507696
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
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
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)
|
|
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
|
|
|
FORMULA
|
a(n) = (n - 1) a(n - 2) + (n - 1) a(n - 1) + a(n - 3).
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
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
|
|
EXAMPLE
|
G.f. = 1 + x^3 + 3*x^4 + 16*x^5 + 96*x^6 + 675*x^7 + 5413*x^8 + ...
|
|
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
|
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 *)
|
|
PROG
|
(Magma) [ &+[(-1)^(n-k)*Binomial(n+k, 2*k)*Factorial(k): k in [0..n]]: n in [0..21]]; // Bruno Berselli, Apr 11 2011
(PARI) a(n) = if(n, round( 2*exp(-2)*(besselk(n+1, 2) + besselk(n, 2)) ), 1) \\ Charles R Greathouse IV, May 11 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|