1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ABC Mar 21 '13 at 14:19
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 21 '13 at 14:31
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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