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 :
- For similar lower bounds like greater than $1$, proceed according as above and add what you think will make it a natural number.
- 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}$.
You overcounted.
Label the balls $1$ through $6$ and let the boxes be $B_1,B_2,B_3$.
Now suppose that
- In the first step you assign ball $1$ to $B_1$, ball $2$ to $B_2$ and ball $3$ to $B_3$.
- In the second step you assign all remaining balls to $B_1$.
The end result would be the same if you had instead
- In the first step assigned ball $x$ to $B_1$, ball $2$ to $B_2$ and ball $3$ to $B_3$, where $x\in\{4,5,6\}$
- In the second step assigned all remaining balls to $B_1$.
In this particular instance, the same end scenario $(B_1$ with balls $\{1,4,5,6\}$, $B_2$ with ball $2$ and $B_3$ with ball $3)$ was counted four times.
If you are interested in the answer to this problem, notice that it is equivalent to finding all surjective functions $f: \{1,2,3,4,5,6\}\longrightarrow\{1,2,3\}$.
This is answered in the infamous twelvefold way, and the answer is
$$3!\cdot\left\{\begin{array}{c}6\\3\end{array}\right\},$$
where $\left\{\begin{array}{c}n\\k\end{array}\right\}$ is a Stirling number of the second kind, which counts the number of ways to partition a set of $n$ labelled objects into $k$ nonempty unlabelled subsets.
Best Answer
You counted twice all the variants with two balls in a box. Say, let at first time you chose balls with numbers $2,3,4,5$, and then ball number $2$ falls into the first box. Suppose after that you put ball number $1$ into the first box. This is one way.
Let at first time you chose balls with numbers $1,3,4,5$, and then ball number $1$ falls into the first box. Suppose after that you put ball number $2$ into the first box. This is the second way. And these ways are the same, if the rest balls are in the same boxes. So you count each way twice.
To avoid it, chose two balls by ${}_2C_5$ ways, then a box for them by $4$ ways, and then put $3$ balls into the rest $3$ boxes by $3!$ ways. You get right answer after multiplying it.