How to count with Catalan numbers

Question

I am wondering, in general, how to show that the Catalan numbers can be used to count in a certain problem? For example, I would like to know how the Catalan number $C_n$ counts the number of ways to construct a regular n-step staircase with n rectangles. I think I could either construct a bijection between something that is known to be countable with Catalan numbers, or simply count the number of tilings and show that the formula is identical to that of the $n^{th}$ Catalan number, but I'm not sure what the best way to do this is.

Answer 1

There is a nice graphic illustration of this in the Wikipedia article on Catalan numbers. The key idea here is that in the triangular staircase when the corner rectangle is removed it leaves two smaller triangluar staircases which leads to the standard Catalan recursion. Of course, this requires some proof, but this approach is more immediate than searching for some bijection with another Catalan object and then having to prove that bijection.

Answer 2

Reading the OP's question it appears that they are interested in any circumstances where the Catalan numbers represent the count for a collection of mathematical objects. But regardless, any 'proof count' examples can only strengthen their understanding of how the Catalan numbers are used.

In the wiki article it is stated that

The Catalan number $C_n$ is the number of ways to form a "mountain range" with $n$ upstrokes and $n$ downstrokes that all stay above a horizontal line. The mountain range interpretation is that the mountains will never go below the horizon.

The article doesn't explicitly give a count proof for this manifestation, but the Second_proof is very close to the mechanics. Interestingly, the paper

Catalan Numbers
by Tom Davis

provides two methods of counting mountain ranges.

The following is almost a verbatim copy of one of Tom Davis' arguments.

Counting Mountain Ranges—Method $1$

If we completely ignore whether the path is valid or not, we have $n$ up-strokes that we can choose from a collection of $2n$ available slots. In other words, ignoring path validity, we are simply asking how many ways you can rearrange a collection of $n$ up-strokes and n down-strokes. The answer is clearly

$$\quad \binom{2n}{n}$$

Now we have to subtract off the bad paths. Every bad path goes below the horizon for the first time at some point, so from that point on, reverse all the strokes—replace up-strokes with downstrokes and vice-versa. It is clear that the new paths will all wind up $2$ steps below the horizon, since they consist of $n + 1$ down-strokes and $n − 1$ up-strokes. Conversely, every path that ends two steps below the horizon must be of this form (employ a 'reverse switch-em-up argument'), so it corresponds to exactly one bad path.

How many such bad paths are there? The same number as there are ways to choose the $n + 1$ down-strokes from among the $2n$ total strokes, or

$$\quad \binom{2n}{n+1}$$

Thus the count of valid mountain ranges, or $C_n$, is given by:

$$\tag 1 C_n = \binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}$$