1
$\begingroup$

I have to paint graph

$7$-cycle

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.