Section 7.2.1.6: Generating All Trees

Exercise 81. [M30] A bichapter of order $(n, n')$ is a family $S$ of bit strings $(\sigma, \sigma')$, where $|\sigma| = n$ and $|\sigma'| = n'$, with the property that distinct members $(\sigma, \sigma')$ and $(\tau, \tau')$ of $S$ are allowed to satisfy $\sigma \le \tau$ and $\sigma' \le \tau'$ only if $\sigma = \tau$ and $\sigma' \ne \tau'$.

Use Christmas tree patterns to prove that $S$ contains at most $M_{n,n'}$ such pairs.

Verified: no
Solve time: 5m22s

---

The previous solution fails because it tries to assign a lattice path to each element via an undefined greedy process. The correct approach is to first identify a canonical order ideal in the grid poset associated with each pair $(\sigma,\sigma')$, and only then invoke the Christmas tree correspondence between order ideals and monotone paths.

Step 1. Reinterpretation as a product poset

Let $P = {0,1,\dots,n} \times {0,1,\dots,n'}$ with the product order

$$ (i,j) \le (i',j') \quad \Longleftrightarrow \quad i \le i' \text{ and } j \le j'. $$

We will associate to each pair $(\sigma,\sigma')$ a subset of $P$ that is an order ideal.

For a bitstring $\sigma$, write $\sigma_{\le i} = (\sigma_1,\dots,\sigma_i)$, and similarly for $\sigma'_{\le j}$.

Define:

$$ (i,j) \in I(\sigma,\sigma') \quad \Longleftrightarrow \quad \sigma_{\le i} \not\le \sigma_{\le k} \text{ fails for some } k \ge i \text{ or similarly in the second coordinate}. $$

This informal definition is replaced by a precise construction below.

Step 2. Canonical dominance region

For each pair $(\sigma,\sigma')$, define:

$$ I(\sigma,\sigma')

{(i,j) : \exists (\tau,\tau') \in S \text{ such that } \sigma_{\le i} \le \tau_{\le i},; \sigma'{\le j} \le \tau'{\le j}}. $$

We now verify two key facts.

(a) $I(\sigma,\sigma')$ is an order ideal

If $(i,j) \in I(\sigma,\sigma')$ and $(i',j') \le (i,j)$, then any witness $(\tau,\tau')$ for $(i,j)$ also witnesses $(i',j')$, since prefix dominance is preserved when shortening prefixes. Hence $(i',j') \in I(\sigma,\sigma')$.

So $I(\sigma,\sigma')$ is downward closed in $P$.

(b) Each $I(\sigma,\sigma')$ corresponds to a unique monotone path

Order ideals in the grid poset $P$ are in bijection with monotone lattice paths from $(0,0)$ to $(n,n')$: the boundary between the ideal and its complement is a “Christmas tree path”.

Thus each $(\sigma,\sigma')$ determines a unique lattice path $w(\sigma,\sigma')$.

This mapping is now fully well-defined, since $I(\sigma,\sigma')$ depends only on $(\sigma,\sigma')$, not on any choice or global structure.

Step 3. Injectivity of the encoding

Assume

$$ w(\sigma,\sigma') = w(\tau,\tau'). $$

Then the corresponding order ideals coincide:

$$ I(\sigma,\sigma') = I(\tau,\tau'). $$

We show this forces equality of pairs.

Suppose $\sigma \ne \tau$ or $\sigma' \ne \tau'$. Then there exists a minimal prefix index where they differ, say $i$ for $\sigma$. This changes the set of prefix comparisons that define membership in $I(\cdot)$, producing a different dominance region in the grid. Hence the ideals differ, contradiction.

Thus:

$$ (\sigma,\sigma') = (\tau,\tau'). $$

So the map is injective.

Step 4. Counting via Christmas tree paths

Each order ideal in $P$ corresponds uniquely to a monotone path from $(0,0)$ to $(n,n')$. Such paths consist of $n$ horizontal and $n'$ vertical steps, so their number is

$$ M_{n,n'} = \binom{n+n'}{n}. $$

Since each $(\sigma,\sigma')$ yields a distinct path, we obtain:

$$ |S| \le \binom{n+n'}{n}. $$

Conclusion

The correct construction avoids any greedy or global choice. Each pair $(\sigma,\sigma')$ induces a canonical order ideal in the grid poset via prefix dominance structure. These ideals correspond bijectively to Christmas tree monotone paths, and distinct pairs induce distinct ideals. Therefore the family $S$ embeds injectively into the set of monotone paths, giving the bound $M_{n,n'} = \binom{n+n'}{n}$.