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.
There are 6 types with 3 pieces, so we say the 3rd 'Schröder number' is 6.
It turns out these numbers are related to trees... and an operad!
(1/n)
The Schröder numbers Sₙ go like this:
1, 2, 6, 22, 90, 394, 1806, 8558, ...
For example, S₄ = 22 since there are 22 types of guillotine partition of a square into 4 pieces, 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.
You can read about Schröder numbers here:
https://en.wikipedia.org/wiki/Schr%C3%B6der_number
(2/n)
@johncarlosbaez is there an easy way to see why this agrees with the number of lattice paths definition given in the wikipedia article you linked? the article itself doesn't explain why they are equal.
@herid - I'm busy writing this series of posts now, so either someone else can tackle that or I'll try it later! All these things must be in Stanley's book "Enumerative Combinatorics".