# weird combinatorics, combinations question from cambridge challenge exercise

A child has $10$ identical blocks, each of which is to be painted with one of $4$ colours. how many different ways can the $10$ blocks be painted?

Answer is $286$ but I have no idea how they got it.

From cambridge year ten book $2$

-
Hint: this is equivalent to finding number of solutions of the equation $x_1+x_2+x_3+x_4=10$ and all $x_i$ are non-negative. which can be done in $\frac{13!}{10! \times 3!}$ different ways. – K.K.McDonald Mar 28 at 8:47
how did you get 13! ? – vicky era Mar 28 at 9:02
i got 13 cause it's equivalent to number of different ways of putting 10 star signs like $**********$ and three slash signs $///$ together. think of it like there is 4 boxes (4 $x_i$ variable) and slash sign / distinguish two adjacent boxes from eachother. number of stars in each section between slashes is value of $x_i$ for example $*//*******/**$ is equivalent to $x_1=1,x_2=0,x_3=7,x_4=2$ – K.K.McDonald Mar 28 at 9:05
For completenes this link: stars and bars – drhab Mar 28 at 9:33

A common way to explain it is known as "stars and bars".

I shall illustrate it by "dipping" identical balls (boxes) into distinct bins (of colours) numbered $1-4$, and depict the results obtained

One result could be $\;\;\bullet\bullet\bullet|\bullet\bullet\bullet\bullet|\bullet |\bullet\bullet\;\to\;\; 3-4-1-2$ of each of the colours.

Make two notes: only $3$ dividers are needed to depict $4$ bins, and some bins could remain empty, e.g. $|\bullet\bullet\bullet\bullet\bullet\bullet\bullet|\bullet\bullet\bullet|$ depicting $\;\;0-7-3-0$

So if there are $n$ balls and $k$ bins ($k-1$ dividers), the only choice you have is to place the dividers among the lot, thus

$\dbinom{n+k-1}{k-1}$ which works out to $\dbinom{10+3}{3} = 286$ for your particular example.

You can look here if you need a a more technical explanation

-
grey cells are (still) working fine :) – drhab Mar 28 at 9:38
@drhab:Yea, the idea is to keep them firing as long as possible ! :) – true blue anil Mar 28 at 9:41
Isn't this usually just called "combinations with replacement"? – alexw Mar 28 at 20:33
@alexw:There are various terms used for the type of problem, such as combinations with replacement or combinations with repetition. "Stars or bars" or "balls and bins" refers to an approach used to solve the problem. – true blue anil Mar 29 at 3:41

HINT:

Calculate the number of ways to write $10$ as a sum of $4$ non-negative integers.

-
a mathematical model is indeed much more transparant than reality. – drhab Mar 28 at 9:36

Why is it the case that this problem can be reduced to the problem of finding four non-negative numbers that sum to $10$? That is because in the end, every box is going to be painted with some colour, which gives $10$ as the total number of blocks,but it's possible that some colours could be left out, in which case their contribution to the above sum would be zero. Thus the problems are the same and have the same answer.

As for the second problem, suppose you have some four non-negative numbers $x_1+x_2+x_3+x_4=10$. Now add $4$ on each side in this fashion: $(x_1 + 1)+(x_2 + 1)+(x_3+1)+(x_4+1)=10+4=14$. Note now that if we let $y_i=x_i+1$ then the $y_i$ are strictly positive integers summing to $14$. Hence our problem now reduces to finding the number of strictly positive solutions to the problem $y_1+y_2+y_3+y_4=14$.

But now, this can be done in the following manner: Suppose I draw $14$ dots right here: $$\cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \ \cdot$$ Now we can represent a sum of $14$ using $4$ integers by doing a partition of these dots. I'll explain with an example: Suppose you want to represent $14=4+2+4+4$,then you would show it as: $$\cdot \cdot \cdot \ \cdot \mid \cdot \ \cdot \mid \cdot \cdot \cdot \ \cdot \mid \cdot \cdot \cdot \ \cdot$$ Similarly for $14=7+1+5+1$, $$\cdot \cdot \cdot \cdot \cdot \cdot \cdot \mid \cdot \mid \cdot \cdot \cdot \cdot \cdot \mid \cdot$$ Now do you see! To constrcut a partition of $14$ into $4$ positive integers, we had to choose how to put $3$ dividers in $13$ slots, so that $4$ groups of dots are created, each of which are not empty and the total being $14$. It follows that the answer is $\binom{13}{3}$, or $\frac{13!}{3!10!}=286$.

As an exercise, think about what would happen if the blocks were distinct as well, and if blocks had $6$ faces, each face can be differently coloured.

-
Be careful. You want to write $10$ as the sum of four non-negative integers and $14$ as the sum of four positive integers. – N. F. Taussig Mar 28 at 10:00
Edited sir. Thank you for pointing it out. – астон вілла олоф мэллбэрг Mar 28 at 10:03
I have a doubt. Can I not say that each block can be painted in 4 ways and since there are ten of them the total number of ways to do this is $4^10$ ? – user230452 Mar 28 at 14:44
NO! You can say that only if the blocks are distinct! For example, consider two identical blocks, and the colours red and blue. The number of choices according to what you are saying should be $2^2=4$,but then suppose I paint (the "second" one red "first" one blue) , and (the "first" one red "second" one blue), you can't really make out the difference because the blocks are identical, there is no first or second block in truth. We would call this one single situation, namely (paint one block red one block blue). Thus we should not overcount by including situations like the above. – астон вілла олоф мэллбэрг Mar 28 at 14:58

If the bocks were numbered $1$ through $10$ then the answer would be simply $4^{10}$. But all the blocks are identical so the problem is a little harder. Imagine you coloured all the blocks and then lined them up by colour, perhaps all the reds then all the greens ect... we would have a picture like this: $$[\;\;]\ [\;\;]\ {\Big|}\ [\;\;]\ {\Big|}\ [\;\;]\ [\;\;]\ [\;\;]\ {\Big|}\ [\;\;]\ [\;\;]\ [\;\;]\$$ Where "$|$" divides the groups of boxes. Since this arrangement would uniquely describe the colouring of the blocks (up to order which we don't care about) the number of ways to colour the blocks is the number of ways to make this arrangement, thus the number of ways to choose the position of the dividers "$|$". $$N={13\choose 3} = 286$$ With $n$ blocks and $m$ colours the number of colourings is given by $$N = {n+m-1\choose m-1}$$ which is indeed the number of ways to sum $m$ numbers to $n$.

-