In how many different ways can two identical balls be arranged inside $10$ different jars?

Question

In how many different ways can two identical balls be arranged inside $10$ different jars?

My first thought was to say the first ball has $10$ different options, after that the second ball will have $9$ options, so $10 \cdot 9=90$ combinations, however the correct answer is $10+9+8+7+...+1=55$, yet I am unable I can't understand how this solution came to be.

(I am not native English speaker, apologies if the question is badly worded)

Answer 1

Since the balls are identical, the only thing characterizing a solution is how many balls there are in each jar. If $x_i$ denotes the balls in jar $i$, then you need to count the integer non-negative solutions to the equation $$x_1+\cdots+x_{10}=2.$$ In general, an equation such as $x_1+\cdots+x_n = m$ has ${m + n - 1\choose m}$ solutions. Indeed, you can think of a solution as a binary vector of $m+n-1$ bits with exactly $n-1$ ones and $m$ zeros. Then $x_i$ represents how many "$0$" there are between the $(i-1)^{th}$ and the $i^{th}$ "$1$". If we apply the formula to our case, where $m=2$ and $n=10$ we get ${11\choose 2}=55$.

Answer 2

The keys are that

• The balls are identical, so ball-1:jar-1, ball-2:jar-2 is to be regarded as the same as ball-1:jar-2, ball-2:jar-1.

• There are $~10~$ distinct ways that the balls can both be placed in the same jar.

So, if you knew that the two balls were in different jars, then the correct computation would be $~\displaystyle \frac{10 \times 9}{2} = \binom{10}{2} = 45.$

Therefore, the overall correct computation is

$$\binom{10}{2} + 10 = 55.$$

Unclear to me what line of analysis is used to follow the algorithm of $~10 + 9 + \cdots + 1 = 55.$

Edit
It just hit me.

Let $~i,j~$ denote the two jars used, where, without loss of generality, $~i \leq j.$

Then, $~i~$ must be some element in $~\{1,2,\cdots,10\},~$ and for each element $~i,~$ $~j~$ must be some element in $~\{i,i+1,\cdots,10\}.~$

So:

• If $~i = 1,~$ then there are $~10~$ choices for $~j.$

• If $~i = 2,~$ then there are $~9~$ choices for $~j.$

• If $~i = 3,~$ then there are $~8~$ choices for $~j.$

• $~\cdots$

• If $~i = 10,~$ then there is $~1~$ choice for $~j.$

This explains the algorithm $~10 + 9 + \cdots + 1.$