What are the no of ways in which we can place 7 apples in 5 containers, given neither apples nor containers are identical.

Question

What are the no of ways in which we can place $7$ apples in $5$ containers such that each container contains at least $1$ apple, given neither apples nor containers are identical

My attempt is as follows:

As containers are not identical, so let's enumerate them as $C_1,C_2,C_3,C_4,C_5$ and as apples are not identical, so let's enumerate them as $A_1,A_2,A_3,A_4,A_5,A_6,A_7$

Now let's try to fill one apple in all the $5$ containers.

No of ways to fill one apple in container $C_1=7$

No of ways to fill one apple in container $C_2=6$

No of ways to fill one apple in container $C_3=5$

No of ways to fill one apple in container $C_4=4$

No of ways to fill one apple in container $C_5=3$

Let's multiply all of them to get the no of ways in which we can fill $1$ apple in each of the container$=7\cdot6\cdot5\cdot4\cdot3=2520$

Now in each of the $2520$ ways, $2$ apples will be left at the end, now as all the containers are containing at least one apple, we can put the remaining $2$ apples in any of the containers.

So no of ways to place remaining $2$ apples in any of the containers$=5\cdot5=25$

So $2520\cdot25=63000$ should be the answer.But actual answer is $11760$.

Where am I making the mistake. I tried to find it but didn't get any breakthroughs.

Answer 1

• Case 1:

First choose which container will have 3 apples. That you can do on $5$ ways. Then choose 3 apples you will put in it, that you can do ${7\choose 3} $ ways. Now put in each of the remaining containers 1 apple, that you can do on $4!$ ways. So in total you have $5\cdot {7\choose 3}\cdot 4! = 4200$ ways in this case.

• Case 2:

Chose which containers will have 2 apples. That you can don on ${5\choose 2} =10$ ways. Then choose 2 apples for first one and 2 apples for the second one, that you can do on ${7\choose 2}\cdot {5\choose 2}$ ways. Now put in each of the remaining containers 1 apple, that you can do on $3!$ ways. So in total you have $10\cdot {7\choose 2}\cdot {5\choose 2}\cdot 3!= 12600$ ways in this case.

All together you have $ \boxed{16800}$ ways.

Answer 2

The Twelvefold Way is your friend. The number of surjections from a set with $n$ members to a set with $r$ members is $$r!\{\,^n_r\}$$ where the bracked combination is the Stirling number of the second kind. So you're looking for $5!\{\,^7_5\}=120\cdot140=16800$.

---

You went wrong by over-counting. For instance, if you put choose to apple 1 in container A in the first phase and then choose to put apple 7 in container A in the final phase with the two leftover apples, then it is the same result as if you had chosen to put apple 7 in A in the first part and apple 1 in A in the final phase. However, you counted it as two different arrangements.

Answer 3

It depends on how you "put" the apples in the bins, or well on which resulting distributions you are going to consider "different".
After establishing that either the apples and bins are distinguishable (labeled), you are left - fundamentally - with another choice to do:

whether or not to consider the order of the balls inside each bin.

Practically, one case corresponds to using transparent bins into which the apples stacks one over the other, then you consider the bin with $[a_1,a_2]$ different from $[a_2,a_1]$.
The other case to flat large bins, where the position of each apple cannot be distinguished.
More rigorously:
- in the first case (order considered) you are partitioning the set $\{1,2, \cdots, 7 \}$ into a list of $5$ sub-lists (without repetition), ex. $[3,2],[1,5,7],[],[6,4],[]]$;
- in the second (order not considered), the partition is into a list of sub-sets, which may be or not also empty, ex. $[\{ 2,3 \} , \{ 1,5,7 \}, \{ \}, \{ 4,6 \}, \{ \} ]$.

Now, concerning the computations, we have.

1) order considered

We establish first the quantity of apples in each bin, which we can do in a number of ways equal to $$ Q_{\,e} = \left( \matrix{ 7 + 5 - 1 \cr 7 \cr} \right) = 330\quad Q_{\,ne} = \left( \matrix{ 7 - 1 \cr 5 - 1 \cr} \right) = 15 $$ depending on whether we allow empty bins to be present ($Q_{\,e}$) or not ($Q_{\,n\, e}$).
These are obtained with the "stars&bars" approach, or better as the "weak" and "standard" compositions of $7$ into exactly $5$ parts. Then we permute the apples in $7!$ ways, and separate them according to the quantities defined above.
Therefore $$ \eqalign{ & N_{\,e} = \left( \matrix{ 7 + 5 - 1 \cr 7 \cr} \right)7! = 7^{\,\overline {\,5\,} } = 1\,663\,200 \cr & N_{\,n\,e} = \left( \matrix{ 7 - 1 \cr 5 - 1 \cr} \right)7! = {{6^{\,\underline {\,4\,} } \;7!} \over {4!}} = 7 \cdot 6 \cdot 5 \cdot 6^{\,\underline {\,4\,} } = 7^{\,\underline {\,5\,} } \cdot \left( {5 \cdot 4 + 5 \cdot 2} \right) = 75\,600 \cr} $$

