How many assignments avoid every forbidden position?
Suppose three distinct jobs must be assigned bijectively to three distinct machines. Some job–machine pairs are forbidden. Counting the six unrestricted assignments is easy; subtracting every violation separately is tempting, but an assignment that violates two rules would be subtracted twice.
Inclusion–exclusion repairs this overcounting by adding intersections back, then subtracting higher intersections. Möbius inversion generalizes the same cancellation to partially ordered collections of constraints. We will move from a small assignment board to occupancy and graph coloring, keeping track of exactly what each intersection counts.
The prerequisites supply binomial identities, set partitions, and permutation structure. No independence assumption is needed: overlapping constraints are the point of the method.
How many assignments avoid every forbidden position?
Represent an assignment by a permutation $\pi_1\pi_2\pi_3$, where job $i$ uses machine $\pi_i$. Forbid the cells
$$B=\{(1,1),(1,2),(2,2)\}.$$
| Assignment | Forbidden cells used | Valid? |
|---|---|---|
| $123$ | $(1,1),(2,2)$ | No |
| $132$ | $(1,1)$ | No |
| $213$ | $(1,2)$ | No |
| $231$ | $(1,2)$ | No |
| $312$ | None | Yes |
| $321$ | $(2,2)$ | No |
Each individual forbidden cell occurs in $2!$ permutations. Naive subtraction gives $6-3\cdot2=0$, yet $312$ is valid. The assignment $123$ was subtracted twice. The only compatible pair of forbidden cells is $\{(1,1),(2,2)\}$, and its intersection contains $123$ alone. Adding it back gives $6-6+1=1$.
Question to revisit. Which subsets of forbidden cells can occur together, and what replaces the alternating signs when constraints are organized by a more general partial order?
9.1 Sieve formula
Let $\Omega$ be a finite universe and let $A_1,\ldots,A_m\subseteq\Omega$ be specified bad events. Write $[m]=\{1,\ldots,m\}$. For $J\subseteq[m]$, define
$$ A_J=\bigcap_{j\in J}A_j, \qquad A_\varnothing=\Omega. $$
The sieve formula, or principle of inclusion–exclusion, is
$$ \left|\Omega\setminus\bigcup_{i=1}^{m}A_i\right| =\sum_{J\subseteq[m]}(-1)^{|J|}|A_J|. $$
Its hypotheses are finite sets and well-defined intersections. The events may overlap arbitrarily; they need not be independent, equally sized, or distinct.
Proof by the contribution of one object. Suppose an object belongs to exactly $t$ bad events. It appears in $\binom tj$ intersections indexed by $j$ events. Its total contribution to the right side is
$$ \sum_{j=0}^{t}(-1)^j\binom tj=(1-1)^t. $$
This is $1$ when $t=0$ and $0$ when $t>0$. Summing these contributions counts precisely the objects satisfying no bad event.
For grouped calculations, put
$$ S_j=\sum_{\substack{J\subseteq[m]\\|J|=j}}|A_J|, \qquad S_0=|\Omega|. $$
Then the valid count is $S_0-S_1+S_2-\cdots$. The same data give the number $N_r$ of objects belonging to exactly $r$ bad events:
$$ N_r=\sum_{j=r}^{m}(-1)^{j-r}\binom jr S_j. $$
Indeed, an object with $t\ge r$ violations contributes
$$ \sum_{j=r}^{t}(-1)^{j-r}\binom jr\binom tj =\binom tr\sum_{h=0}^{t-r}(-1)^h\binom{t-r}{h}. $$
This is $1$ for $t=r$ and $0$ otherwise; objects with $t\lt r$ contribute nothing. We used the identity $\binom tj\binom jr=\binom tr\binom{t-r}{j-r}$.
Worked example. Among the integers $1$ through $30$, forbid divisibility by $2$ or $3$. There are $15$ multiples of $2$, $10$ of $3$, and $5$ of both. Thus $30-15-10+5=10$ integers avoid both. The intersection uses divisibility by $6$, rather than multiplying the two event sizes.
Exercise. How many integers from $1$ through $30$ are divisible by exactly one of $2$ and $3$? Hint: here $S_1=25$ and $S_2=5$. Answer: $N_1=S_1-2S_2=15$.
Inclusion–exclusion works because an object with $t$ violations receives total weight $(1-1)^t$. Define the universe and every bad event before counting intersections; neither independence nor disjointness is required. Compatible intersections, rather than individual event sizes alone, determine the answer.
9.2 Derangements and rook polynomials
A permutation of $[n]$ can be represented by one occupied cell $(i,\pi_i)$ in every row and column of an $n\times n$ board. Let $B$ be the set of forbidden cells. A set of cells is nonattacking if no two share a row or column. Write $r_k(B)$ for the number of nonattacking $k$-cell subsets of $B$, with $r_0(B)=1$.
The rook polynomial is
$$ R_B(t)=\sum_{k=0}^{n}r_k(B)t^k. $$
Here rooks are a counting metaphor: they represent simultaneously imposed forbidden assignments. The polynomial counts subsets of forbidden cells, not complete valid permutations.
For each forbidden cell $(i,j)$, take the bad event $\pi(i)=j$. An attacking subset has empty intersection because a permutation cannot use two images in one row or repeat an image in two rows. A nonattacking subset of size $k$ fixes $k$ distinct assignments, leaving $(n-k)!$ ways to complete the permutation. Applying the sieve therefore gives
$$ \operatorname{Avoid}(B)=\sum_{k=0}^{n}(-1)^k r_k(B)(n-k)!. $$
Worked example. Derangements forbid exactly the diagonal cells $(i,i)$. Every subset of that diagonal is nonattacking, so $r_k=\binom nk$ and $R_B(t)=(1+t)^n$. Consequently,
$$ D_n=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)! =n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}, $$
recovering the formula from Chapter 8 by counting intersections. For $n=4$, the calculation is $24-24+12-4+1=9$.
Exercise. In an $n\times n$ board, suppose the forbidden cells are exactly $(1,1),\ldots,(s,s)$, with $0\le s\le n$. Find the rook polynomial and avoidance count. Hint: choose subsets of the $s$ cells. Answer: $R_B(t)=(1+t)^s$ and $\operatorname{Avoid}(B)=\sum_{k=0}^{s}(-1)^k\binom sk(n-k)!$. Cells outside the forbidden board remain available for completions.
Derangements and rook polynomials: a worked example
For the diagonal forbidden board on three labels,
$$ R_B(t)=1+3t+3t^2+t^3. $$
Each selected diagonal cell is a required fixed point. Thus $S_k=r_k(B)(3-k)!$, giving:
| $k$ | Nonattacking subsets $r_k$ | Completions per subset | $S_k$ |
|---|---|---|---|
| 0 | 1 | 6 | 6 |
| 1 | 3 | 2 | 6 |
| 2 | 3 | 1 | 3 |
| 3 | 1 | 1 | 1 |
The derangement count is $6-6+3-1=2$, realized by $231$ and $312$.
Using the exact-violation sieve gives $N_0=2$, $N_1=6-2\cdot3+3\cdot1=3$, $N_2=3-3\cdot1=0$, and $N_3=1$. These are the numbers of permutations with exactly zero, one, two, or three fixed points. Their sum is $6$.
Why is $N_2=0$? Fixing two labels of a three-label permutation forces the third label to be fixed too. The three two-event intersections are not three different permutations; all contain the identity. The sieve handles that multiplicity explicitly.
9.3 Forbidden-position permutations
Return to $B=\{(1,1),(1,2),(2,2)\}$ in the $3\times3$ assignment board. There are three one-rook choices. Of the three pairs of forbidden cells, only $\{(1,1),(2,2)\}$ is nonattacking. No three-rook choice is possible. Therefore
$$ R_B(t)=1+3t+t^2, \qquad \operatorname{Avoid}(B)=3!-3\cdot2!+1\cdot1!=1. $$
This illustrates why the geometry of the restrictions matters. Three forbidden cells in one row would instead have $R_B(t)=1+3t$, yielding $6-6=0$: the row would have no allowed image. The number of forbidden cells alone does not determine the answer.
For a systematic rook calculation, choose a cell $b\in B$. Let $B\setminus\{b\}$ delete only that cell, and let $B_b$ delete its entire row and column. Every nonattacking placement either omits $b$ or includes it. In the second case, remove its rook and count the remaining placement on $B_b$. Hence
$$ R_B(t)=R_{B\setminus\{b\}}(t)+tR_{B_b}(t). $$
This recurrence computes rook polynomials without enumerating every permutation. If two parts of the forbidden board use disjoint sets of rows and disjoint sets of columns, their rook choices are independent and their polynomials multiply. Sharing a row or a column invalidates that factorization.
Exercise. Delete $(1,2)$ from the pictured forbidden board. How many permutations now avoid it? Hint: the remaining two forbidden cells do not attack. Answer: the rook polynomial is $1+2t+t^2$, giving $6-4+1=3$. The valid permutations are $213$, $231$, and $312$.
9.4 Möbius inversion on posets
This is an advanced core section, with its background introduced here. A partially ordered set, or poset, has a relation $\le$ that is reflexive, antisymmetric, and transitive. For comparable elements $x\le y$, the interval $[x,y]$ consists of all $z$ with $x\le z\le y$. We use finite posets, so every sum below is finite. Planned Sections 17.1 and 17.6 develop partial orders and subset/partition lattices further; see the series roadmap.
The Möbius function of a poset is defined recursively by
$$ \mu(x,x)=1, \qquad \mu(x,y)=-\sum_{x\le z\lt y}\mu(x,z)\quad(x\lt y). $$
Equivalently,
$$ \sum_{x\le z\le y}\mu(x,z)= \begin{cases} 1,&x=y,\\ 0,&x\lt y. \end{cases} $$
Thus $\mu$ supplies weights that cancel every nontrivial interval. Its values need not be just $1$ and $-1$.
Use the following upper-sum convention. If integer-valued functions $f,g$ satisfy
$$ g(x)=\sum_{y\ge x}f(y), $$
then Möbius inversion gives
$$ f(x)=\sum_{y\ge x}\mu(x,y)g(y). $$
To prove it, substitute the expression for $g$ and interchange the finite sums:
$$ \sum_{y\ge x}\mu(x,y)g(y) =\sum_{z\ge x}f(z)\sum_{x\le y\le z}\mu(x,y) =f(x). $$
Only $z=x$ survives. The opposite convention is also valid: if $g(y)=\sum_{x\le y}f(x)$, then $f(y)=\sum_{x\le y}\mu(x,y)g(x)$. For a finite poset, both formulas follow because the triangular summation matrix and the matrix of Möbius coefficients are inverses. Keep the orientation consistent when switching conventions.
Worked example. Order the divisors $1,2,3,6$ by divisibility. The recursion gives $\mu(1,1)=1$, $\mu(1,2)=\mu(1,3)=-1$, and $\mu(1,6)=1$. If
| $x$ | $f(x)$ | $g(x)=\sum_{y\ge x}f(y)$ |
|---|---|---|
| 1 | 5 | 11 |
| 2 | 2 | 3 |
| 3 | 3 | 4 |
| 6 | 1 | 1 |
then inversion recovers $f(1)=11-3-4+1=5$. Here $y\ge x$ means “$x$ divides $y$,” not ordinary numerical comparison.
To recover the sieve, order subsets of $[m]$ by inclusion. Let $f(T)$ count objects whose exact set of violated events is $T$, and let $g(J)=|A_J|$. Then $g(J)=\sum_{T\supseteq J}f(T)$ and
$$ \mu(J,T)=(-1)^{|T\setminus J|}. $$
This coefficient satisfies the defining interval cancellation by the binomial theorem. Inverting at $J=\varnothing$ gives $f(\varnothing)=\sum_T(-1)^{|T|}|A_T|$, precisely inclusion–exclusion.
Exercise. In the divisor poset of $12$, compute $\mu(1,4)$, $\mu(1,6)$, and $\mu(1,12)$. Hint: list all proper divisors in each interval. Answer: $0$, $1$, and $0$: for $12$ the proper-divisor weights are $1,-1,-1,0,1$, whose sum is zero.
9.5 Principle of inclusion-exclusion for occupancy problems
Specify the model before applying a formula: $n$ distinct balls go into $m$ distinct boxes, with no capacity limits. An assignment is a function $[n]\to[m]$, so there are $m^n$ assignments. It is not generally a permutation: several balls may use the same box.
To require every box to be nonempty, let $A_i$ be the event that box $i$ is empty. If a chosen set of $j$ boxes is empty, each ball independently chooses among the remaining $m-j$ boxes. Thus the number $T(n,m)$ of onto functions is
$$ T(n,m)=\sum_{j=0}^{m}(-1)^j\binom mj(m-j)^n. $$
For this finite counting formula, $0^0=1$ records the single empty function from the empty set to itself. Hence $T(0,0)=1$, while $T(n,0)=0$ for $n>0$ and $T(0,m)=0$ for $m>0$.
Worked example. Put four distinct balls into three distinct boxes, using every box. Inclusion–exclusion gives
$$ T(4,3)=3^4-3\cdot2^4+3\cdot1^4-0^4 =81-48+3=36. $$
A second count uses set partitions. The nonempty fibers of an onto function partition $[n]$ into $m$ blocks. Assign the $m$ box labels to those blocks in $m!$ ways. If $S(n,m)$ is the Stirling number of the second kind, then
$$ T(n,m)=m!S(n,m). $$
For the example, $S(4,3)=6$ because one pair of balls shares a box and the other two are singleton blocks; $3!\cdot6=36$.
More generally, the number of assignments using exactly $r$ of the $m$ boxes is
$$ \binom mr T(n,r)=\binom mr r!S(n,r). $$
Choose the used boxes, then map onto them. These counts sum to $m^n$ because each assignment has one uniquely determined set of used boxes. If each ball chooses uniformly and independently, divide the onto count by $m^n$ to obtain the probability that every box is used; in the worked example it is $36/81=4/9$.
Exercise. How many assignments of four distinct balls to three distinct boxes use exactly two boxes? Hint: onto two boxes excludes the two constant assignments. Answer: $\binom32(2^4-2)=3\cdot14=42$. Together with $3$ assignments using one box and $36$ using all three, this gives $81$.
9.6 Crosscut theorem and applications
Optional graduate extension. This section is not required for the chapter foundation. A finite lattice is a poset in which each pair has a least upper bound, its join $x\vee y$, and a greatest lower bound, its meet $x\wedge y$. Write $\hat0$ and $\hat1$ for its bottom and top. An atom is an element covering $\hat0$, meaning that no element lies strictly between them. Planned Section 17.7 develops incidence algebras and generalized inversion; see the series roadmap.
We use the atom form of the crosscut theorem: if $A$ is the set of atoms of a finite lattice $L$, then
$$ \mu(\hat0,x)=\sum_{\substack{S\subseteq A\\\bigvee S=x}}(-1)^{|S|}, \qquad \bigvee\varnothing=\hat0. $$
This form is stated as Theorem 1.3 in Blass and Sagan, Möbius functions of lattices. It does not require every element to be a join of atoms. arxiv.org
Proof mechanism. Call the proposed right side $h(x)$, and let $A_y$ be the atoms below $y$. A subset has join at most $y$ exactly when all its atoms lie below $y$. Therefore
$$ \sum_{x\le y}h(x)=\sum_{S\subseteq A_y}(-1)^{|S|}. $$
For $y=\hat0$ this is $1$. For $y>\hat0$, finiteness supplies an atom below $y$, making the sum zero. These are the defining cumulative equations for $\mu(\hat0,x)$, so uniqueness proves the formula.
Worked example. In the divisor lattice of $30$, join is least common multiple and the atoms are $2,3,5$. Only their full set has join $30$, giving $\mu(1,30)=(-1)^3=-1$. In the divisor lattice of $12$, the atoms are $2,3$; even their full join is only $6$. No atom subset joins to $12$, so $\mu(1,12)=0$, agreeing with Section 9.4.
The application is computational: replace interval recursion with an alternating sum over atom subsets. This may be convenient when joins are easy to compute, though a lattice with many atoms still requires many subsets.
Exercise. In the three-element chain $\hat0\lt a\lt\hat1$, compute $\mu(\hat0,\hat1)$ by both methods. Hint: its only atom is $a$. Answer: no atom subset joins to $\hat1$, so the crosscut sum is zero; recursion gives $-(1-1)=0$.
9.7 Möbius functions of subset and partition lattices
Optional advanced extension. Sections 17.6 and 17.7 in the series roadmap provide fuller lattice and incidence-algebra treatments. Here we derive the coefficients directly from finite cancellation.
The Boolean lattice on a finite set $E$ consists of all its subsets ordered by inclusion. For $U\subseteq V$,
$$ \mu(U,V)=(-1)^{|V\setminus U|}. $$
Indeed, summing over intermediate subsets gives $(1-1)^{|V\setminus U|}$, the required interval cancellation. For $U=\{1\}$ and $V=\{1,2,3\}$, the four coefficients from $U$ to the intermediate subsets are $1,-1,-1,1$, summing to zero.
The partition lattice $\Pi_n$ consists of set partitions of $[n]$, ordered by refinement: $\pi\le\sigma$ means each block of $\pi$ lies inside a block of $\sigma$. Its bottom has all singleton blocks, and its top has one block. For $n\ge1$,
$$ \mu_{\Pi_n}(\hat0,\hat1)=(-1)^{n-1}(n-1)!. $$
The bottom-to-top formula appears as Equation 10.1 in Björner and Stanley's A Combinatorial Miscellany. math.mit.edu
More generally, let $r_B$ be the number of blocks of $\pi$ contained in a block $B$ of $\sigma$. Then
$$ \mu(\pi,\sigma)=\prod_{B\in\sigma}(-1)^{r_B-1}(r_B-1)!. $$
The interval separates into independent partition lattices on those groups of blocks; the Möbius function of a product is the product of the factors.
Here is a cancellation proof for the bottom-to-top formula. Give a partition $\tau$ weight
$$ w(\tau)=\prod_{B\in\tau}(-1)^{|B|-1}(|B|-1)!. $$
A block of size $r$ has $(r-1)!$ cyclic orders. Summing these weights over partitions of $[r]$ therefore sums $(-1)^{r-\operatorname{cyc}(\pi)}$ over permutations. Chapter 8's cycle polynomial makes this sum $1$ for $r=1$ and $0$ for $r\ge2$. For any partition $\sigma$, the sum over refinements factors over its blocks. It is $1$ only for the singleton partition and zero otherwise, proving the Möbius recursion for $w$.
Worked example. In $\Pi_3$, the bottom is $1|2|3$, the middle elements are $12|3$, $13|2$, and $23|1$, and the top is $123$. Their bottom-based Möbius values are $1$, three copies of $-1$, and $2$, since $1-3+2=0$. The value $2$ shows why general inversion needs more than alternating signs.
Exercise. Let $\pi=1|2|3|4$ and $\sigma=12|34$. Find $\mu(\pi,\sigma)$. Hint: each of the two final blocks merges two initial blocks. Answer: $(-1)(-1)=1$. In contrast, merging all four into one block gives $(-1)^3 3!=-6$.
9.8 Chromatic polynomials via inclusion-exclusion
A finite simple graph $G=(V,E)$ has vertices $V$ and edges joining distinct pairs of vertices, with no repeated edges. A proper coloring with $q$ labeled colors assigns a color to every vertex so that the endpoints of each edge receive different colors. Planned Sections 15.1 and 15.5 develop graphs and coloring further; see the series roadmap. Only these definitions are needed here.
Start with all $q^{|V|}$ colorings, for a positive integer $q$. For each edge $e=uv$, let $A_e$ be the bad event that $u$ and $v$ have the same color. For $F\subseteq E$, satisfying all these equalities makes the color constant on each connected component of the spanning subgraph $(V,F)$. Write $c(F)$ for its number of components, including isolated vertices. Components independently choose colors, so the intersection has size $q^{c(F)}$.
The sieve gives the chromatic polynomial
$$ P_G(q)=\sum_{F\subseteq E}(-1)^{|F|}q^{c(F)}. $$
This is a polynomial with integer coefficients whose value counts proper colorings at every positive integer $q$. The edge-subset expansion is also presented in Jeff Hicks's notes on the chromatic complex. math.berkeley.edu
Worked example. Let $G$ be the triangle on vertices $1,2,3$. Its edge subsets contribute:
| Selected edges | Number of subsets | Components $c(F)$ | Total signed contribution |
|---|---|---|---|
| None | 1 | 3 | $q^3$ |
| One | 3 | 2 | $-3q^2$ |
| Two | 3 | 1 | $3q$ |
| Three | 1 | 1 | $-q$ |
Thus $P_G(q)=q^3-3q^2+2q=q(q-1)(q-2)$. Direct coloring agrees: choose the first color in $q$ ways, the second in $q-1$, and the third in $q-2$. The three-edge subset still has one component; its equality constraints are redundant. Replacing $c(F)$ by $|V|-|F|$ would fail when $F$ contains a cycle.
The formula also gives $P_G(q)=q^{|V|}$ for an edgeless graph and a leading coefficient of $1$ for every simple graph. Every nonempty edge subset has fewer than $|V|$ components.
For a Möbius interpretation, form the poset $L_G$ of partitions whose blocks induce connected subgraphs, ordered by refinement. Each $F$ produces its connected-component partition. Grouping the signed edge-subset terms by that partition gives
$$ P_G(q)=\sum_{\pi\in L_G}\mu_{L_G}(\hat0,\pi)q^{|\pi|}. $$
To see the coefficient, sum the grouped weights over partitions refining $\pi$. This sums $(-1)^{|F|}$ over all edges internal to its blocks, giving $(1-1)^a$, where $a$ is their number. It is $1$ at the singleton partition and zero at every other element of $L_G$, exactly the Möbius recursion. This interpretation appears in Stanley's Enumerative Combinatorics, Volume 1, Exercise 3.108. math.mit.edu
Use the Möbius function of $L_G$, not automatically that of the full partition lattice. For a complete graph the two posets coincide; for a general graph they need not.
Exercise. Find the chromatic polynomial of the path with edges $12$ and $23$. Hint: its four edge subsets have component counts $3,2,2,1$. Answer: $q^3-2q^2+q=q(q-1)^2$. With three colors there are $12$ proper colorings.
Compute a Möbius function and recover a counting formula
The sieve and the chromatic polynomial are the same calculation with different bad events. For assignments, an intersection fixes selected job–machine pairs; for colorings, it forces equality along selected edges. Boolean-lattice coefficients provide the alternating signs. Grouping equivalent constraints can replace those signs by a different poset's Möbius coefficients, such as the value $2$ at the top of $\Pi_3$.
One application is scheduling tasks into labeled time slots. Put an edge between tasks that cannot share a slot. Proper colorings count feasible schedules when slots have no capacity limit and conflicts are pairwise. If instead each task must use a distinct resource and some task–resource pairs are forbidden, use the permutation-board model. Defining the assignment rules determines which counting formula applies.
Compute a Möbius function and recover a counting formula
Inputs. Use the board $B=\{(1,1),(1,2),(2,2)\}$ on three labels; four distinct balls and three distinct boxes; and the triangle graph. For the poset calculation use the five partitions of $\{1,2,3\}$ ordered by refinement.
- Sieve warm-up, 5 points. Compute $S_0,S_1,S_2,S_3$ for the forbidden board and recover its valid count. Hint: shared rows or columns make an intersection empty. Worked solution: the values are $6,6,1,0$, so the count is $1$. Identify $312$ as the unique valid assignment.
- Möbius calculation, 5 points. Compute $\mu(\hat0,\pi)$ for each element of $\Pi_3$. Verify the cumulative sum below each non-bottom element is zero. Worked solution: the bottom has value $1$, each of the three pair-merge partitions has value $-1$, and the top has value $2$. At a middle element the sum is $1-1=0$; at the top it is $1-3+2=0$.
- Recover a coloring formula, 5 points. Group the triangle's edge subsets by their component partitions. Worked solution: the empty subset contributes $q^3$; each one-edge subset contributes $-q^2$; the three two-edge subsets and the three-edge subset all have the top partition and contribute $(3-1)q$. Hence $P_G(q)=q^3-3q^2+2q$. Explain why this top coefficient equals the Möbius value computed in Task 2.
- Proof of cancellation, 5 points. Prove either the general sieve by following one object with $t$ violations or the Möbius upper-sum inversion by substituting $g(y)=\sum_{z\ge y}f(z)$. Solution outline: in the first proof the surviving weight is $(1-1)^t$; in the second it is the interval sum $\sum_{x\le y\le z}\mu(x,y)$, which vanishes unless $x=z$. State the finite-set or finite-poset hypothesis.
- Independent checks, 5 points. Enumerate the six board permutations, the $3^4=81$ occupancy functions, and the $3^3=27$ triangle colorings. For occupancy, tabulate by the number of used boxes; for coloring, reject any assignment with equal colors on an edge. Solution check: the board has one valid permutation; occupancy counts are $3,42,36$ for one, two, and three used boxes; the triangle has six proper three-colorings. Compare $36$ with $3!S(4,3)$ and $6$ with $P_G(3)$.
Optional crosscut extension. In $\Pi_3$, the atoms are the three pair-merge partitions. Any two atoms join to the top, as do all three. The atom crosscut sum is therefore $\binom32-\binom33=2$, recovering the top Möbius value without interval recursion.
Optional exploration. Replace the triangle by the three-vertex path. List its connected partitions and compute their Möbius values. Solution outline: they are $1,-1,-1,1$, giving $q^3-2q^2+q$. Compare with the full partition lattice and explain why its coefficient $2$ would be inappropriate here. You may then explore larger boards or graphs, reporting finite tables as evidence and supplying cancellation arguments for any general claims.
Deliverables and rubric. Submit the intersection table, the five Möbius values with interval checks, the grouped coloring polynomial, one proof, and the enumeration totals or a reproducible trace. Each task earns two points for correct results, two for reasoning or a reproducible method, and one for the specified validation. Total: 25 points; optional extensions are not required for full credit. Exhaustive small cases verify examples, while the proofs establish the formulas for all stated finite inputs.
Next in the Series
In Chapter 10: Generating Functions and Recurrence Relations, we'll explore Translate recursive structure into algebra and extract exact counts.