Coloring a flag

Separating the coloring into three cases.

case 1: Using exactly 5 different colors . 10x9x8x7x6=30240

case 2: Using exactly 4 different colors . We have two possibilities leftmost section and rightmost section have the same color or the middle's section uppermost and lowermost sections have the same color. 10x9x8x7x2=10080.

case 3: Using exactly 3 colors . Leftmost and rightmost have the same color and middle's section uppermost section and lowermost section have the same color. 10x9x8=720

30240+10080+720=41040

Consider the underlying graph of the flag, the left graph in the following picture, which we will call $F$ (for "flag"):

We will compute the chromatic polynomial of this graph by using deletion-contradiction formula. (Remember that the chromatic polynomial $P(G, k)$ of a graph $G$ , evaluated at $k$ , gives the number of proper colorings of $G$ with $k$ colors. So we just need to evaluate $P(F, 10)$ to get the answer.) For any two adjacent vertices $u,v$ in a graph $G$ , the chromatic polynomial $P(G, k)$ is equal to $P(G-uv, k) - P(G/uv, k)$ , where $G-uv$ is the graph $G$ with $uv$ removed, and $G/uv$ is the graph $G$ with $u,v$ glued. (The proof is obvious: $P(G-uv, k)$ counts colorings where $u,v$ may have any color, and $P(G/uv, k)$ counts colorings where $u,v$ have the same color; this leaves $P(G, k)$ , where $u,v$ have different colors.) We can restate this as $P(G, k) = P(G+uv, k) + P(G/uv, k)$ where $u,v$ are not adjacent.

Also, the chromatic polynomial of a complete graph $K_n$ is easy: $P(K_n, k) = \frac{k!}{(k-n)!}$ , since we have $k$ choices for the first vertex, $k-1$ choices for the second vertex, and so on. (If $k < n$ , the polynomial evaluates to zero.) Moreover, $K_n - e$ , the complete graph missing one edge, is also easy: $P(K_n-e, k) = \frac{k!}{(k-n+1)!} \cdot (k-n+2)$ , which can be done combinatorially (pick one endpoint of the missing edge, color it and its neighbors, then color the other endpoint), or by simply using the deletion-contradiction formula above.

Finally, let $F_1, F_2$ be the middle graph and the right graph in the above picture. Note that if we pick the red vertices as $u,v$ , then $F+uv = F_1$ and $F/uv = F_2$ . So $P(F, k) = P(F_1, k) + P(F_2, k)$ . But the latter two are both complete graphs with one edge missing (the green vertices form the missing edge): $P(F_1, k) = k(k-1)(k-2)(k-3)^2$ and $P(F_2, k) = k(k-1)(k-2)^2$ . Thus $P(F,k) = k(k-1)(k-2)(k^2 - 5k + 7)$ . Plugging in $k = 10$ gives $10 \cdot 9 \cdot 8 \cdot 57 = \boxed{41040}$ .

We must choose three different colors for the left, top, and center regions. There are $10 \times 9 \times 8$ ways to do this.

For the remaining regions, we have four options.

• Choose the same color for left and right, and the same color for top and bottom. No additional choices are necessary. ( $1$ )

• Choose the same color for left and right, and a new color for the bottom. This gives $7$ additional choices.

• Choose the same color for top and bottom, and a new color for the right. This gives $7$ additional choices.

• Choose two new colors for right and bottom. This gives $7 \times 6$ additional choices.

Adding these together, we have $10 \times 9 \times 8 \times (1 + 7 \times (2 + 6)) = 720 \times 57 = \boxed{41\,040}$ possible colorings.

resolved by brute force in Python :

(I don't know why the indentation doesn't work, so I've put an image)

P=0 for a in range(10): for b in range(10): for c in range(10): for d in range(10): for e in range(10): if a!=b and a!=c and a!=d and b!=c and c!=d and e!=b and e!=c and e!=d:P+=1 print(P)

>> 41040 >>

Case 1 gives you 10x9x8x7x7 different designs. Case 2 gives you 10x9x8x8 different designs.

Case 1+Case 2 = 41040 ways

Considering two different cases:

Case 1: Leftmost and rightmost have same colors 10(left-large) *9(middle-center) *8(middle-top) *8(middle-bottom)=5760

Case 2: Leftmost and rightmost have different colors 10(left-large) *9(right-large) *8(middle-center) *7(middle-top) *7(middle-bottom)=35280

Total=5760+35280=41040

Consider the center section, we can have either A) 3 different colors, or B) top and bottom the same color. In Case A, there are 7 possible colors remaining for the two outer sections, in case B, there are 8 possible colors remaining.

Hence A = 10 x 9 x 8 x (7 x 7) = 35280 and B = 10 x 9 x 1 x (8 x 8) = 5760

Total = 41040

Three distinct colours in the middle (10x9x8): => 10x9x8x7x7=35280 (because right side can have same colour then left side). Two distinct colours in the middle (10x9): => 10x9x8x8=5760 (right side again can have same colour than left side). Add both together: => 35280+5760=41040.

This is ultimately a counting problem so the solution comes naturally by breaking down into cases. In my case I will only consider two cases. Case 1: First choose a color to paint both the leftmost side and rightmost side, then pick a color to paint the center rectangle, and then pick two colors for the two remaining rectangles. For our first choice we have 10 options. For our second choice we cant pick whatever we picked in the first choice, so we have 9 options. And for the third and fourth choice we cannot pick the two colors we chose previously, so there are 8 options and then 8 options. Total = $10*9*8*8$ =5760.

Case 2: First choose a color to paint the leftmost side. Then choose a different color to paint the rightmost side, then pick a color to paint the center rectangle, then pick two colors for the two remaining rectangles. For the first choice we have 10 options. For the second choice we are forcing ourselves to pick a different color, so 9 choices. For the third choice we may pick from the 8 remaining colors. And for the last two choices we may pick twice from the 7 remaining colors. Total = $10*9*8*7*7 = 35280$ .

Adding up both of these totals we get the grand total $41040$ .