TAOCP 7.2.2.1 Exercise 185
A strict exact cover problem consists of options, each option containing exactly one primary item and any number of secondary items, such that every primary item is covered exactly once and each secon...
Section 7.2.2.1: Dancing Links
Exercise 185. [M22] What is the largest number of solutions to a strict exact cover problem that has $N_1$ primary items and $N_2$ secondary items?
Verified: no
Solve time: 1m31s
Solution
A strict exact cover problem consists of options, each option containing exactly one primary item and any number of secondary items, such that every primary item is covered exactly once and each secondary item is covered at most once.
Let $S$ be the set of all solutions. Each solution consists of a choice of exactly one option for each primary item, subject to the constraint that no secondary item appears in more than one chosen option.
Upper bound
For each secondary item $x$, examine a fixed solution $\mathcal{T} \in S$. Exactly one of the following holds: either $x$ appears in one of the chosen options, or it appears in none. If it appears, it is contained in the unique option chosen for a unique primary item.
Define a function
$f_{\mathcal{T}}(x) \in {0,1,\dots,N_1}$
by setting $f_{\mathcal{T}}(x)=0$ when $x$ is not covered by any chosen option, and setting $f_{\mathcal{T}}(x)=i$ when $x$ is contained in the chosen option for primary item $i$.
This produces a well-defined function
$f_{\mathcal{T}} : {\text{secondary items}} \to {0,1,\dots,N_1}.$
If two solutions $\mathcal{T}_1$ and $\mathcal{T}2$ satisfy $f{\mathcal{T}1} = f{\mathcal{T}_2}$, then for each primary item $i$, the set of secondary items assigned to $i$ is identical in both solutions. Each chosen option in a solution is uniquely determined by the primary item together with the set of secondary items it contains, so equality of all these assigned sets forces identical collections of chosen options. This yields $\mathcal{T}_1 = \mathcal{T}2$, hence the mapping $\mathcal{T} \mapsto f{\mathcal{T}}$ is injective.
The number of such functions is $(N_1+1)^{N_2}$, so
$|S| \le (N_1+1)^{N_2}.$
Construction achieving the bound
Construct a strict exact cover instance as follows. Let the primary items be $1,2,\dots,N_1$ and the secondary items be $x_1,\dots,x_{N_2}$. For every primary item $i$ and every subset $A \subseteq {x_1,\dots,x_{N_2}}$, include the option
${i} \cup A.$
No secondary item appears in more than one chosen option in any valid solution only when the subsets chosen for different primary items are disjoint, and every secondary item belongs either to exactly one chosen subset or to none. Each solution therefore induces an assignment of each secondary item to exactly one of the $N_1$ primary items or to no primary item.
Conversely, given any function
$f : {x_1,\dots,x_{N_2}} \to {0,1,\dots,N_1},$
define $A_i = {x_j : f(x_j)=i}$. The option ${i} \cup A_i$ exists by construction for each $i$, and these options form a valid exact cover since the sets $A_i$ are disjoint by definition. This yields a solution, and different functions produce different solutions.
Thus the number of solutions equals the number of such functions, namely $(N_1+1)^{N_2}$.
Conclusion
Both the upper bound and the construction coincide, giving the maximal possible number of solutions:
$\boxed{(N_1+1)^{N_2}}.$
This completes the proof. ∎