|
%I #158 Aug 31 2023 02:08:46
%S 1,0,2,8,60,544,6040,79008,1190672,20314880,387099936,8148296320,
%T 187778717632,4702248334848,127140703364480,3691602647581184,
%U 114562300528369920,3784124901630435328,132555364873399378432,4908221631901073295360,191549525877429961604096
%N a(0)=1; a(1)=0; a(n) = 2*(n-1)*(a(n-1) + a(n-2)).
%C 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 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 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 Also n!*a(n) = 2^n * c(n) where c(n) = A001499(n). 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 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). - _Emeric Deutsch_, Jan 23 2009
%C Inverse binomial transform of the odd double factorials (A001147). - _David Callan_, Aug 25 2009
%C From Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009: (Start)
%C The formula is given directly by the Principle of Inclusion and Exclusion.
%C 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.
%C Based on n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= 0.60653.
%C We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~= 0.6050124904, 0.6057720290, 0.6060250088, 0.6061514604. (End)
%C This 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) (seeing the constraint as circular by opposition to the linear A165968). - _Olivier Gérard_, Feb 08 2011
%C a(n) is the n-th central moment of a central chi-squared distribution (with 1 degree of freedom), i.e., a(n) = E[ (Y- E[Y] )^n ] = E[ (X^2 - 1 )^n ] where Y is chi-squared, X is std normal, X~N(0,1), and the expectation operator is E[]. - _David Fioramonti_, May 11 2016
%C Exponential self-convolution of a(n)/2^n gives subfactorials (A000166). - _Vladimir Reshetnikov_, Oct 09 2016
%C For n > 1, also the number of maximum matchings in the n-cocktail party graph. - _Eric W. Weisstein_, Jun 15 2017
%C Number of polygonal tiles with n sides with two exits per side and n edges connecting pairs of exits, with no edges between exits on the same side (cf. A289191, A289269 for nonisomorphic tiles under rotational and rotational and reflectional symmetries). - _Marko Riedel_, Jun 28 2017
%C Number of ways n people can hold hands (every hand is holding another hand) where no one is holding their own hand. - _Harry Richman_, Aug 29 2023
%D R. Bricard, L'Intermédiaire des Mathématiciens, 8 (1901), 312-313.
%H Michael De Vlieger, <a href="/A053871/b053871.txt">Table of n, a(n) for n = 0..404</a> (First 100 terms from _T. D. Noe_)
%H A. Ayyer, <a href="http://arxiv.org/abs/1106.1465">Determinants and Perfect Matchings</a>, arXiv:1106.1465 [math.CO], 2011.
%H Roland Bacher, <a href="https://doi.org/10.37236/2522">Counting Packings of Generic Subsets in Finite Groups</a>, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
%H Bela Bollobas, <a href="http://dx.doi.org/10.1016/0095-8956(78)90011-4">The number of 1-factors in 2k-connected graphs</a>, J. Combin. Theory Ser. B 25 (1978), no. 3, 363--366. MR0516268 (80m:05060) - _N. J. A. Sloane_, Mar 26 2012
%H James N. Brawner, <a href="http://www.jstor.org/stable/2691486">Dinner, Dancing and Tennis, Anyone?</a>, Mathematics Magazine, Vol. 73, No 1 (2000).
%H M. A. Brodie, <a href="http://www.jstor.org/stable/3219242">Avoiding your spouse at a party leads to war</a>, Math. Mag., 75 (2002), 203-208.
%H Davi B. Costa, Bogdan A. Dobrescu, and Patrick J. Fox, <a href="https://arxiv.org/abs/2001.11991">Chiral Abelian gauge theories with few fermions</a>, arXiv:2001.11991 [hep-ph], 2020.
%H Barbara H. Margolius, <a href="https://web.archive.org/web/20201128023513/http://academic.csuohio.edu/bmargolius/homepage/dinner/dinner/cardentry.htm">Dinner-Diner Matching Probabilities</a>
%H B. H. Margolius, <a href="http://www.jstor.org/stable/2691151">Avoiding your spouse at a bridge party</a>, Math. Mag., 74 (2001), 33-41.
%H B. H. Margolius, <a href="http://www.jstor.org/stable/3219303">The Dinner-Diner Matching Problem</a>, Mathematics Magazine, 76 (2003), 107-118.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CocktailPartyGraph.html">Cocktail Party Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentEdgeSet.html">Maximum Independent Edge Set</a>
%F a(n) = A054479(n)/A001147(n).
%F E.g.f.: 1/(exp(x)*sqrt(1-2x)).
%F a(n) = (-1)^n*Sum_(k=0..n} (-1)^k*C(n, k)*(2k-1)!!. - _Benoit Cloitre_, May 01 2003; corrected by _David Fioramonti_, May 17 2016
%F a(n) = Integral_{x>=0} (x-1)^n * (exp(-x/2)/sqrt(2*Pi*x)) dt. - _Paul Barry_, Apr 12 2010
%F Conjectured g.f.: 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
%F a(n) ~ 2^(n+1/2) * n^n / exp(n+1/2). - _Vaclav Kotesovec_, Mar 11 2014
%F G.f.: Sum_{k>=0} (2*k - 1)!!*x^k/(1 + x)^(k+1). - _Ilya Gutkovskiy_, Apr 12 2019
%F Conjecture: if m == n (mod q) for q odd, then (-1)^m*a(m) == (-1)^n*a(n) (mod q). - _Harry Richman_, Aug 29 2023
%p f:= gfun:-rectoproc({a(0) = 1, a(1) = 0, a(n) = 2*(n - 1)*(a(n - 1) + a(n - 2))},a(n),remember):
%p map(f, [$0..30]); # _Robert Israel_, May 10 2016
%t RecurrenceTable[{a[0]==1,a[1]==0,a[n]==2(n-1)(a[n-1]+a[n-2])}, a[n],{n,20}] (* _Harvey P. Dale_, Sep 15 2011 *)
%t 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 *)
%t Range[0, 20]! CoefficientList[Series[1/(Exp[x] Sqrt[1 - 2 x]), {x, 0, 20}], x] (* _Eric W. Weisstein_, Jun 15 2017 *)
%t Table[(-1)^n HypergeometricPFQ[{1/2, -n}, {}, 2], {n, 20}] (* _Eric W. Weisstein_, Jun 15 2017 *)
%t Table[I (-1)^n HypergeometricU[1/2, 3/2 + n, -1/2]/Sqrt[2], {n, 20}] (* _Eric W. Weisstein_, Dec 31 2017 *)
%o (PARI) a(n)=(-1)^(n+1)*sum(k=0,n,(-1)^k*binomial(n,k)*prod(i=0,k,2*i-1))
%o (Haskell)
%o a053871 n = a053871_list !! n
%o a053871_list = 1 : 0 : zipWith (*)
%o [2,4..] (zipWith (+) a053871_list $ tail a053871_list)
%o -- _Reinhard Zumkeller_, Mar 07 2012
%Y Cf. A054479, A001147, A001818, A000166, A001499.
%Y See A289191 for when rotational symmetries of the tiles are taken into account. - _Marko Riedel_, Jun 28 2017
%Y 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). - Lewis Mammel (l_mammel(AT)att.net), Oct 07 2009
%K nonn,nice,easy
%O 0,3
%A Cris Moore (moore(AT)santafe.edu) and _Christian G. Bower_, Mar 29 2000
%E More terms from _James A. Sellers_, Apr 08 2000
|
