Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 12 down vote favorite
9

The Problem
$ab$ couples are sitting at $a$ tables with $2b$ seats each. Call a couple a "good" couple if they are seated at the same table.

(1) What is the probability that, in total, there are exactly $k$ "good" couples?

My Approach so Far
Recurrence Relations One possible approach is to set up a recurrence relation, with $p_{a,b,n}$ denoting the probability of having exactly $k$ "good" couples. However, the issue with this is to recurrence equation between $p_{a+1,b,k}$ and $p_{a,b,k}$ will not be simple as one will have to consider the different combinations of people on the additional table.
Principle of Inclusion and Exclusion Another possible approach is to use PIE. We denote $P_S$ as the probability that only the couples in $S$ are good. While $P_S$ for $|S|=1$ is easy ($P={b-1}/{ab}$), I'm not sure how to proceed.

share|improve this question
When $a=2$, $p_{2,b,k}$ is exactly $\binom{2b}{k} \big(\frac{1}{4}\big)^k\big(\frac{3}{4}\big)^{2b-k}$ (binomial law). – Ewan Delanoy Feb 13 at 8:05
This is incorrect. When $a=2$, the number of good couples must necessarily be even. Getting $p_{a,b,k}$ for small values of $a,b$ is relatively easy, the problem is how to generalise this. – Ivan Loh Feb 13 at 9:00
1  
A reformulation might be to take a random permutation of $1,\ldots,2ab$ and compute the probability that, if $n$ is even, the positions of $n$ and $n+1$ are congruent mod $2b$. – Alexander Gruber♦ Feb 16 at 18:15
@Alexander: But that part is easy; what makes this question difficult is that it asks for the probability of there being exactly $k$ good couples, not just for the probability of a given couple being good. – joriki Feb 18 at 19:33
1  
@SeanBallentine I don't think there's a general way to express what you require. However, given $k$ distinct objects to be placed in $n$ distinct slots, each with a capacity of $b$, where the ordering within each slot is not important, what we need to find is the coefficient of $x^k$ in $$\left(\sum^{b}_{i=0} \frac {x^{i}}{i!}\right)^n$$ This can be converted into a recurrence relation, where, if the desired quantity is denoted as $C(n,k)$ for given $b$, the recurrence is $$C(n,k)=\sum^{b}_{i=0} \frac {C(n-1,k-i)}{i!}$$ – Vincent Tjeng Feb 21 at 3:17
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.