# How can I count the number of colored combinations in a set of regions?

Let me first start out by saying as you might have guessed, this is a homework problem. Therefore I am not looking for an answer to the question. I am looking for help in how to analyze it (My textbook is horrid).

I have a grid of 9 squares surrounded by a circle. I can use three colors to color each region with no region touching any other region with the same color (corners don't count). **`

I am asked to find the number of possible different colorings.

I drew a set of nodes with lines connecting neighboring regions, but I still have no idea how to figure out the number of combinations.

I also made a guess of three (which I know is wrong) since you can color the regions once with the three colors then map each color to a different one two times after the first coloring.

No blue is touching any other blue regions, no white is touching any other white regions, no red is touching any other red regions.

-
Do the corners of the grid touch the circle? – Weltschmerz Sep 3 '10 at 0:06
No they do not. – Joshua Enfield Sep 3 '10 at 0:12

I'm not sure about this, maybe I don't understand the problem, but here it goes. If you colour the region outside the grid A, the 8 external cells of the grid must be coloured alternately with B and C, and the one in the center, with A. Thus you have two possible colourings. Same thing if you colour the region outside B, or C. Thus the total number of colourings would be 6.

Update Indeed, there are more. If the external cells are coloured B and C, then the one in the centre may be A, and either B or C, so there are 12 different colourings now.

-
This did help. So I can color it 3 different colors for each "pattern." So for the one I have in the original post, I get 3 combinations, then if I put blue in the middle like you said (colour in circle) then I get another 3 for 6. I know there is still more, but this gives me a way of approach, which is what I was looking for thanks! I just need to look for all the different color patterns then multiply by 3. – Joshua Enfield Sep 3 '10 at 0:25

While it is valuable to attack such problems "by hand," here are some generalities. The general version of this problem is called graph coloring. (The graph being colored here is the graph whose vertices are the regions of the diagram where there is an edge between two regions if they are adjacent.) Counting colorings is known to be #P-hard, so it is not all that easy to do in general. For small graphs there is a reasonable way to compute the number of colorings by any fixed number of colors $n$ by using the deletion-contraction recurrence for the chromatic polynomial.

-
The problem of counting the number of valid graph colourings is a harder problem than just determining if a colouring exists (the graph colouring problem you refer to). Counting number of valid colourings is #P-Complete. – Aryabhata Sep 3 '10 at 2:18
Expanding on this answer a bit, your first step should be drawing the graph of your above picture. Each region is a node and two nodes are connected by an edge only if they are adjacent in your drawing. Like Qiaochu hinted at, once you've drawn the graph you can use all the tools already developed to solve the problem. – Hooked Sep 3 '10 at 2:48
@Moron: thanks for the correction. – Qiaochu Yuan Sep 3 '10 at 3:17

I've found that the simplest way to attack problems like this is really by straight enumeration. Start by coloring the outer region, then see what colors that forces or eliminates; in this case, it means that none of the eight outer cells of your grid can share that color. Now, pick another unforced cell (e.g., the top-left corner of the grid) and see how many ways that you can color it; in this case we have two separate colors that we can use, and whichever one we use then forces the colors on all of the outer cells of the grid, leaving us with just one un-forced color (the central square of the grid can be one of two colors), etc. While this is sort-of a graph coloring problem, it's really closer to a constraint satisfaction problem in disguise, and the methods used for solving a lot of the popular pen-and-paper puzzles like Sudoku/Kakuro/Picross/etc. are pretty closely related to this.

-