A 3-part combinatorics question with varying conditions

102 Views Asked by At

I am not entirely sure about my approach to these questions (especially b) and I wanted to get some opinions:

a) There are $m$ identical-looking men (indistinguishable/ treated as not distinct elements, $m>=10$) in an elevator. At each of floors $2$ through $11$, at least one man leaves the elevator (not in an ordered line = the order in which they exit in each floor does not matter & We don't know whether all have left by the time the elevator reaches floor $11$). How many ways is it possible for these $m$ identical-looking men to exit the elevator according to these conditions?

b) What happens if this time men are distinguishable/distinct (it matters which men get off on which floor) and you notice that all men have emptied the elevator by floor $11$. How many ways is it possible for them to empty out of the elevator, again not in an ordered line (at least one man leaves the elevator on every floor, $m$ still $>=10$)?

c) Now, what happens if men are still distinct but $m>0$, you do not know whether at least one man exits the elevator or not (it is possible no one leaves on a given floor but all will have emptied the elevator by floor $11$) and it matters the exact order in which they leave the elevator on each floor?

1

There are 1 best solutions below

0
On BEST ANSWER

Question (a):

Let $m_i$ be the number of men that leave at the $i$-th floor. Then the number of ways is precisely the number of solutions to

$$\sum_{i=2}^{11}m_i \leq m \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(m_i \in \mathbb{Z}, \,\,m_i \geq 1)$$

Let $\widetilde{m_i}=m_i-1$, that is equivalent to the number of solution to

$$\sum_{i=2}^{11}\widetilde{m_i} \leq (m-10) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(\widetilde{m_i} \in \mathbb{Z}, \,\,\widetilde{m_i} \geq 0)$$

For each $0 \leq k \leq m-10$, the number of solutions to

$$\sum_{i=2}^{11}\widetilde{m_i} =k \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(\widetilde{m_i} \in \mathbb{Z}, \,\,\widetilde{m_i} \geq 0)$$

is a well known problem (see stars and bars), and the answer is $\binom{k+9}{9}$. So the final answer is:

$$\sum_{k=0}^{m-10}\binom{k+9}{9}=\sum_{k=9}^{m-1}\binom{k}{9}=\binom{m}{10}$$

where we've used reindexation and the hockey stick identity.

Question (b):

First, observe that, for each solution to

$$\sum_{i=2}^{11}m_i = m\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(m_i \in \mathbb{Z}, \,\,m_i \geq 1)$$

there are a number of possible configurations, because each man is now dinstinguishable from the others (which $m_2$ of the $m$ men leave on second floor? which $m_3$ of the $m$ men leave on the third floor? and so on).

For a solution $(m_2,m_3,\dots,m_{11})$, this is given by the multinomial coefficient:

$$ \pmatrix{m\\m_2,\dotsc,m_{11}}=\frac{m!}{m_2!\cdots m_{11}!}\,, $$

Hence, the total number of configurations is:

$$T = \sum_{\substack{\displaystyle m_2+\,\dots\,+m_{11}=m\\\displaystyle m_2,\dots,m_{11}\geq 1}}\pmatrix{m!\\m_2,\dotsc,m_{11}}$$

This look a bit troublesome to calculate. However, by the multinomial theorem:

$$S=\sum_{\substack{\displaystyle m_2+\,\dots\,+m_{11}=m\\\displaystyle m_2,\dots,m_{11}\geq 0}}\pmatrix{m!\\m_2,\dotsc,m_{11}}={10}^{m}$$

Now, look into

$$N=\sum_{\substack{\displaystyle m_2+\,\dots\,+m_{11}=m\\\displaystyle m_2,\dots,m_{11}\geq 0}\\\displaystyle\text{At least one $m_j$ is $0$}}\pmatrix{m!\\m_2,\dotsc,m_{11}}$$

and notice that $S=T+N$. Rewrite $N$ as:

