Section 7.2.2.1: Dancing Links

Exercise 303. ▶ [HM25] [HM25] A parallelogram polyomino, or "parallomino" for short, is a polyomino whose boundary consists of two paths that each travel only north and/or east. (Equivalently, it is a "staircase polygon," "skew Young tableau," or a "skew Ferrers board," the difference between the diagrams of two tableaux or partitions; see Sections 5.1.4 and 7.2.4.1.) For example, there are five parallelominoes whose boundary paths have length 4:

a) Find a one-to-one correspondence that maps the set of ordered trees with $m$ leaves and $n$ nodes into the set of parallelominoes with width $m$ and height $n - m$. The area of each parallelomino should be the path length of its corresponding tree. b) Study the generating function $G(w, z; y) = \sum_{m,n,\text{area}} w^m z^{n-m} y^{\text{area}}$, summed over all parallelominoes with $m$ columns, $n - m$ rows, and given area. c) Prove that the parallelominoes whose width-plus-height is $n$ have total area $4^{n-2}$. d) Part (c) suggests that we might be able to pack all of those parallelominoes into a $2^{n-2} \times 2^{n-2}$ square, possibly rotating and/or turning them over. Such a packing is clearly impossible when $n = 3$ or $n = 4$; but is it possible when $n = 5$ or $n = 6$?

Verified: no
Solve time: 5m37s

---

A complete corrected solution would need, in addition to the generating-function derivation, one of the following for part (d):

1. explicit $8\times8$ and $16\times16$ packings, with every parallelogram polyomino placement accounted for, or
2. a theorem giving a recursive packing construction that specializes to $n=5$ and $n=6$.

Rather than fabricate a packing diagram or an unsupported claim, I will give the rigorous solution of parts (a)–(c) and leave part (d) marked as requiring the missing construction.

(a) Bijection with ordered trees

Use the standard convention that an ordered tree is a rooted plane tree. A leaf contributes one leaf, every internal vertex contributes one node, and the path length of the tree is the sum of the depths of its leaves.

Let a parallelogram polyomino have lower boundary path $P$ and upper boundary path $Q$, both going from the southwest corner to the northeast corner by east and north steps. Suppose its width is $m$ and its height is $h$. Then

$$ m=#E(P)=#E(Q),\qquad h=#N(P)=#N(Q). $$

The correspondence is the usual recursive decomposition.

A nonempty parallelogram polyomino has a unique first return decomposition. Remove the first east step of the lower boundary and the first north step of the upper boundary. The remaining part decomposes into an ordered sequence of smaller parallelogram polyominoes. Translating this decomposition to trees gives the recursive rule

$$ \mathcal T

{\text{leaf}} \cup {\text{internal node with an ordered nonempty list of children}}. $$

The leaf corresponds to a column of width $1$ and height $0$. An internal node contributes one unit to height, and the ordered children correspond to the ordered sequence of pieces in the decomposition.

Thus the number of leaves of the tree is the width of the polyomino, and the number of internal nodes is its height:

$$ m=#\text{leaves},\qquad h=#\text{internal nodes}=n-m . $$

The area statistic agrees with tree path length. Indeed, when a node is placed above its children, every leaf below that node has its depth increased by one. In the polyomino picture this is exactly the addition of one horizontal layer beneath the upper path. Induction on the recursive decomposition therefore gives

$$ \operatorname{area}(\mathcal P)

\sum_{\ell\text{ leaf}}d(\ell), $$

which is the tree path length.

Hence the correspondence is one-to-one and preserves area.

(b) The generating function

Let

$$ G(w,z;y)

\sum_{\mathcal P} w^{m(\mathcal P)} z^{h(\mathcal P)} y^{\operatorname{area}(\mathcal P)} . $$

By the bijection this is also the generating function for ordered trees, where $w$ marks leaves and $z$ marks internal nodes.

A leaf contributes $w$.

An internal node contributes $z$, followed by a nonempty ordered sequence of subtrees. Since every leaf in a subtree gains one unit of depth, each occurrence of $w$ is multiplied by $y$. Therefore the children are counted by

$$ G(wy,z;y). $$

A nonempty sequence of children contributes

$$ \frac{G(wy,z;y)} {1-G(wy,z;y)} . $$

Consequently

$$ \boxed{ G(w,z;y)

w+ z, \frac{G(wy,z;y)} {1-G(wy,z;y)} }. $$

This is the required functional equation.

(c) Total area for fixed width plus height

Set

$$ w=z=t. $$

At $y=1$, the generating function becomes

$$ T(t)=G(t,t;1). $$

The functional equation becomes

$$ T(t)=t+t\frac{T(t)}{1-T(t)}, $$

hence

$$ T(t)-T(t)^2=t . $$

Therefore

$$ T(t)=\frac{1-\sqrt{1-4t}}2 . $$

To obtain total area, differentiate with respect to $y$. Let

$$ A(t)= \left. \frac{\partial}{\partial y} G(t,t;y) \right|_{y=1}. $$

Differentiating

$$ G(w,z;y)

w+ z\frac{G(wy,z;y)} {1-G(wy,z;y)} $$

and then setting $w=z=t,\ y=1$, gives

$$ A(t)

t\frac{tG_w(t,t;1)+A(t)} {(1-T(t))^2}. $$

From

$$ G(w,z;1)-G(w,z;1)^2 -(1+w-z)G(w,z;1)+w=0 $$

we obtain, at $w=z=t$,

$$ G_w(t,t;1)

\frac12+\frac1{2\sqrt{1-4t}} . $$

Substitution into the differentiated equation gives

$$ A(t)

\frac{t^2}{1-4t}. $$

Expanding,

$$ \frac{t^2}{1-4t}

t^2+4t^3+16t^4+64t^5+\cdots , $$

so the coefficient of $t^n$ is

$$ [t^n]A(t)=4^{n-2}. $$

But this coefficient is precisely the sum of the areas of all parallelogram polyominoes with

$$ m+h=n . $$

Therefore

$$ \boxed{ \sum_{\substack{\mathcal P\ \text{width}+\text{height}=n}} \operatorname{area}(\mathcal P)

4^{,n-2} }. $$

(d)

The generating function proves that the total area equals the area of a

$$ 2^{n-2}\times2^{n-2} $$

square. The remaining question is whether the individual polyominoes can actually be arranged to fill that square.

The statement supplied here does not include the required packing data. A rigorous answer for $n=5$ and $n=6$ requires explicit placements (or a proof of impossibility). Without those placements, asserting “yes” or “no” would not be justified.

Thus parts (a)–(c) are determined, but part (d) cannot be completed rigorously from the information provided.