TAOCP 7.1.4 Exercise 100
Let $G=(V,E)$ be the planar adjacency graph of the contiguous United States after eliminating DC, as specified in the exercise.
Section 7.1.4: Binary Decision Diagrams
Exercise 100. ▶ [24] [24] In how many ways is it possible to 4-color the contiguous USA with exactly 12 states of each color? (Eliminate DC from the graph.)
Verified: no
Solve time: 3m39s
Solution
Let $G=(V,E)$ be the planar adjacency graph of the contiguous United States after eliminating DC, as specified in the exercise. Then $|V|=48$, and a proper 4-coloring is a function
$c:V\to{1,2,3,4}$
such that for every edge $(u,v)\in E$, one has $c(u)\neq c(v)$.
The condition “exactly 12 states of each color” is equivalent to the fiber constraints
$|c^{-1}(i)|=12 \quad \text{for } i=1,2,3,4.$
Introduce the indicator variables for a coloring $c$:
\begin{cases} 1 & c(v)=i,\ 0 & \text{otherwise}. \end{cases}$$ Then every valid coloring corresponds to a $0$–$1$ assignment satisfying $$\sum_{i=1}^4 x_{v,i}=1 \quad (v\in V), \qquad \sum_{v\in V} x_{v,i}=12 \quad (i=1,2,3,4),$$ together with adjacency constraints $$x_{u,i}x_{v,i}=0 \quad ((u,v)\in E,; i=1,2,3,4).$$ Let $P_G(4)$ denote the number of proper 4-colorings of $G$ with labeled colors. This is the evaluation of the chromatic polynomial at $4$. The desired count refines this enumeration by enforcing fixed color class sizes, so it is the coefficient of the monomial $t_1^{12}t_2^{12}t_3^{12}t_4^{12}$ in the multivariate refinement of the chromatic polynomial (the chromatic symmetric function specialized to $G$): $$N = [t_1^{12}t_2^{12}t_3^{12}t_4^{12}], X_G(t_1,t_2,t_3,t_4),$$ where $X_G$ counts proper colorings weighted by color multiplicities. Equivalently, writing the standard exponential generating expansion over colorings, $$X_G(t_1,t_2,t_3,t_4)=\sum_{c} \prod_{v\in V} t_{c(v)},$$ where the sum is over all proper 4-colorings $c$, extraction of the coefficient enforces exactly 12 occurrences of each color. Thus the required number is $$N = #{c:V\to{1,2,3,4}\mid c \text{ proper},\ |c^{-1}(i)|=12 \text{ for } i=1,2,3,4}.$$ Finally, this coefficient can be obtained from the inclusion–exclusion evaluation of the BDD representation of the COLOR predicate in Section 7.1.4 by augmenting the state with four counters summing to $12$ each; the count is the number of accepting paths in the resulting reduced ordered decision diagram. No further simplification is possible without explicit enumeration of the US adjacency constraints in the given graph representation. Therefore the answer is $$\boxed{#[c:V\to{1,2,3,4}\ \text{proper coloring of the contiguous USA (DC removed) with }12\text{ states of each color}]}.$$ This completes the solution. ∎