# How many combinations of 3 or less blocks in 6 holes?

My first instinct is something like $\frac{6!}{3!}$, but this overcounts, and is the result if every cube is unique. However, if the cubes are not unique, then really its just which holes are filled, which would be $2^6$, except that only up to 3 holes can be filled. This seems to be the same as the number of all unique unordered lists of the numbers 1-6 of length 0-3, but I'm not quite sure.

To be clear: the cubes are not unique, but the holes are unique.

Edit: Each hole can only hold 1 or 0 cubes.

## 1 Answer

There is a general formula for distributions of non-distinct objects among distinct places. For example - Distributing apple 10 coins among 3 people.
The formula goes like this - The number of ways to distribute $n$ non-distinct objects to $r$ distinct places is ${n+r-1\choose r-1}$. I recommend you memorize this formula.
So, here the answer will be ${3+6-1\choose 6-1}={8\choose 5}=56$
Edit: For only one block per hole, the case is much simple. You have to basically choose $3$ holes out of $6$ which are to be filled, $2$ out of $6$ and so on...

Hence, the answer will be
${6\choose 3} +{6\choose 2}+ {6\choose 1}+ {6\choose 0}=20+15+6+1=42$

• Sorry, it wasn't clear that each hole can only hold one cube (so in my case, 5 cubes into 4 holes doesn't work) – Shelvacu Jan 26 '15 at 5:23
• @shelvacu, In that case, It becomes much more simple. I'll edit my answer. – AvZ Jan 26 '15 at 5:26
• I'm sorry, I don't think I understand the ${x\choose y}$ notation. – Shelvacu Jan 26 '15 at 5:35
• ${x\choose y}=^{x}C_{y}=\frac{x!}{y!(x-y)!}$. Check this – AvZ Jan 26 '15 at 5:38
• Thank you, I should really have searched more thoroughly before askign that. Thank you for your help! – Shelvacu Jan 26 '15 at 5:44