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.

  • $\begingroup$ 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). $\endgroup$ Feb 13, 2013 at 8:05
  • $\begingroup$ 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. $\endgroup$
    – Ivan Loh
    Feb 13, 2013 at 9:00
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Alexander Gruber
    Feb 16, 2013 at 18:15
  • $\begingroup$ @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. $\endgroup$
    – joriki
    Feb 18, 2013 at 19:33
  • 2
    $\begingroup$ @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!}$$ $\endgroup$ Feb 21, 2013 at 3:17

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$ Nov 9, 2013 at 5:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .