19
$\begingroup$

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.

  • 0
    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).2013-02-13
  • 0
    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.2013-02-13
  • 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$.2013-02-16
  • 0
    @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.2013-02-18
  • 0
    @joriki Sure - I was just pointing out that this could be viewed as a permutation problem, which could be helpful. I don't have an answer for that part.2013-02-18
  • 0
    I was thinking about this problem in class today and I realized I don't know the answer to a much simpler problem that seems to be an obvious first step. You could take the number of ways of choosing k couples times the number of ways of placing k couples randomly among the tables and then time the number of ways of seating the rest of them such that no couple sits at the same table. Even though the last part seems hard to solve I am more interested in the middle part. How many ways can you place k things in a slots when the slots have capacity b?2013-02-20
  • 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!}$$2013-02-21
  • 0
    Reposted at http://mathoverflow.net/questions/127864/number-of-couples-sitting-at-same-table2013-04-18
  • 0
    just a comment - that "tjeng" is not me, and I'm not sure who it is! I am http://mathoverflow.net/users/23976/vincent-tjeng on mathoverflow2013-04-18
  • 0
    Why was this question deleted at mathoverflow? I believe I have an "answer", although it involves a bunch of sums of the form $\sum_{k_1+\cdots+k_a=k} f(k_1,\ldots,k_a)$. In my opinion, it's better than nothing, and perhaps a point of departure for improvement.2013-10-29

1 Answers 1

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

  • 0
    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.2013-11-09