[seqfan] Re: Splitting the square into equal parts

[Elijah Beregovsky]

I’ve been thinking about your problem and here’s what I’ve thought up.
Every fixed partition of a square into k rectangles, if done with your
restrictions, corresponds to a certain ordered rooted tree with k leaves.
Let’s build a tree from an existing partition:
(1) A starting square corresponds to the root of your tree.
(2) Draw all m vertical lines that split the square. The m+1 rectangles
you‘ve got this way correspond to the children of the root, moreover, they
are ordered from left to right.
(3) Draw all horizontal line segments you can (each has to split exactly
one rectangle). New rectangles you’ve got by splitting a rectangle R
correspond to the children of the node associated with R, moreover, they’re
ordered from top to bottom.
(4) Draw all vertical line segments you can (each has to split exactly one
rectangle). New rectangles you’ve got by splitting a rectangle R correspond
to the children of the node associated with R, moreover, they’re ordered
from left to right.
(5) Alternate (3) and (4) until you’ve drawn every line segment.

For example, let’s find a tree associated with the partition 42 (Life,
Universe and Everything) from the illustration you’ve sent.
(1) A tree with no branches:
o
(2) Only one possible vertical line, so the tree looks like that:
(oo)
(3) Two horizontal lines in the right half:
(o(ooo))
(4) A vertical segment in the bottommost rectangle:
(o(oo(oo)))
(3) A horizontal segment in the left half of the last split:
(o(oo((oo)o)))

Or for partition 65:
(1) Root only:
o
(2) Two vertical lines:
(ooo)
(3) Every rectangle gets split in half:
((oo)(oo)(oo))

Starting with a tree you could also make a square partition, using the same
algorithm, pretty much. You just have to make the size of a rectangle
proportional to the number of leaves hanging from the corresponding node.
For example, building the partition 42 from (o(oo((oo)o))), you make the
first split one sixth of the starting square's sidelength from the left
side, then you make two horizontal splits one fifth and two fifths from the
top side in the right half of the square and so on.
There's several problems with this, however. First, a tree that could
conceivably be produced from a partition has to be homeomorphically
irreducible, as each splitting gives you two or more rectangles, and the
only case when it can be different is the first split: you could start with
a partition that has no legal vertical lines for the first move, number 62,
for instance. Its tree is, thus, (((oo)(o(oo)o))). Second, in some cases
even a tree, valid by the first restriction cannot be produced. For
instance, ((oo)((oo)(oo))) can be translated into the partition 65, but as
we already know, this one produces ((oo)(oo)(oo)). This confusion is a
result of vertical and horizontal lines crossing. I strongly believe,
though I haven't rigorously proven it, that this can be remedied by
prohibiting a non-root node to have branches with non-coprime numbers of
leaves. A handwavy explanation of this restriction is that due to the
proportionality of the rectangle sizes and leaf counts, if the leaf counts
of the branches are not coprime, there'll be segments that share endpoints,
which makes them ONE segment that had to be drawn on one of the previous
iterations.

So, yeah, you're actually counting homeomorphically irreducible ordered
rooted trees, all non-root branches of which have coprime leaf-counts. I
hope that helps  :)

Best wishes,
Elijah Beregovsky

PS: counting one-sided and free partitions this way is a lot harder, due to
the weird symmetries the system exibits