# Counting Couples

A group of m men and w women randomly sit in a single row at a theater. If a man and woman are seated next to each other, they form a "couple." "Couples" can overlap, which means one person can be a member of two "couples."

Question: What is the expected number of couples?

Comment: I have a hard time with word problems that deal with "expectations".

• Please explain What do u mean by expected number of couples? there may be as less as 1 or as many as $2m \space or\space 2w$ depending which is less. Do u want max. and min. – ABC Mar 21 '13 at 14:19
• @exploringnet: No, the OP wants the expected value of the random variable $X(\omega)$ giving the number of couples in seating $\omega$, where $\omega$ ranges over all $(m+w)!$ seatings. – Brian M. Scott Mar 21 '13 at 14:31

Consider a woman. If she’s sitting at one end of the row, there are $m(m+w-2)!$ permutations in which she is part of a couple. Otherwise, there are $m(m-1)(m+w-3)!$ permutations in which she is part of two couples and $2m(w-1)(m+w-3)!$ permutations in which she is part of one couple. There are $(m+w-1)!$ permutations with her in that seat, so the expected number of couples containing a randomly chosen woman is

$$\frac2{m+w}\cdot\frac{m(m+w-2)!}{(m+w-1)!}+\frac{m+w-2}{m+w}\cdot\frac{2m(m+w-3)!(m+w-2)}{(m+w-1)!}\;.$$

This simplifies to

$$\frac{2m(m+w-1)}{(m+w)(m+w-1)}=\frac{2m}{m+w}\;.$$

There are $w$ women, so by linearity of expectation the expected number of couples is

$$\frac{2mw}{m+w}\;.$$

(As a partial check against obvious errors, notice that this expression is unchanged if we interchange the rôles of $m$ and $w$, as it obviously should be.)

Let $n=m+w$. Let $X$ be the number of couples, a random variable. Let Irma be one of the women and let Jack be one of the men. There are $n(n-1)$ ways that Irma and Jack can be seated, and there are $2(n-1)$ ways they can be seated next to each other. The probability that Irma and Jack are seated next to each other is $\frac{2(n-1)}{n(n-1}=\frac 2 n$, and this is the expected value of the indicator variable $X_{\text{Irma,Jack}}$ whose value is $1$ if Irma and Jack are seated next to each other, $0$ otherwise. Summing over all $mw$ potential couples, $E[X]=\frac{2mw}n=\frac{2mw}{m+w}$.

This problem may also be solved using generating functions. Let $p_{n,k}$ be the number of sequences of length $n$ with $k$ couples where the last person is male. Similarly, let $q_{n,k}$ be the number of sequences of length $n$ with $k$ couples where the last person is female.

This gives the following relations: $$p_{n,0} = u^n \\ q_{n,0} = v^n \\ p_{n,k} = u z \times q_{n-1,k-1} + u \times p_{n-1,k} \\ q_{n,k} = v z \times p_{n-1,k-1} + v \times q_{n-1,k}.$$ Here the variable $z$ represents the number of couples.

Now introduce $$P(z, u, v) = \sum_{n\ge 0} \sum_{k\ge 0} p_{n, k} \\ Q(z, u, v) = \sum_{n\ge 0} \sum_{k\ge 0} q_{n, k}.$$

Summing the recurrence relations, we find $$\sum_{n\ge 1} \sum_{k\ge 1} p_{n,k} = P - \sum_{k\ge 1} p_{0, k} - \sum_{n\ge 1} p_{n, 0} = P - \frac{u}{1-u} \\ = u z \times Q + u \times \left(P - \sum_{n\ge 0} p_{n, 0}\right) = u z \times Q + u \times \left(P - \frac{u}{1-u}\right)$$ and similarly $$\sum_{n\ge 1} \sum_{k\ge 1} q_{n,k} = Q - \sum_{k\ge 1} q_{0, k} - \sum_{n\ge 1} q_{n, 0} = Q - \frac{v}{1-v} \\ = v z \times P + v \times \left(Q - \sum_{n\ge 0} q_{n, 0}\right) = v z \times P + v \times \left(Q - \frac{v}{1-v}\right).$$ Solving this system of equations, we obtain $$P = -{\frac { \left( vz-v+1 \right) u}{v-1-uv+u+u{z}^{2}v}} \quad \text{and} \quad Q = -{\frac {v \left( -u+1+uz \right) }{v-1-uv+u+u{z}^{2}v}},$$ so that $$P+Q = -{\frac {2\,uzv-2\,uv+u+v}{v-1-uv+u+u{z}^{2}v}}.$$ Now observe that $$\left.(P+Q)\right|_{z=1} = -{\frac {u+v}{v-1+u}} = \sum_{q\ge 1} (u+v)^q,$$ and $$[u^m v^w] \sum_{q\ge 1} (u+v)^q = \binom{m+w}{m}.$$ This is a nice sanity check, a kind of hash certificate that shows that we have the right generating function.

To conclude note that $$\left.\left(\frac{d}{dz} (P+Q)\right)\right|_{z=1} = 2\,{\frac {uv}{ \left( v-1+u \right) ^{2}}}$$ so that $$[u^m v^w] 2 uv \sum_{q\ge 0} (q+1) (u+v)^q = 2 [u^{m-1} v^{w-1}] \sum_{q\ge 0} (q+1) (u+v)^q = 2 (m+w-1)\binom{m+w-2}{m-1}.$$ It follows that the expected number of couples $E[C]$ is $$E[C] = \frac{2 (m+w-1)\binom{m+w-2}{m-1}}{\binom{m+w}{m}} = \frac{2mw}{m+w}.$$ I do believe that this is a nice exercise in the use of ordinary generating functions including the sanity check (obviously the number of arrangements is $m+w$ choose $m$.) With these generating functions we can calculate arbitrary factorial moments of $C.$

Continuing the computation we can calculate $E[C(C-1)]$.

We have $$\left.\left(\left(\frac{d}{dz}\right)^2 (P+Q)\right)\right|_{z=1} = 2\,{\frac {uv \left( -2\,uv-u+{u}^{2}+{v}^{2}-v \right) }{ \left( v-1+u \right) ^{3}}}.$$ After a straightforward calculation this transforms into $$E[C(C-1)] = {\frac {2\,mw \,\left( 2\,mw-w-m \right) }{ \left( m+w-1 \right) \left( m+w \right) }}.$$