Combinatorics – Different Ways of Arranging Balls in Boxes

combinatoricsfaq

This question is generalization of different cases of combinatorics problems that are generally asked.
We will find general way of arranging $n$ balls in $r$ boxes. Cases :

  1. Identical Balls.
  2. Distinct Balls. Order considered.
  3. Distinct Balls. Order not considered.

Two cases arise in each case :

  1. Empty boxes allowed.
  2. Empty boxes not allowed.

Please feel free to add any other cases or minor variations you might think can be generalized.

Best Answer

CASE 1

Lets discuss number of non negative integral solutions of the equation :

$$a_1+a_2...a_r=n$$

Lets consider them all natural numbers($0$ not included). The $n$ terms can be written as $1+1+1...$ and thus we can choose $(r-1)$ + signs from $(n-1)$ + signs from right for left. Remaining numbers add and form a solutions together. Hence, number of solutions : $$\text{Empty boxes not allowed}$$ $$\binom{n-1}{r-1}$$

If all numbers are whole numbers($0$ included) :

Add $r$ to both sides to get : $$(a_1+1)+(a_2+1)...(a_r+1)=n+r$$

This does not affect number of solutions to $a_i+1$ which is a natural number now. Hence, number of solutions are : $$\text{Empty boxes allowed}$$ $$\binom{n+r-1}{r-1}$$

Minor Variations :

  1. For similar lower bounds like greater than $1$, proceed according as above and add what you think will make it a natural number.
  2. What if one is an even number?

$$2a_1+a_2...a_r=n$$

$$a_2+a_3...a_r=n-2a$$ Number of solutions are :

$$\sum{\binom{n-2a-1}{r-2}}$$

The sum must go for all possible values of $a$. Proceed for similar cases like multiple of $3$ etc...

. What if I have less than sign?

Introduce a dummy variable and count cases for $r+1$ balls. Note that the dummy variable is a natural number. If the sign is $\le$, it is a whole number. Case 2 :

After doing so much hard work on case 1, it is elementary. Just multiply by $n!$ for each corresponding sub-case. Note that order here implies ball $1$ going before $2$ to box $1$ is different from going after ball $2$.

Suitable application : In how many ways can $10$ people go through $3$ gates wide enough for $1$ person only ?

Answer : Empty boxes allowed. $3$ boxes. $10$ balls. Order considered. Therefore :

$$\binom{10+3-1}{3-1}10!$$

Case 3:

Empty boxes allowed :

Every ball has choice to go to $r$ boxes. Hence: $$r^n$$

Note that if you ever get confused what is raised to what, it is $$\text{repeatable}^\text{non-repeatable}$$

This is so because a ball can not be in $2$ boxes. But, a box can have $2$ balls.

Empty boxes not allowed :

By inclusion exclusion, we first count cases $r^n$ then remove where one was empty like : $\binom{r}{1} (r-1)^n$ but then again we remove where 2 were empty from this. As we use $-$ within nested brackets, alternate plus minus will appear :

$$r^n-\binom r 1 (r-1)^n+\binom r 2 (r-2)^n...$$

You can continue till you get $0^\text{something}$.

Related Question