# Calculate the number of ways to paint $5$ buildings with $4$ colours such that all $4$ colours must be used

A developer has recently completed a condominium project in a valley. There are blocks of buildings $A$, $B$, $C$, $D$ and $E$ as shown in the diagram below.

The developer has colours available to paint the buildings. Each block can only be painted using a single colour. Find the number of ways to paint all the blocks if all $4$ colours must be used.

My attempt: We have $5$ ways to choose $4$ buildings with $4$ different colours. Among the $4$ buildings, we have $4!$ ways to paint them using $4$ different colours.

So my answer is $120$. However, the answer given is $240$. What is my mistake?

• Um, what do paint the fifth building? Don't you have 4 chooses for that? I'd get that you method out to give 4*120 =480. Which is also wrong as we double counted. We'd choose a building to be a duplicate color. there are 5 choices for that. We'd paint the other four. 24 four that. We'd pick one of the four buildings to duplicate the fifth one. There are four choices of that. Which ever building we choose to duplicate is a double counting as we could have choosen that building to be a duplicate. so divide by two. – fleablood May 12 '17 at 15:24

You're on the right track. After choosing the four buildings with different colours, what about the fifth? It will be a repeated colour, and there are four colours to choose from. However, we will have overcounted by a factor of $2$, so the final answer will be $$120\cdot\frac42 = 240$$ To explain the overcounting, suppose that you first choose $A,B,C,D$ as the set of four buildings. Then $E$ is the same as one of them, say $A$. But then we will also later consider $E,B,C,D$ as the set of four, with $A$ the same as $E$.

First, you must choose which $2$ buildings will be of the same colour; there are ${5\choose 2} =10$ ways to do this.

Then you have $4!=24$ ways to paint the buildings using your $4$ colours.

The mistake in your solution is that you are not specifying how you will paint the last building; so it's like saying that it is left without colour, which is like giving it a fifth colour distinct from the others. This explains why you arrive at an answer of $120=5!$.

You didn't paint the 5th building at all!

Two buildings must be painted the same color. There are ${5 \choose 2} = \frac {5*4}2 = 10$ possible pairs of buildings that will be the same color.

There are $4*3*2$ ways to paint the remaining $3$ buildings and only one choice left for the two that must be the same color. So that is $10*5*4*3*2 = 240$.

.... or ....

to continue your method: There are $5$ chooses for the duplicate painted building. There are $4!$ ways to be paint the four differently colored buildings. So that is $5*4!=120$.

Then there are $4$ chooses to paint the fifth building. That is $4*120 =480$. However whatever color we choose it will be the same result as if we had chosen the other building to be our fifth building and made the same choices otherwise. So that ere $480/2 = 240$ distinct choices.

For a given set of 4 houses, there are 4!=24 ways to colour them with 4 distinct colours. There are 4 ways to colour the remaining house, so that gives 96 ways. 5 ways to choose the four-set then gives 480 but this double counts all the colourings because each house is or is not left out. So divide by 2 to get 240.

5 buildings need to be painted with 4 different colours, painter needs to use all 4 colors.

Painter needs to use the same colour on 2 buildings.

Say colour 1 is used twice.

There are (5×4) /2 ways of painting 2 out of the 5 buildings.

Now there are 4 colors, so the above is true for each of the 4 colors.

We have 4 × [(5×4)/2] ways of painting 2 out of the the 5 buildings with the same color.

3 remaining buildings still need to be painted with the remaining 3 different colors.

For each of the ways where 2 equal colors have been used on 2 out of 5 buildings we can paint the remaining 3 buildings in 3×2×1 ways

Altogether: 4 × [(5×4)/2] × (3×2×1) = 240.