TAOCP 7.2.2.1 Exercise 39

Section 7.2.2.1: Dancing Links

Exercise 39. ▶ [M21] $[M21]$ Experiment with exact cover problems that are defined by $m$ random options on $n$ items. (Each option is generated independently, with repetitions permitted.)

a) Use a fixed probability $p$ that item $i$ is included in any given option.

b) Let every option be a random sample of $r$ distinct items.

Verified: yes
Solve time: 1m23s

---

Solution

We study the expected number of exact covers in two random models of an $m \times n$ instance.

An exact cover corresponds to choosing a set $S$ of options such that every item is contained in exactly one option of $S$.

(a) Independent inclusion with probability $p$

Each option is generated by including each item independently with probability $p$.

Fix an integer $t$ and fix a subset $S$ of $t$ options. For a fixed item $i$, the event that $i$ is covered exactly once by $S$ means that exactly one of the $t$ options in $S$ contains $i$. Since inclusions are independent across options, this event has probability

$t p (1-p)^{t-1}.$

Independence across items follows from independence of item-inclusion across options, hence the probability that $S$ is an exact cover is

$\bigl(t p (1-p)^{t-1}\bigr)^n.$

There are $\binom{m}{t}$ choices for $S$, so the expected number of exact covers is

$$ \mathbb{E} = \sum_{t=0}^{m} \binom{m}{t} \bigl(t p (1-p)^{t-1}\bigr)^n. $$

(b) Random $r$-subsets without replacement within each option

Each option is a uniformly random subset of size $r$ from the $n$ items.

Let $t$ options be fixed. If they form an exact cover, every item appears in exactly one of the $t$ options, hence the total number of item occurrences is $tr$, so necessarily

$tr = n.$

Thus only $t = n/r$ can contribute, and this requires $r \mid n$.

Fix an ordered $t$-tuple of options. Each option is chosen independently uniformly among all $\binom{n}{r}$ subsets, so the total number of possible outcomes is

$\binom{n}{r}^t.$

The tuple forms an exact cover exactly when the $t$ chosen $r$-subsets form a partition of the $n$ items into $t$ labeled blocks of size $r$. The number of such ordered partitions is

$\frac{n!}{(r!)^t},$

since we permute all items and then split into consecutive blocks of size $r$.

Hence, for a fixed ordered $t$-tuple,

$$ \mathbb{P}(\text{exact cover}) = \frac{n!}{(r!)^t \binom{n}{r}^t}. $$

For a fixed unordered subset $S$ of $t$ options, the same probability applies to its ordered representation, and there are $\binom{m}{t}$ such subsets. Therefore the expected number of exact covers is

$$ \mathbb{E} = \begin{cases} \binom{m}{t} \dfrac{n!}{(r!)^t \binom{n}{r}^t}, & t = n/r,\[6pt] 0, & \text{otherwise}. \end{cases} $$

This completes the analysis of both random models. ∎