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

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]

Inverse binomial transform of the odd double factorials (A001147). [From David Callan (callan(AT)stat.wisc.edu), Aug 25 2009]

Contribution 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 n-a -> n for large n, the ratio a(n)/(2n-1)!! -> exp(-1/2) ~= .60653

We find a(n)/(2n-1)!! for n= 100, 200, 300, 400 ~=

.6050124904, .6057720290, .6060250088, .6061514604 (End)

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.

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]

Sequence in context: A162065 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