Take the 2-minute tour ×
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.

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 '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 '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 '13 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 '13 at 19:33
2  
@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 '13 at 3:17

1 Answer 1

up vote 1 down vote accepted

Recall: $a$ tables, $2b$ people at each table. Label the couples $1,\ldots,ab$. Define the event $C$ as follows: $$ C = \{\mbox{couples $1,\ldots,k$ are good and all others are bad}\}. $$ By symmetry, observe that $$ \mathbb{P}(\mbox{exactly $k$ good couples}) = \left(\begin{array}{c} ab \\ k \end{array}\right)\ \mathbb{P}(C). $$

We'll compute $\mathbb{P}(C)$ with an inclusion-exclusion argument.

Let $\pi_n$ be the probability that couples $1,\ldots,n$ are good (regardless of whether any other couple is good). Note that by symmetry again, $\pi_n$ is the probability that any particular set of $n$ couples are good. Define the events $A$ and $A_n$ as follows for $n=k+1,\ldots,ab$: \begin{eqnarray} A &=& \{\mbox{couples $1,\ldots,k$ are good} \} \\ A_n &=& \{\mbox{couples $1,\ldots,k$, and $n$ are good}\}. \end{eqnarray} Observe $$ C = A \setminus \bigcup_{i=k+1}^{ab} A_i. $$ Inclusion-exclusion: $$ \mathbb{P}(C) = \mathbb{P}(A) - \sum_{t=1}^{ab-k} \sum_{i_1,\ldots,i_t} (-1)^{t+1} \mathbb{P}(A_{i_1}\cap\cdots\cap A_{i_t}). $$ Again by symmetry, $\mathbb{P}(A_{i_1}\cap\cdots\cap A_{i_t})=\pi_{k+t}$, and there are $\left(\begin{array}{c}ab - k \\ t\end{array}\right)$ terms of this form in the sum above. Thus, we may write $$ \mathbb{P}(C) = \sum_{t=0}^{ab-k} (-1)^t\ \left(\begin{array}{c}ab - k \\ t\end{array}\right) \ \pi_{k+t}. $$ We can move on to computing $\pi_n$.

Let us count the number of ways in which each of the $2ab$ people can be assigned tables in which couples $1,\ldots,n$ are good. Suppose that among these $n$ couples, $n_1$ are seated at table 1, $n_2$ at table 2, $\ldots$, and $n_a$ are seated at table $a$. Thus, $n_1+\cdots +n_a = n$. There are $\left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)$ ways of choosing which of the $n$ couples sit at which table. There are $\left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right)$ ways to choose the tables at which the remaining $2ab-2n$ people sit. Thus, the total number of ways of assigning people to tables in such a way that couples $1,\ldots,n$ are good is $$ \sum_{n_1+\cdots+n_a=n} \ \left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)\ \left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right). $$ The total number of ways of assigning all $2ab$ people is just $\frac{(2ab)!}{(2b)!^a}$. Thus, $$ \pi_n = \frac{(2b)!^a}{(2ab)!} \sum_{n_1+\cdots+n_a=n} \ \left(\begin{array}{c}n \\ n_1,\ldots,n_a\end{array}\right)\ \left(\begin{array}{c}2ab-2n \\ 2b-2 n_1,\ldots,2b-2n_a\end{array}\right). $$ Alternatively, note that $\pi_n$ can be written $$ \pi_n = \frac{(2b)!^a \ n! \ (2ab - 2n)!}{(2ab)!} C_n $$ where $C_n$ is the coefficient of $X^n$ in the polynomial $$ \left(\sum_{i=0}^b \frac{1}{i! (2b - 2i)!} X^i\right)^a. $$

share|improve this answer
    
Hi Will - I read through your proof and think that it works! Will get a few other people to read through this to verify it before accepting it as the answer. –  Vincent Tjeng Nov 9 '13 at 5:31

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.