Determine the number of ways to colour a 1 by n grid using the colours red and white if an even number of squares are to be coloured red.

Question

a) Determine the number of ways to colour a 1 by n grid using the colours red and white if an even number of squares are to be coloured red.

Note that n is greater than or equal to 1 and the number of red squares could be 0.

I know I must consider the cases of n being even and odd, and determine the sum, from zero to n of the squares being red, where the number of red squares is even. But I just want to make sure I haven’t missed any arrangements by saying a) is $2^{n-1}$ when n is even and $2^{n-1}-1$ when n is odd.

b) Determine the number of ways to colour the squares using red, white and blue if an even number of squares are to be coloured red.

For this case, I can have arrangements including red only, white only, blue only, white and blue only, red and white only, red and blue only, and finally all three colours.

Thank you for any help provided.

Answer 1

For part (a): If $n$ is odd, then any arrangement will have either an even number of red squares or an even number of white squares (but not both). Reversing white and red if necessary gives an even number of red squares. So the answer in this case is one half of the total number of arrangements, or $2^{n-1}$.

If $n$ is even, then any arrangement has either an even number of both red and white squares or an odd number of both. But there is a bijection between the latter set and the former by switching the color of the last square. Thus in this case as well the total number of arrangements with an even number of red squares is $2^{n-1}$.

For the general case, part (b), suppose there are $c$ colors and you want to know the number of arrangements with an even number of red colors. Suppose first that the number of squares, $2n$, is even. For each $k$ from $0$ to $2n$ we first choose the number of arrangements with $2k$ red squares in $\binom{2n}{2k}$ ways, and then any arrangement of the remaining squares using $c-1$ colors. Then the total number of such arrangements is $$\sum_{k=0}^n \binom{2n}{2k}(c-1)^{2n-2k} = \sum_{k=0}^n \binom{2n}{2n-2k}(c-1)^{2n-2k} = \sum_{k=0}^n \binom{2n}{2k}(c-1)^{2k}.$$ This can be seen to be an expansion of the formula $$\frac{1}{2}(((c-1)+1)^{2n} + ((c-1)-1)^{2n}) = \frac{1}{2}(c^{2n}+(c-2)^{2n}).$$ In your case, with $c=3$, one gets for the number of arrangements with an even number of squares $$\frac{1}{2}(3^{2n}+1).$$ For an odd number of squares, the computation is very similar, and the answer comes out to be $$\frac{1}{2}(c^{2n+1}+(c-2)^{2n+1}).$$

Answer 2

In part (a) the answer is $2^{n-1}$ for all $n\gt0$, even or odd. You see, flipping the colour of the leftmost square changes the parity of the number of red squares, so there are just as many even as odd, so exactly half of the $2^n$ possible colourings have an even number of red squares.

(The following answer to part (b) is plagiarized from my answer to this related question.)

In part (b), flipping the leftmost non-white square from red to blue or blue to red changes the parity of the number of red squares. This argument would show that there are equal numbers of colourings with an even or an odd number of red squares, except that we've left out one colouring: ALL SQUARES WHITE. In this case there are no red squares, and $0$ is an even number, so even wins by one. That is, there are $\frac{3^n-1}2$ colourings with an odd number of red squares, and $\frac{3^n+1}2$ colourings with an even number of red squares.

More generally, if $k$ colours are available for the squares, then there are $\frac{k^n+(k-2)^n}2$ ways to colour the $1\times n$ rectangle with an even number of red squares, $\frac{k^n-(k-2)^n}2$ ways with an odd number of red squares, so the difference is $(k-2)^n$ in favour of even; see this answer.