# Catalan bijections in TikZ

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:

$B₀=1, \quad B₁=1, \quad B₂=2, \quad B₃=5, \quad B₄=14, \quad B₅=42, \quad \dotsc$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…