If adjacent regions should have different colors, how many ways can I have to color the regions with 4 different colors ? We do not need to use all four colors, yet each region is supposed to be colored by any of them.
I got the answer as 4!*4=96. But, I certainly feel that there are some same colors in neighboring regions and I have to minus it from the total number. I could not come up with any idea about finding same color in neighboring regions. I am trying to understand this concept. Could you please help me to understand this type of questions? Thanks in advance
a square is divided into four regions and each region has a different size
Best Answer
You have to break it up into cases, by considering the possible patterns of colors of colors.
First, you could color each region a different color. There are $4!$ ways to do this. Second, you could color the top and bottom the same color, and the left and right different colors. Again there are $24$ ways to do this. Also, you could color the left and right the same, and the op and bottome different, so that's another $24$.
Finally, you can color the top and bottom the same color, and and color both the left and right with a second color in $12$ ways.
That's all she wrote. $84$ ways in total.
I guess the thing to realize is that each region is adjacent to exactly two others, so it can only be colored the same as one other region.