A Brief Attempt at the ``Cross'' Combinatorial Counting Problem

Programming Verification

For this type of permutation and combination problem where the total count is not excessively large, the most direct way to verify the correctness of an answer is naturally through programming enumeration. The most straightforward programming method is to enumerate all possible coloring schemes for the 16 line segments and then judge one by one whether they meet the requirements. However, this scheme would require enumerating 3^{16} \approx 43 \text{ million} schemes, which is quite a large amount of computation. Therefore, we can think of ways to reduce the computational load.

First, we naturally label the five squares as “Top,” “Bottom,” “Left,” “Right,” and “Center,” as shown below:

Obviously, among these five squares, the “Center” occupies the most special position. Therefore, whether for theoretical analysis or programming calculation, we use it as the starting point. For the convenience of programming, we map the three colors red, yellow, and blue to the numbers 0, 1, and 2 respectively. Thus, we can quickly enumerate all possible coloring schemes for the “Center” as follows:

from itertools import product

centers = [s for s in product(*[range(3)] * 4) if len(set(s)) == 3]

Then, for each coloring scheme of the “Center,” we enumerate its corresponding coloring schemes for “Top,” “Bottom,” “Left,” and “Right.” The method is also simple: first identify the dominant color of the “Center” coloring, then the dominant colors of “Top-Bottom” and “Left-Right” are selected from the remaining two colors respectively. Multiply the number of coloring schemes for “Top,” “Bottom,” “Left,” and “Right” together. Note that after the coloring scheme of the “Center” is given, when enumerating the schemes for “Top,” “Bottom,” “Left,” and “Right,” one side of each has already been determined, so the number of enumerable sides should be 3^3 instead of 3^4. The total reference code is as follows:

def master(s):
    """Identify the dominant color"""
    for i in range(3):
        if s.count(i) == 2:
            return i

N = 0
for c in centers:
    m = master(c)  # Current dominant color
    M = [i for i in range(3) if i != m]  # Remaining two colors
    for i in range(2):  # Top, Bottom dominant colors
        for j in range(2):  # Left, Right dominant colors
            top = [s for s in product([c[0]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[i]]
            bottom = [s for s in product([c[2]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[1 - i]]
            left = [s for s in product([c[1]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[j]]
            right = [s for s in product([c[3]], *[range(3)] * 3) if len(set(s)) == 3 and master(s) == M[1 - j]]
            N += len(top) * len(bottom) * len(left) * len(right)

print('Total number of coloring schemes is', N)

Finally, the total number of coloring schemes is calculated to be 27,216.

Theoretical Calculation

To calculate the final number of coloring schemes from a theoretical perspective, the logic is the same as the experimental verification: center first, then the sides. However, the brute-force enumeration part of the code is replaced by calculations using permutation and combination formulas.

First, consider the number of coloring schemes for the “Center.” Looking at the combinations, there are three types: “0 0 1 2,” “0 1 1 2,” and “0 1 2 2.” Taking “0 0 1 2” as an example, to insert a 1 into “0 0,” there are 3 possible positions, and then to insert a 2, there are 4 possible positions. So each combination has 3 \times 4 = 12 permutations. Therefore, the number of coloring schemes for the “Center” is 12 \times 3 = 36.

Next, we divide the coloring schemes of the “Center” into two categories as shown in the figures below: 1. Two dominant colors are adjacent; 2. Two dominant colors are opposite.

Obviously, the ratio between the two is 2:1. Therefore, among the coloring schemes of the “Center,” there are 24 where the dominant colors are adjacent and 12 where the dominant colors are opposite. We discuss these two cases separately below.

First, dominant colors are adjacent. Without loss of generality, consider the case on the left in the figure above. At this time, the dominant color of the “Center” is “Red,” so the dominant colors for “Top” and “Bottom” can only be “Yellow” or “Blue.” Suppose the dominant color of “Top” is chosen as “Yellow”; then its coloring schemes are only 3, and correspondingly, the coloring schemes for “Bottom” are also only 3. Thus, there are 3 \times 3 = 9 coloring schemes for “Top-Bottom.” If the dominant color of “Top” is chosen as “Blue,” then its coloring schemes are also only 3, but correspondingly, the coloring schemes for “Bottom” are 6. Thus, there are 3 \times 6 = 18 coloring schemes for “Top-Bottom.” Adding the two cases gives 9 + 18 = 27 schemes. The analysis for “Left-Right” is the same, and “Top-Bottom” and “Left-Right” can be combined freely. Therefore, there are 27 \times 27 = 729 schemes. Note that this is for only one “Center” coloring scheme, so the total number of coloring schemes in this case is 729 \times 24 = 17,496.

Second, dominant colors are opposite. Without loss of generality, consider the case on the right in the figure above. At this time, the dominant color of the “Center” is “Red,” so the dominant colors for “Top” and “Bottom” can only be “Yellow” or “Blue.” Suppose the dominant color of “Top” is chosen as “Yellow”; then its coloring schemes are only 3, and correspondingly, the coloring schemes for “Bottom” are also only 3. Thus, there are 3 \times 3 = 9 coloring schemes for “Top-Bottom.” If the dominant color of “Top” is chosen as “Blue,” its coloring schemes are also only 3, and the coloring schemes for “Bottom” are likewise only 3. Thus, there are 3 \times 3 = 9 coloring schemes for “Top-Bottom.” Adding the two cases gives 9 + 9 = 18 schemes.

However, in this case, the result for “Left-Right” is different from “Top-Bottom” and requires separate analysis. Suppose the dominant color of “Left” is chosen as “Yellow”; then its coloring schemes are only 3, and correspondingly, the coloring schemes for “Right” are also only 3. Thus, there are 3 \times 3 = 9 coloring schemes for “Left-Right.” If the dominant color of “Left” is chosen as “Blue,” then its coloring schemes are 6, and the coloring schemes for “Right” are also 6. Thus, there are 6 \times 6 = 36 coloring schemes for “Left-Right.” Adding the two cases gives 9 + 36 = 45 schemes. Therefore, the total number of coloring schemes for “Top,” “Bottom,” “Left,” “Right,” and “Center” is 18 \times 45 \times 12 = 9,720.

Finally, adding the two together gives 17,496 + 9,720 = 27,216.

Article Summary

It has been a long time since I worked on math problems; this was purely to brush up on high school mathematics knowledge.