MATH: Catalan sequence

By Bruno;

A few weeks ago, while having a preparatory class for the IMO, my teacher presented a very interesting solution for a problem from the USA TST (or the USAMO, I don't really remember the source), here you are the problem:

But don't worry, we aren't going to solve it(today), I will target my focus on the result of this nonsense sum. Have you already seen it? If yes, take a look at this post here: https://www.meepblogs.com/post/math-thue-s-lema-corollaries-and-a-few-consequences , because nothing here will be new for you (I guess); otherwise, it is the (n+1)-th term of the Catalan sequence. But for understanding it, you should know what a bijection is: in few terms, it is a correspondence of the form 1:1 between two sets X and Y.

The generic picture of two sets X and Y (clearly taken from google) in the left shows this correspondence: every element in X has exactly one correspondent in Y and vice versa.

Well, so let's define Catalan:

1)The n-th Catalan term is the total number of manners of opening and closing 2n parenthesis correctly matched. For example, for n=3 we use 6 parenthesis and

the possibilities are: ((())), ()()(), (())(), ()(()), (()()), but note that ()()(( is not possible, because the 5th parenthesis was not closed by the last one.

2)It is the total number of ways of cutting a convex polygon with n+2 sides into triangles

The cases n= 2,3 and 4 are shown in the generic picture in the left.

3) Consider a grid n by n where the points are the intersections of the horizontal line with the vertical lines, so the n-th Catalan term is the number of ways of going from A to B (only passing through the points of the grid) without being under the diagonal AB (you also can't move down or left)

The Image shows two wrong possibilities(don't consider the colors).

Anyway, all those ways of representing Catalan are bijections! In the first, we corresponded the sequence to the manners of matching parenthesis, in the second, we related Catalan to the ways of cutting polygons into triangles, and in the third, we interpreted it as the number of paths in the grid. Isn't awesome? I mean, it looks like my last post "One point, many properties". The title could even be "One sequence, many interpretations", but I think it would be quite repetitive... Anyway, I need solve a problem now, so see you next week!