# In how many ways can seven people depart a lift on three floors if at least one person leaves the lift on each floor?

Seven people enter a lift. The lift stops at three unspecified floors. At each of the three floors , no one enters the lift but at least one person leaves the lift . After the three floor stops , the lift is empty. In how many can this happen. What I tried was I created an equation of three variables x,y, z and equated them to 7 .I found the total no. of solution by using formula (n+r-1)C(r-1) and subtracted the case of occurrence of any x,y,z as zero and subtracted those possibilities from the total solution but I was not able to get the result. Any help would be appreciated. Thanks for advance.

• Are the people indistinguishable? (I'd presume so). It is 'stars and bars' except there is a constraint of >0 get out on each floor - how about if you work out how many ways 4 get out on 3 floors, in that way fixing at >= 1 for each floor - using a stars and bars method. – Cato May 24 '17 at 16:30
• Can we solve this question by assuming x=0 and y=0 and then using inclusion exclusion principal. And by using the same process of x+y+z=7 and finding the total number of solutions of this equation by the use of the formula. – user449276 May 25 '17 at 5:27
• I don't see how that would work, x and y cannot be zero – Cato May 25 '17 at 11:13

If there were no restrictions, there would be three choices for each of the seven people, so there would be $3^7$ ways the seven people could depart the lift. However, at least one person gets off the lift at each floor. Therefore, we must exclude those arrangements in which fewer than three floors are used as exits.

There are $\binom{3}{1}$ ways to exclude one of the floors as an exit and $2^7$ ways for the people to depart the lift on the remaining floors.

However, if we subtract $\binom{3}{1}2^7$ from $3^7$, we will have subtracted those distributions in which all seven people depart the lift on the same floor twice, once for each way we could have excluded one of the other floors. Since we only want to subtract these distributions once, we must add them back.

There are $\binom{3}{2}$ ways to exclude two of the three floors and one way for all seven people to exit the lift on the remaining floor.

Thus, by the Inclusion-Exclusion Principle, the number of ways seven people can depart on the lift on three floors with at least one person leaving the lift on each floor is $$3^7 - \binom{3}{1}2^7 + \binom{3}{2}1^7$$

The wording of the problem indicates to me that people are to be treated as distinct.

There are just $4$ possible patterns, viz. $5-1-1,\; 4-2-1,\;3-3-1,\;and\;\;3-2-2$

Compute (Choose people ) $\times$ (Permute patterns), for each pattern.

e.g. for the $3-3-1$ pattern, $\binom73\binom43\binom11 \times \frac{3!}{2!}$,

or if you are comfortable with multinomials, $\binom{7}{3,3,1}\binom{3}{2,1}$

Compute similarly for each pattern, and add up. You should get the desired answer of $1806$

Hint:

Assuming people are distinguishable.

Think of this problem as follows: suppose we have a set with seven elements (the seven people) say $S=\{1,2,3,4,5,6,7\}$. You want to find the number of ways to create a three tuple $(A,B,C)$ (the three floors) of the sets $A,B$ and $C$, where these sets form a partition $\{A,B,C\}$ of the set $S$.

For example $$\Big(\{1,2\}, \, \{3,4\}, \, \{5,6,7\}\Big)$$ represents the scenario that $1,2$ got off on floor $1$, then $3,4$ got off on floor $2$, and $5,6,7$ got off on floor $3$. Whereas $$\Big(\{3,4\}, \, \{1,2\}, \, \{5,6,7\}\Big)$$ represents the scenario that $3,4$ got off on floor $1$, then $1,2$ got off on floor $2$, and $5,6,7$ got off on floor $3$.

Since $\{A,B,C\}$ is a partition containing three sets , so each of the set $A, B$ and $C$ are non-empty (this ensures at least one person left at each of the three floors). Once you have the partition

In your approach you are only counting the number of people stepping out on a floor but person 1 getting out at floor 1 is different from person 1 getting out at say floor 2. Your counting does not take that into consideration.

Your approach is correct, but subtracting the ones that have x, y or z as 0 makes the problem a bit harder. Instead, consider the following approach:

There are 7 people in the lift. Since at least one leaves the lift at each of the 3 floors, we only decide on the remaining 4. Therefore, the integer solutions of x, y, z such that

### x + y + z = 4 where x,y,z $\ge$ 0

And the number of solutions to this problem is found by using your formula.

The possible combinations are 5-1-1, 4-2-1, 412, 3-3-1, 3-2-2, 3-1-3, 2-4-1, 2-3-2, 2-2-3, 2-1-4, 1-5-1, 1-4-2, 1-3-3, 1-2-4, 1-1-5. In each possible way you need to find the permutations