0,3

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)

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

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 having 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.

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

James N. Brawner, Dinner, Dancing and Tennis, Anyone?, Mathematics Magazine, Vol. 73, No 1 (2000).

R. Bricard, L'Interm\'{e}diaire des Math\'{e}maticiens, 8 (1901), 312-313.

M. A. Brodie, Avoiding your spouse at a party leads to war, Math. Mag., 75 (2002), 203-208.

B. H. Margolius, Avoiding your spouse at a bridge party, Math. Mag., 74 (2001), 33-41.

B. H. Margolius, The dinner-diner matching problem, Math. Mag., 76 (2003), 107-118.

T. D. Noe, Table of n, a(n) for n=0..100

Barbara H. Margolius, Dinner-Diner Matching Probabilities

E.g.f.: 1/(exp(x)*sqrt(1-2x)).

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

(PARI) a(n)=(-1)^(n+1)*sum(k=0, n, (-1)^k*binomial(n, k)*prod(i=0, k, 2*i-1))

a(n)=A054479(n)/A001147(n). Cf. A001818, A000166, A001499.

Sequence in context: A132186 A027278 A001415 this_sequence A052622 A001188 A113145

Adjacent sequences: A053868 A053869 A053870 this_sequence A053872 A053873 A053874

nonn,nice,easy

Cris Moore (moore(AT)santafe.edu), Mar 29 2000; Christian G. Bower (bowerc(AT)usa.net), Mar 29 2000

More terms from James A. Sellers (sellersj(AT)math.psu.edu), Apr 08 2000