%I A053871
%S A053871 1,0,2,8,60,544,6040,79008,1190672,20314880,387099936,8148296320,
%T A053871 187778717632,4702248334848,127140703364480,3691602647581184,
%U A053871 114562300528369920,3784124901630435328,132555364873399378432
%N A053871 a(0) = 1; a(1) = 0; a(n) = 2 (n - 1)*(a(n - 1) + a(n - 2)).
%C A053871 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 re-paired so that no object is with its original 
               partner (the dancing problem in the article)
%C A053871 Of interest in the "collision problem", where, given a 2-to-1 function 
               f, we are asked for x, y such that f(x)=f(y).
%C A053871 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 
               1-factors of the complete graph on 2n vertices. The number of these 
               is (2n)!/2^{n}n!. The number of 1-factors being disjoint from (that 
               is, having no edges in common with) a given 1-factor is then a(n); 
               and then b(n) is the probability of picking such a disjoint one factor 
               at random.
%C A053871 Also n! a(n) = 2^{n} c(n) where c(n) = A001499. If we define d(n,k) = 
               k(n-1)(d(n-1,k) + d(n-2,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) = (n-1)(d*(n-1,k) + d*(n-2,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
%C A053871 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(n-1) 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(n-1); (ii) y_1 
               is matched with y_2; their number is a(n-2). [From Emeric Deutsch 
               (deutsch(AT)duke.poly.edu), Jan 23 2009]
%C A053871 Inverse binomial transform of the odd double factorials (A001147). [From 
               David Callan (callan(AT)stat.wisc.edu), Aug 25 2009]
%C A053871 Contribution from Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)
%C A053871 The formula is given directly by the Principle of Inclusion and Exclusion.
%C A053871 The first term includes all pairings, the second term excludes
%C A053871 all pairings containing each pair, the third term includes all pairings
%C A053871 containing each pair of pairs, and so on.
%C A053871 Based on n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= 
               .60653
%C A053871 We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~=
%C A053871 .6050124904, .6057720290, .6060250088, .6061514604 (End)
%D A053871 James N. Brawner, Dinner, Dancing and Tennis, Anyone?, Mathematics Magazine, 
               Vol. 73, No 1 (2000).
%D A053871 R. Bricard, L'Interm\'{e}diaire des Math\'{e}maticiens, 8 (1901), 312-313.
%D A053871 M. A. Brodie, Avoiding your spouse at a party leads to war, Math. Mag., 
               75 (2002), 203-208.
%D A053871 B. H. Margolius, Avoiding your spouse at a bridge party, Math. Mag., 
               74 (2001), 33-41.
%D A053871 B. H. Margolius, The dinner-diner matching problem, Math. Mag., 76 (2003), 
               107-118.
%H A053871 T. D. Noe, <a href="b053871.txt">Table of n, a(n) for n=0..100</a>
%H A053871 Barbara H. Margolius, <a href="http://academic.csuohio.edu/bmargolius/
               homepage/dinner/dinner/cardentry.htm">Dinner-Diner Matching Probabilities</
               a>
%F A053871 E.g.f.: 1/(exp(x)*sqrt(1-2x)).
%F A053871 a(n)=(-1)^(n+1)*sum(k=0, n, (-1)^k*C(n, k)*(2k-1)!!) - Benoit Cloitre 
               (benoit7848c(AT)orange.fr), May 01 2003
%o A053871 (PARI) a(n)=(-1)^(n+1)*sum(k=0,n,(-1)^k*binomial(n,k)*prod(i=0,k,2*i-1))
%Y A053871 a(n)=A054479(n)/A001147(n). Cf. A001818, A000166, A001499.
%Y A053871 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)/(2n-2). [From Lewis Mammel (l_mammel(AT)att.net), Oct 07 
               2009]
%Y A053871 Sequence in context: A162065 A027278 A001415 this_sequence A052622 A001188 
               A113145
%Y A053871 Adjacent sequences: A053868 A053869 A053870 this_sequence A053872 A053873 
               A053874
%K A053871 nonn,nice,easy
%O A053871 0,3
%A A053871 Cris Moore (moore(AT)santafe.edu), Mar 29 2000; Christian G. Bower (bowerc(AT)usa.net), 
               Mar 29 2000
%E A053871 More terms from James A. Sellers (sellersj(AT)math.psu.edu), Apr 08 2000