How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

Question

I have to paint graph

We have three colors. The constraint is that there are no three consecutive nodes of the same color.

And my idea is:

All ways to paint is $3^7$

I'm going to count following situations:

1. Exactly $7$ nodes have the same color - it is three possibilities.
2. Exactly $6$: $7 \times 3 \times 2$
3. Exactly $5$: $7 \times 3 \times 2$
4. Exactly $4$: $5(3 \times 2 \times 1+3 \times 2 \times 2 )$
5. Exactly $3$: $5 (3 \times 2 \times 2 + 3 \times 2 \times 3 + 3 \times 2 \times 2 + 3 \times 2 \times 2 + 3 \times 2 \times 2 + 3 \times 2 \times 3 ) $

Finally it yields: $$3^7 - (1)+(2)+(3)+(4)+(5) = 1548$$

Is it correct? Maybe somebody has another approach?

Answer 1

That number is not going to be correct: it counts e.g. XXXYZZZ twice and XXXXYYY 3 times. It also fails a check: if we rotate a valid color combination, we always obtain a distinct valid color combination. The Orbit-Stabilizer Theorem therefore implies the number will be divisible by $7$.

---

To be honest, if I was going to answer this question, I would just plug it into a computer. Here's some GAP code:

S:=Tuples([1,2,3],7);;
A:=[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,1],[7,1,2]];;
T:=Filtered(S,L->ForAll(A,I->Size(Set(I,i->L[i]))<>1));
Size(T);

which gives $1134$ colorings.

---

But if we really want to do it by hand, it can be done. We begin with all $3^7$ colorings.

• Exactly one color: we exclude $3$ color combinations.

• Exactly two colors: The partitions of $7$ into $2$ parts are $(4,3)$, $(5,2)$, $(6,1)$.

  • Case 43: There are $3 \times 2=6$ choices for these colors, and once chosen they can be arranged as XXXXYYY, XXXYXYY, XXXYYXY or one of their cyclic rotations. So we exclude $6 \times 3 \times 7=126$ possibilities here.

  • Case 52: We have structures XXXXXYY, XXXXYXY and XXXYXXY. There's $3 \times 2=6$ ways to choose the colors, and $7$ rotations. Thus giving $3 \times 6 \times 7=126$ possibilities here.

  • Case 61: We have the structure XXXXXXY. There's $3 \times 2=6$ ways to choose the colors, and $7$ rotations. Thus giving $6 \times 7=42$ possibilities here.

• Exactly three colors: The partitions of $7$ into $3$ parts are $(3,2,2)$, $(3,3,1)$, $(4,2,1)$, and $(5,1,1)$. So we do the bookkeeping:

  • Case 322: We have the structure XXX----. There are $3$ ways to choose the colors (since the Ys and Zs are equinumerous), and $\binom{4}{2}$ ways to assign the Ys and Zs, and $7$ rotations. Thus giving $3 \times \binom{4}{2} \times 7=126$ possibilities here.

  • Case 331: We have structures XXXYYYZ, XXXYYZY and XXXYZYY. There's $3!$ ways to choose the colors, and $7$ rotations. Thus giving $3 \times 3! \times 7=126$ possibilities here.

  • Case 421: We have structures XXXXYYZ, XXXXYZY, XXXXZYY, XXXYXYZ, XXXYXZY, XXXXZYY XXXYYXZ, XXXYZXY, XXXZYXY. There's $3!$ ways to choose the colors, and $7$ rotations. Thus giving $9 \times 3! \times 7=378$ possibilities here.

  • Case 511: We have structures XXXXXYZ, XXXXYXZ, XXXYXXZ. There's $3!$ ways to choose the colors, and $7$ rotations. Thus giving $3 \times 3! \times 7=126$ possibilities here.

Finally, we do the arithmetic: $$3^7-3-(126+126+42)-(126+126+378+126)=1134$$ agreeing with the computational result.