This summer, I taught at MathILy-Er for the first time. (In previous years, I taught at MathILy.) It is a joyful place to do math; the students are lovely and only occasionally get on my nerves.

Every summer, MathILy[-Er] is where go to I disconnect myself from the outside world and focus on nothing but math (and the “levity” infused within). This year, I couldn’t disconnect— I woke up every morning to an inescapable awareness of the still-ongoing genocide of Palestinians, and of my own unwilling complicity in it.

That is to say: I’m here to talk about cool math things, but in doing so I must also acknowledge the political realities of the world that cool math things exist within. It would be silly of me to pretend that my appreciation of artistic, mathematical “beauty” can somehow be divorced from my human-ness. That is to say: free Palestine.

In the meantime, let’s do a little math.

what is a Catalan?

The MathILy-Er students love to build staircases using rectangular brownies. In particular, they wish to build a $n$-step staircase using exactly $n$ rectangular brownies (of arbitrary size); how many ways are there to do so?

Here are two examples of brownie-staircases with size $n=4$:

(figure figure)

First, note that there are $n$ brownies and $n$ staircase nooks, so the rectangular shape of each brownie forces each brownie to occupy exactly one nook:

(figure)

Then, a nice way to count brownie-staircase configurations is to categorize them according to which brownie occupies the lower-left corner of the staircase:

(brownie)

This brownie “cleaves” the staircase into two smaller staircases: one above and the other to the right of the cleaver-brownie. And in particular, if the cleaver-brownie occupies the $k$-th nook, then:

• the above sub-staircase has size $k-1$, and
• the right sub-staircase has size $n-k$.

Let’s call $Bₙ$ is the number of brownie-staircases of size $n$. Then there are $Bₖ₋₁$ possible ways to build the above brownie-staircase, and $Bₙ₋ₖ$ possible ways to build the right brownie-staircase, and so overall there are $Bₖ₋₁⋅Bₙ₋ₖ$ possible combinations.

There are $n$ different cases, one for each possible cleaver-nook position $k$. So the total number of brownie-staircase configurations is

Let’s use this recurrence to calculate a few terms of the sequence:

This sequence is sometimes called the Catalan sequence.

And, just to demonstrate, here are all the brownie-staircases of size $n=4$, categorized according to cleaver-nook position:

(fig)

roller-coasters, a.k.a. parenthesequences

An amusement park wants to build a roller-coaster by assembling a sequence of tracks. There are two types of tracks, called up and down tracks:

• up tracks move the roller-coaster one step forward and up;
• down tracks move the roller-coaster one step forward and down.

The roller-coaster has to start and end at ground level (i.e., there must be equally many up and down tracks), and at no point in the middle can the roller-coaster dip below ground level. Here are examples of two valid roller-coasters, plus one example of an invalid roller-coaster for good measure:

(figure)

If there are $n$ up/down tracks each, how many ways are there to arrange them into valid roller-coasters?

Consider the first chunk of the roller-coaster, before it returns to ground level for the very first time. This chunk necessarily begins with an up track and ends with a down track; between them is an elevated, $1$-high platform that cleaves the roller-coaster into two parts:

• one part that rests atop the platform, and
• the rest of the roller-coaster, after the end of the platform.

(figure)

If the chunk consists of $k$ up/down track pairs, then the inner/above part has $k-1$ pairs, and the after/right part has $n-k$ pairs…

roller-coasters are brownie-staircases?

recursive-descent parsing

doing math with TikZ