That means that you omitted the case in which, when the remaining two balls go into the same bin, you have the choice of which to put above and below.

2) order not considered

The computations in this case are $$ \eqalign{ & N_{\,e} = 5^{\,7} = 78\,125 \cr & N_{\,n\,e} = 5!\left\{ \matrix{ 7 \cr 5 \cr} \right\} = 16\,800 \cr} $$ as already provided in a precedent answer.

Concerning the number $11 \, 760$ I have no idea of what it relates to.

Answer 4

We start with OPs approach:

• The first part, namely putting five apples one into each container in $\frac{7!}{2!}=2\,520$ different ways is quite ok.

• The second part has to be reconsidered. Let's WLOG assume there are $(A_1,A_2,A_3,A_4,A_5)$ in the five container $(C_1,C_2,C_3,C_4,C_5)$ and we want to distribute $A_6$ and $A_7$ into one or two container.

  • Case (a): $A_6, A_7$ distributed into two different container. We have the situation

\begin{align*} &\color{blue}{C_1\qquad C_2\qquad C_3\qquad C_4\qquad C_5}\\ &A_1\qquad A_2\qquad A_3\qquad A_4\qquad A_5\tag{1}\\ &A_6\qquad A_7 \end{align*}

We observe we get the same constellation (1) when in the first part $(A_6,A_2,A_3,A_4,A_5)$ were distributed into the five container $(C_1,C_2,C_3,C_4,C_5)$ and we then put $A_1$ into $C_1$ and $A_7$ into $C_2$. In the same way we can exchange $A_2$ with $A_7$ to also obtain the same constellation (1).

This means we have $\color{blue}{2\cdot 2=4}$ cases to identify.

• Case (b): $A_6, A_7$ put into the same container. Here we have the situation

\begin{align*} &\color{blue}{C_1\qquad C_2\qquad C_3\qquad C_4\qquad C_5}\\ &A_1\qquad A_2\qquad A_3\qquad A_4\qquad A_5\tag{2}\\ &A_6\\ &A_7\\ \end{align*}

We observe that we obtain the same constellation (2) when we have in the first part $(A_6,A_2,A_3,A_4,A_5)$ distributed into the five container $(C_1,C_2,C_3,C_4,C_5)$ and then put $A_1$ and $A_7$ into $C_1$. Here we can exchange $A_1$ with $A_6$ or $A_7$ to also obtain the same constellation (2).

This means we have $\color{blue}{3\cdot 1=3}$ cases to identify.

Conclusion: The $5\cdot 5=25$ cases are subdivided as follows:

• There are $2\binom{5}{2}=20$ ways to select two different container out of the five container and we have to identify four cases as we are in part (a).

• There are $\binom{5}{1}=5$ ways to select one container out of the five container and we have to identify three cases as we are in part (b).

• We finally obtain \begin{align*} 2\,520\cdot \frac{20}{4}+2\,520\cdot \frac{5}{3}&=12\,600 + 4\,200\\ &\,\,\color{blue}{=16\,800} \end{align*} ways to put 7 distinguishible apples into 5 distinguishible container.

Algebraic method:

Here is a generating function approach. Denoting with $[x^n]$ the coefficient of $x^n$ of a series and recalling that $e^x$ is the generating function for counting configurations with labelled objects,

we obtain

\begin{align*} \color{blue}{7![x^7]\left(e^x-1\right)^5}&=7![x^7]\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)^5\tag{3}\\ &=7![x^7]x^5\left(1+\frac{x}{2}+\frac{x^2}{6}\right)^5\tag{4}\\ &=7![x^2]\sum_{j=0}^5\binom{5}{j}\left(\frac{x}{2}+\frac{x^2}{6}\right)^j\tag{5}\\ &=5\,040\left(\binom{5}{1}\cdot\frac{1}{6}+\binom{5}{2}\cdot\left(\frac{1}{2}\right)^2\right)\tag{6}\\ % &=5\,040\left(5\cdot\frac{1}{6}+10\cdot\frac{1}{4}\right)\\ &\,\,\color{blue}{=16\,800} \end{align*}

Comment:

• In (3) we take powers of $x$ up to $x^3$ since higher powers do not contribute to $[x^7]$. This corresponds to a maximum of three apples in a container.

• In (4) we factor out $x^5$.

• In (5) we apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$ and expand the binomial.

• In (6) we select the terms which contribute to $[x^2]$.

Note: The number $11\,760$ seems to be an answer to a different question.