$$N=\sum_{k=1}^9\left[\sum_{\substack{\displaystyle m_2+\,\dots\,+m_{11}=m\\\displaystyle m_2,\dots,m_{11}\geq 0}\\\displaystyle\text{Exactly $k$ of the $m_j$ are $0$}}\pmatrix{m!\\m_2,\dotsc,m_{11}}\right]$$

For each $1 \leq k \leq 9$, there are $\binom{10}{k}$ ways to choose $k$ of the $10$ $m_j$'s to be $0$'s. Then, we may yet rewrite $N$ as:

\begin{align} N&=\sum_{k=1}^9\binom{10}{k}\left[\sum_{\substack{\displaystyle m_2+\,\dots\,+m_{11-k}=m\\\displaystyle m_2,\dots,m_{11-k}\geq 1}}\pmatrix{m!\\m_2,\dotsc,m_{11-k}}\right] \end{align}

Hummm, see the similarity of the term inside brackets to $T$? Indeed, define:

$$\mathcal{T}(n,m)=\sum_{\substack{\displaystyle a_1+\,\dots\,+a_{n}=m\\\displaystyle a_1,\dots,a_{n}\geq 1}}\pmatrix{m!\\a_1,\dotsc,a_{n}}$$

(so that $T=\mathcal{T}(10,m)$.) What we've shown is that $\mathcal{T}$ satisfies the following recursion for $n\geq 2$:

$$\mathcal{T}(n,m)=n^m-\sum_{k=1}^{n-1}\binom{n}{k}\mathcal{T}(k,m)$$

where of course $\mathcal{T}(1,m)=1$.


Lemma: For each $n \geq 1$, we have that:

$$\mathcal{T}(n,m)=\sum_{k=0}^{n}\binom{n}{k}{(-1)}^{n-k}k^m=n!\cdot S(m,n)$$

where $S(\dot\ ,\dot\ )$ denotes a Stirling number of the second kind.

Proof: We use induction. Notice that $\mathcal{T}(1,m)=1$ according to the lemma's formula, so we need only check that the recursion is satisfied, that is, for $n\geq 2$ it holds that:

$$n!\cdot S(m,n)=n^m-\sum_{k=1}^{n-1}\binom{n}{k}\cdot k!\cdot S(m,k)$$

Rewrite it as:

$$\sum_{k=0}^{n}\binom{n}{k}\cdot k!\cdot S(m,k)=n^m$$

which is a well-known identity relating Stirling numbers of the second kind to Bell numbers. This completes the proof of the lemma.


Using the lemma, we find that the answer to question (b) is

$$\mathcal{T}(10,m)=10!\cdot S(m,10)$$

The answer shouldn't be too surprising if we interpret it combinatorially.

Indeed, $S(m,n)$ counts the number of ways to partition a set of $m$ labelled objects into $n$ non-empty and unlabelled sets. What happens here is as follows: first, we partition the $m$ men into $n=10$ non-empty floors (that is, at least one man will leave on each floor). The floors are as yet unlabelled: we don't know what number each floor is! For each such partition of men into 'not-yet-numbered' floors, there are $10!$ ways to choose a numbering of these floors (from the set $\{2,3,\dots,11\}$ of available floor numbers). Hence the result.

Question (c):

The first thing we do is choose an order for the men to leave -- we do not yet know on which floor each man will leave, but we may choose the order. The number of possible orders is $m!$.

Next, we choose the number of men that will leave on each floor. This is equivalent to choosing a solution to

$$\sum_{i=2}^{11}m_i = m\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(m_i \in \mathbb{Z}, \,\,m_i \geq 0)$$

Like before, by 'stars and bars' there are $\binom{m+9}{9}$ solutions. Hence, the final answer is

$$\binom{m+9}{9}m!=\frac{{(m+9)}!}{9!}=\frac{{(m+9)}!}{362880}$$

FINAL EDIT: The answer should be correct now.