The flag colouring problem

Question

Ok so I came across this question. It goes something like this : A new flag is to be designed with 6 vertical stripes using all 4 colours. In how many ways can this be done so that no 2 adjacent stripes have the same colour and it is given that we have to use all the 4 colours for 4 stripes ( we cannot use less than 4 colours to colour the stripes. For example, for a given set of colours {1,2,3,4}, the solution cannot be like 1,2,1,2,1,2). I've been struggling to come up with a solution. Can someone show me how it is done?

Answer 1

First, lets forget about the restriction that we must use all four colours (i.e. we are now counting how many ways this can be done using four or less colours).

You then have $4$ choices for the first stripe.

Then $3$ choices for the second stripe (cannot be the same colour as the first stripe).

Similarly, $3$ choices for each of the following stripes.

Thus, there are $4 \times 3 \times 3 \times 3 \times 3 \times 3 = 972$ combinations.

However, we must subtract the patterns that do not use all $4$ colours, so you ask yourself how many ways you can colour the flag with three or less colours, with no two adjacent stripes having the same colour.

There are $C_3^4 = 4$ ways of picking three colours out of four, and the number of patterns for the chosen set of colours is done using the above logic, giving $3 \times 2 \times 2 \times 2 \times 2 \times 2 = 96$ combinations.

It follows that we are left with $972-4 \times 96 = 588$ patterns.

However, as pointed out in the comments, the patterns that only use $2$ colours have been subtracted twice instead of just once, so we must add one set of these back in.

There are $C_2^4 = 6$ ways you can choose two colours out of four, and after you have selected two colours, there are only $2$ possible patterns (namely having the two colours alternating, or you can calculate $2 \times 1 \times 1 \times 1 \times 1 \times 1 = 2$ like before). Thus, we must add back in $6 \times 2 = 12$ patterns.

In total, the answer is $972-4 \times 96 + 6 \times 2 = 600$ patterns.