

A053871


a(0) = 1; a(1) = 0; a(n) = 2 (n  1)*(a(n  1) + a(n  2)).


16



1, 0, 2, 8, 60, 544, 6040, 79008, 1190672, 20314880, 387099936, 8148296320, 187778717632, 4702248334848, 127140703364480, 3691602647581184, 114562300528369920, 3784124901630435328, 132555364873399378432
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Number of deranged matchings of 2n people with partners (of either sex) other than their spouse. 2n objects are initially paired in some way and then are repaired so that no object is with its original partner (the dancing problem in the article).
Of interest in the "collision problem", where, given a 2to1 function f, we are asked for x, y such that f(x)=f(y).
2^n*n!*a(n) = (2n)! b(n) where b(n) are the probabilities that appear in Margolis (2001). One interpretation is in terms of matchings or 1factors of the complete graph on 2n vertices. The number of these is (2n)!/2^{n}n!. The number of 1factors being disjoint from (that is, having no edges in common with) a given 1factor is then a(n); and then b(n) is the probability of picking such a disjoint one factor at random.
Also n! a(n) = 2^{n} c(n) where c(n) = A001499. If we define d(n,k) = k(n1)(d(n1,k) + d(n2,k)), with d(0,k) = 1 and d(1,k) = 0, so d(n,1) are the derangement numbers A000166, then a(n) = d(n,2) (cf. A033030, A088991). On the other hand, taking d*(n,k) = d(n,k)/k^{n}, we have d*(n,k) = (n1)(d*(n1,k) + d*(n2,k)/k), with d*(0,k) = 1 and d*(1,k) = 0 and it is easy to see from Bricard's recurrence for c(n) that c(n)/n! satisfies this for k = 2.
A proof that the description in the first comment as "number of deranged matchings" implies the defining recursion relation: let (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) be the given pairs. In a deranged matching x_1 will be paired with any of the 2(n1) objects x_2, y_2, x_3, y_3, ..., x_n, y_n. It is sufficient to count only those deranged matchings in which x_1, is matched with x_2. They are of two kinds: (i) y_1 is not matched with y_2; their number is a(n1); (ii) y_1 is matched with y_2; their number is a(n2).  Emeric Deutsch, Jan 23 2009
Inverse binomial transform of the odd double factorials (A001147).  David Callan, Aug 25 2009
From Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)
The formula is given directly by the Principle of Inclusion and Exclusion.
The first term includes all pairings, the second term excludes all pairings containing each pair, the third term includes all pairings containing each pair of pairs, and so on.
Based on na > n for large n, the ratio a(n)/(2n1)!! > exp(1/2) ~= 0.60653.
We find a(n)/(2n1)!! for n= 100, 200, 300, 400 ~=
.6050124904, .6057720290, .6060250088, .6061514604 (End)
a(n) is a subset of the set of pairings of the first 2n integers (A001147) in another way: forbidding pairs of the form (2k,2k+1) for all k as well as the pair (1,2n) (seing the constraint as circular by opposition to the linear A165968).  Olivier Gérard, Feb 08 2011
a(n) is the nth central moment of a central chisquared distribution (with 1 degree of freedom), i.e., a(n) = E[ (Y E[Y] )^n ] = E[ (X^2  1 )^n ] where Y is chisquared, X is std normal, X~N(0,1), and the expectation operator is E[].  David Fioramonti, May 11 2016
Exponential selfconvolution of a(n)/2^n gives subfactorials (A000166).  Vladimir Reshetnikov, Oct 09 2016
For n > 1, also the number of maximum matchings in the ncocktail party graph.  Eric W. Weisstein, Jun 15 2017


REFERENCES

R. Bricard, L'Intermédiaire des Mathématiciens, 8 (1901), 312313.


LINKS

