The n-Category Café

Last night I had insomnia, worrying about my aunt in a nursing home. To lull myself to sleep I thought about math. I had an idea about guillotine partitions.

In a ‘guillotine partition’ of a square you repeatedly slice off and remove rectangular pieces by cutting vertically or horizontally all the way through what’s left:

• Wikipedia, Guillotine partition.

There are 6 types of guillotine partition where you make 2 cuts, so we say the 2nd Schröder number is 6:

The first few Schröder numbers $S_n$ go like this:

$$S_0 = 1$$ $$S_1 = 2$$ $$S_2 = 6$$ $$S_3 = 22$$

etc. For example, $S_3 = 22$ since there are 22 types of guillotine partition of a square with 3 cuts, as shown below:

We can arrange it so the cuts always go through equally spaced points lying on a diagonal line. This is a cheap way to make the idea of ‘type’ precise: we only count guillotine partitions with this property.

(It’s probably better to define a ‘type’ of guillotine partition as an equivalence class under a certain equivalence relation. Briefly: if you start with a guillotine partition, and move a horizontal cut up or down without it hitting another horizontal cut, or move a vertical cut right or light without it hitting another vertical cut, you get a guillotine partition of the same type. The trick with equally spaced points is just a way to choose one representative guillotine partition of each type.)

You can read more about the Schröder numbers here:

• Wikipedia, Schröder number.

If we demand that the first cut be vertical we get half as many guillotine partitions… except when there are no cuts at all. This gives the ‘little Schröder numbers’:

$$x_0 = 1$$ $$x_1 = 1$$ $$x_2 = 3$$ $$x_3 = 11$$

etc. For example if we take the guillotine partitions with 3 cuts, and cross out those where the first cut is horizontal, we’re left with 11 of them:

You can read about the little Schröder numbers here:

• Wikipedia, Schröder–Hipparchus number.

The little Schröder numbers are now also called ‘Schröder–Hipparchus numbers’, because sometime between 50 and 120 AD Plutarch wrote:

Chrysippus says that the number of compound propositions that can be made from only ten simple propositions exceeds a million. Hipparchus, to be sure, refuted this by showing that on the affirmative side there are 103,049 compound statements….”

This was utterly mysterious until 1994, when David Hough, a math grad student, realized that 103,049 is the 9th little Schröder number!

Why was Hipparchus messing around with the little Schröder numbers around 150 BC?

It turns out the $(n-1)$st little Schröder number is also the number of planar trees with $n$ leaves where each node has 0, or 2, or 3, or 4, or 5, etcetera, children. Anything but one child!

For example this tree with 8 leaves is one of 4279 such trees, since the 7th little Schröder number, $x_7$, is 4279:

Hipparchus was probably studying such trees with 10 leaves! There are 103,049 of them.

But wait! Why is the nth little Schröder number both:

the number of types of guillotine partition of a square with $n$ cuts, where the first cut is vertical

and

the number of planar trees with $n+1$ leaves where each node has any number of children except 1

?

This is what I figured out in my bout of insomnia, after connecting little Schröder numbers to guillotine partitions.

Here’s a better way to phrase the question: why is

the number of types of guillotine partition of a square into $n$ rectangles, where the first cut is vertical

equal to

the number of planar trees with $n$ leaves where each node has any number of children except 1

?

There’s a nice bijective proof. Here’s how you can set up a 1-1 correspondence between such trees and such types of guillotine partitions:

Each node of your tree corresponds to a rectangle. The top node corresponds to the whole square you are partitioning. Then, when a node has $n$ children, you cut its rectangle into $n$ smaller rectangles using parallel lines any way you want. These are the node’s children.

As you work down the tree you first cut with vertical lines, then horizontal, then vertical, etc.

So, the first cuts are always vertical!

Using this correspondence, types of guillotine partitions of a square into $n$ rectangles where the first cut is vertical correspond to trees with $n$ leaves where each node that’s not a leaf has at least two children!

Almost a decade ago, I noticed that such trees are also operations in the free operad on one operation of arity 2, one operation of arity 3, etc. You could say this is the operad for ‘unbiased magmas’. I wrote about this here, and I called it the ‘Hipparchus operad’:

• John Baez, The Hipparchus operad, April 1, 2013.

This blog post was a ‘meta-April-fool’s joke’, since it was strange, with a few jokes thrown in, but true in all important respects.

The Hipparchus operad has nice connections to other branches of math, as discussed in comments. For example the little Schröder numbers count the trees appearing when you barycentrically subdivide Stasheff’s associahedra! There are 11 trees here:

Each of these trees gives a type of guillotine partition of the square where the first cut is vertical.

So, there’s a lot to play with here!

I’m hoping this will help us understand this problem:

• John Baez, Dividing a square into similar rectangles.

This only works for similar rectangles forming a guillotine partition of the square. But those are very interesting! For those, I think we just need to take a tree of the sort I’m describing, and label each leaf with ‘vertical’ or ‘horizontal’, to say whether that rectangle is tall and skinny, or short and squat. But some more thought is required.

This is the sort of thing that happens sometimes when I try to fall asleep by diverting my mind away from more unpleasant subjects. Does something like this happen to you too?

Anyway, I called my aunt today and she’s actually doing okay. I forgot to do it yesterday, on Christmas day. Aargh!!!

Sometimes I think pure math is just an elaborate trick to avoid confronting reality.

Acknowledgements

The pictures of guillotine partitions were drawn by Robertd and put on Wikicommons under a Creative Commons Attribution 3.0 Unported license. The picture of a tree is from Etienne Ghys’ article Quand beaucoup de courbes se rencontrent. The picture of a barycentrically subdivided Stasheff pentagon is from Tom Leinster’s book Higher Operads, Higher Categories.