Number of ways to color the numbers from 1 to 9 choosing from 3 colors for each one, such that no two numbers whose sum is odd are the same color

Question

I've realised that odd and even numbers cannot have the same color, but two odds or two evens can.

I tried counting like this: For number 1 we can choose from 3 colors, for 2 we have 2 colors, and for 3 we have two possibilities: if you choose the same color as number 1 (one color left, the same as number 1), there are 2 colors for number 4; if you choose a different color for number 3 (not the same color as number 1, also only one color left) there is only one color for number 4, 6 and 8, and all the other odd numbers 5, 7 and 9 have two colors each. Let's call this when you choose a different color than the color for the number one "locking".

You can lock the colors at the numbers 3, 5, 7 or 9. If you lock it at 3, the number of ways are $3*2*1*1*2*1*2*1*2$, at 5 $3*2*1*2*1*1*2*1*2$, at 7 $3*2*1*2*1*2*1*1*2$ and for 9 $3*2*1*2*1*2*1*2*1$, in each case 48, so $48*4=192$, but this is already over the solution. Why is this wrong, what have I double counted?

Answer 1

This is a good approach, but the mistake you're making is that you can also lock the colours at $4$, $6$ or $8$. If you don't lock the colours at $3$ then you have $2$ choices for $4$, but one of them is the colour that hasn't yet been used, and this will lock the colours.

So actually the number of ways that lock at $4$ is $3\times 2\times 1\times 1\times 1\times 2\times 1\times 2\times 1=24$, the number of ways to lock at $5$ is $3\times 2\times 1\times1\times 1\times1\times2\times1\times2=24$, but there are only $12$ ways to lock at $6$, $12$ for $7$, $6$ for $8$ and $6$ for $9$ (and $6$ more which never lock, i.e. only use two colours).

Answer 2

The colors used for coloring $D=\{1,3,5,7,9\}$ cannot be used for coloring $E=\{2,4,6,8\}$ and vice-versa. So we have two cases: either $D$ is monochromatic or $E$ is monochromatic. In the first case, once we pick the color for each element of $D$ we have $2^4$ ways for coloring $E$. In the second case, once we pick the color for the elements of $E$ we have $2^5$ ways for coloring the elements of $D$. We have counted twice the cases in which both $D$ and $E$ are monochromatic, hence the final outcome is

$$ 3\cdot 2^4+ 3\cdot 2^5 - 6 = \color{blue}{138}. $$

Answer 3

Either odd or even numbers shall be of the same color. Excluding the cases when also the numbers of the other parity are monochromatic there are $$ (2^5-2+2^4-2)3=132 $$ such combinations. By adding 6 possible combinations with both parities being monochromatic one obtains as final answer the number $$138.$$

Answer 4

As you note "sum is odd" is equivalent to "have different parity". Thus, this can be considered a complete bipartite graph, K(5,5). There is a concept called the "chromatic polynomial", which is a polynomial that gives the number of coloring for different number of color. https://web.cs.elte.hu/blobs/diplomamunkak/mat/2009/hubai_tamas.pdf gives the formula for a bipartite graph as being

$chr(K_{n,m}, q) = \sum_k S(m, k)q(q − 1). . .(q − k + 1)(q − k)n$

Where S(m,k) are Stirling numbers of the second kind.

It 's probably easier in this case to simply find the number by inspection, but I thought you might be interested in the wider theory.