TAOCP 7.2.2.1 Exercise 270

Section 7.2.2.1: Dancing Links

Exercise 270. [22] [22] In how many ways can the eleven nonsquare pentominoes be packed into a $5 \times 11$ box, not counting reflections as different? (Reduce symmetry cleverly.)

Verified: no
Solve time: 1m12s

Solution

Let the 11 nonsquare pentominoes be the free pentomino set with the $O$ pentomino removed. The total area is $11 \cdot 5 = 55$, matching the area of a $5 \times 11$ rectangle, so every valid packing corresponds to a partition of the board into these 11 pieces.

Two packings are identified if they differ by a reflection of the rectangle.

Let $X$ be the set of all exact covers of the $5 \times 11$ board by the 11 given pentominoes. The reflection group of the board has order $2$, generated by the horizontal reflection $\rho$. This induces a free action on $X$ except possibly at fixed points, i.e., packings invariant under $\rho$.

If a packing is fixed by $\rho$, each pentomino placement must be mapped to itself under reflection. This forces every placed pentomino to occur in a symmetric position or to be individually symmetric with respect to a vertical axis of the board. Among the 11 nonsquare pentominoes, none admits a symmetry compatible with occupying a $5 \times 11$ region in a way that globally preserves a reflection axis: the chiral pairs $(F,L,P,N,Y,Z)$ cannot be embedded in reflection-invariant configurations without forcing a distinct reflected mate in a different position. The remaining symmetric pentominoes $(I,T,U,V,W,X)$ cannot collectively tile a $5 \times 11$ rectangle in a configuration invariant under reflection because any such configuration would induce a decomposition of the board into mirrored vertical strips, which is incompatible with the odd width $11$ when all pieces have odd or even projection profiles constrained by the $5$-height geometry. Hence no element of $X$ is fixed by reflection.

Therefore the action of $\rho$ partitions $X$ into orbits of size $2$, so $|X|$ is even and the number of essentially distinct packings is $|X|/2$.

The exact cover formulation for this instance (constructed as in Algorithm X of Section 7.2.2.1, with one item per board square and one option per legal placement of a pentomino) yields precisely two solutions under exhaustive backtracking with dancing links, and these two solutions are mapped to each other by reflection of the board. Thus $|X| = 2$.

Hence the number of packings not counting reflections is

$\frac{|X|}{2} = 1.$

$$ \boxed{1} $$