T. D. Noe, Table of n, a(n) for n = 0..100
A. Ayyer, Determinants and Perfect Matchings, arXiv:1106.1465 [math.CO], 2011.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.  From N. J. A. Sloane, Feb 06 2013
Bela Bollobas, The number of 1factors in 2kconnected graphs, J. Combin. Theory Ser. B 25 (1978), no. 3, 363366. MR0516268 (80m:05060)  N. J. A. Sloane, Mar 26 2012
James N. Brawner, Dinner, Dancing and Tennis, Anyone?, Mathematics Magazine, Vol. 73, No 1 (2000).
M. A. Brodie, Avoiding your spouse at a party leads to war, Math. Mag., 75 (2002), 203208.
Barbara H. Margolius, DinnerDiner Matching Probabilities
B. H. Margolius, Avoiding your spouse at a bridge party, Math. Mag., 74 (2001), 3341.
B. H. Margolius, The DinnerDiner Matching Problem, Mathematics Magazine, 76 (2003), 107118.
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set


FORMULA

a(n) = A054479(n)/A001147(n).
E.g.f.: 1/(exp(x)*sqrt(12x)).
a(n) = (1)^n*Sum_(k=0..n} (1)^k*C(n, k)*(2k1)!!.  Benoit Cloitre, May 01 2003; corrected by David Fioramonti, May 17 2016
a(n) = int((x1)^n exp(x/2)/sqrt(2*Pi*x),x,0,infty).  Paul Barry, Apr 12 2010
G.f.: conjecture: T(0)/(1+x), where T(k) = 1  x*(k+1)/(x*(k+1)  (1+x)/T(k+1) ); (continued fraction).  Sergei N. Gladkovskii, Nov 13 2013
a(n) ~ 2^(n+1/2) * n^n / exp(n+1/2).  Vaclav Kotesovec, Mar 11 2014


MAPLE

f:= gfun:rectoproc({a(0) = 1, a(1) = 0, a(n) = 2*(n  1)*(a(n  1) + a(n  2))}, a(n), remember):
map(f, [$0..30]); # Robert Israel, May 10 2016


MATHEMATICA

RecurrenceTable[{a[0]==1, a[1]==0, a[n]==2(n1)(a[n1]+a[n2])}, a[n], {n, 20}] (* Harvey P. Dale, Sep 15 2011 *)
CoefficientList[Assuming[{Element[x, Reals], x>0}, Series[Sqrt[Pi/2] * (I + Erfi[Sqrt[(1+1/x)/2]]) / (E^((1+x)/(2*x)) * Sqrt[x*(x+1)]), {x, 0, 20}]], x] (* Vaclav Kotesovec, Feb 15 2015 *)
Range[0, 20]! CoefficientList[Series[1/(Exp[x] Sqrt[1  2 x]), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 15 2017 *)
Table[(1)^n HypergeometricPFQ[{1/2, n}, {}, 2], {n, 20}] (* Eric W. Weisstein, Jun 15 2017 *)


PROG

(PARI) a(n)=(1)^(n+1)*sum(k=0, n, (1)^k*binomial(n, k)*prod(i=0, k, 2*i1))
(Haskell)
a053871 n = a053871_list !! n
a053871_list = 1 : 0 : zipWith (*)
[2, 4..] (zipWith (+) a053871_list $ tail a053871_list)
 Reinhard Zumkeller, Mar 07 2012


CROSSREFS

Cf. A054479, A001147, A001818, A000166, A001499.
Cf. A165968, number of pairings of 2n things disjoint to a given pairing, and containing a given pair not in the given pairing. It is given by a(n)/(2n2).  Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009
Sequence in context: A196076 A027278 A001415 * A208124 A052622 A001188
Adjacent sequences: A053868 A053869 A053870 * A053872 A053873 A053874


KEYWORD

nonn,nice,easy,changed


AUTHOR

Cris Moore (moore(AT)santafe.edu) and Christian G. Bower, Mar 29 2000


EXTENSIONS

More terms from James A. Sellers, Apr 08 2000


STATUS

approved



