1
$\begingroup$

I know there are versions of this question on here, but I'm looking to relate this concept to permutation. Let me explain: If we have $10$ seats and $7$ distinguishable people, and we want to find all ways $7$ people can sit on $10$ seats (they can't sit on top of each other), the formula for that is $$P(10,7)=\frac{10!}{(10-7)!}$$.

Now take the converse, so there are $7$ seats and $10$ distinguishable people, I want to count the ways these $10$ people can sit on $7$ chairs such that at least one person sits on each chair. So I first thought the following:

The first person has $7$ choices to sit on, the second person has $6$... and the $7^{th}$ person has 1 choice. This leaves us $3$ people who can sit on any of the 7 chairs.

Therefore we resort to the formula above (since $3<7$), so we the total ways $10$ people can sit on $7$ chairs with no chair empty is this:

$$7!\cdot \frac{7!}{(7-3)!}$$

This only worked because in the second round because we had fewer people than chairs. So can we generalize this? In other words, how can find a formula for sitting $m$ people in $n$ cars when $m>n$ such that there is at least $1$ person per car and no car can have more than $2$ people than any other cars (sort of like quasi evenly layering a cake).

$\endgroup$
8
  • 1
    $\begingroup$ You counted the number of ways the first seven people could each sit on a separate chair and the last three people could each sit on a separate chair occupied by one of the first seven people. Is that what you meant to count? $\endgroup$ Feb 20, 2020 at 10:01
  • $\begingroup$ @N.F.Taussig Yes! furthermore, suppose I didn't care if the next 3 people could be stacked on each other, would the total number of ways we can seat 10 people on 7 chairs such that no chair is empty be $7!\cdot 3^7$? $\endgroup$
    – Kam
    Feb 20, 2020 at 10:03
  • $\begingroup$ In a stack of 2 or more people, does the order matter? Like if there are 2 people, a and b, then b can sit first and a will sit on top of him or a can sit first and b will sit on top of him. Do you consider this as 1 case or 2? $\endgroup$ Feb 20, 2020 at 10:16
  • 1
    $\begingroup$ If you want to count the number of ways the first seven people could each occupy a different chair and the remaining three people could sit on any chair, your answer would be $7!7^3$ since the last three people would each have seven places where they could sit. To determine the number of ways, $10$ distinct objects could be placed in seven distinct boxes, we would have to use the Inclusion-Exclusion Principle. $\endgroup$ Feb 20, 2020 at 11:07
  • 1
    $\begingroup$ Let me retract what I said in my previous comment. For the general case, we would use the Inclusion-Exclusion Principle. For the specific case of $10$ distinct objects placed in seven distinct boxes, we could consider the cases \begin{align*} 10 & = 4 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 3 + 2 + 1 + 1 + 1 + 1 + 1\\ & = 2 + 2 + 2 + 1 + 1 + 1 + 1\end{align*} $\endgroup$ Feb 20, 2020 at 11:13

1 Answer 1

2
$\begingroup$

In how many ways can ten distinct objects be placed in seven distinct boxes if no box is left empty?

Method 1: The number $10$ can be partitioned into seven parts in three ways. \begin{align*} 10 & = 4 + 1 + 1 + 1 + 1 + 1 + 1\\ & = 3 + 2 + 1 + 1 + 1 + 1 + 1\\ & = 2 + 2 + 2 + 1 + 1 + 1 + 1 \end{align*}

Four objects placed in one box and one object apiece placed in each of the other boxes: Choose which box receives four objects, choose which four objects it receives, then distribute the remaining six objects to the remaining six boxes so that one object is placed in each of those boxes. This can be done in $$\binom{7}{1}\binom{10}{4}6!$$ ways.

Three objects placed in one box, two objects placed in another box, and one object apiece placed in each of the other boxes: Choose which box receives three objects, choose which three objects it receives, choose which of the other boxes receives two objects, choose which two of the remaining objects it receives, then distribute the remaining five objects to the remaining five boxes so that one object is placed in each of those boxes. This can be done in $$\binom{7}{1}\binom{10}{3}\binom{6}{1}\binom{7}{2}5!$$ ways.

Two objects apiece place in three boxes and one object apiece placed in each of the remaining boxes: Choose which three boxes receive two objects each. Suppose the boxes are lined up from left to right. Place two objects in the leftmost box that has been selected to receive two objects, two of the remaining objects in the middle box that has been selected to receive two objects, and two of the remaining objects to be placed in the rightmost box that has been selected to receive two objects. Distribute the remaining four objects to the remaining four boxes so that one object is placed is placed in each of those boxes. This can be done in $$\binom{7}{3}\binom{10}{2}\binom{8}{2}\binom{6}{2}4!$$ ways.

Total: Since these three cases are mutually exclusive and exhaustive, the number of ways of distributing ten distinct objects to seven distinct boxes so that no box is left empty is $$\binom{7}{1}\binom{10}{4}6! + \binom{7}{1}\binom{10}{3}\binom{6}{1}\binom{7}{2}5! + \binom{7}{3}\binom{10}{2}\binom{8}{2}\binom{6}{2}4!$$

Method 2: We use the Inclusion-Exclusion Principle.

If there were no restrictions, we would have seven choices for each of the ten objects. Therefore, there are $7^{10}$ ways to distribute ten distinct objects to seven distinct boxes without restriction.

From these, we must subtract those distributions in which at least one box is left empty. There are $\binom{7}{k}$ ways to select $k$ boxes to be left empty and $(7 - k)^{10}$ ways to distribute the objects to the remaining $7 - k$ boxes. Thus, by the Inclusion-Exclusion Principle, the number of ways ten distinct objects can be distributed to seven distinct boxes if no box is left empty is $$\sum_{k = 0}^{7} (-1)^k\binom{7}{k}(7 - k)^{10} = 7^{10} - \binom{7}{1}6^{10} + \binom{7}{2}5^{10} - \binom{7}{3}4^{10} + \binom{7}{4}3^{10} - \binom{7}{5}2^{10} + \binom{7}{6}1^{10} - \binom{7}{7}0^{10}$$

In how many ways can $m$ distinct objects be placed in $n$ distinct boxes if no box is left empty, where $m \geq n$?

Apply the Inclusion-Exclusion Principle.

$$\sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)^m$$

$\endgroup$
1
  • $\begingroup$ This is one of the most beautiful things people have done for me on MSE, thank you N. F. Taussig, from the bottom of my heart :) and I'll have a proper read tomorrow, its very late here :P $\endgroup$
    – Kam
    Feb 20, 2020 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .