## Catalan Numbers

Let $T_{n}$ be the number of integer sequences $a_{1}, a_{2},...a_{n}$ satisfying $a_{1}$ $a_{2}$ ≤ ... ≤ $a_{n}$ and $a_{1}$ ≤ 1, $a_{2}$ ≤ 2, ..., $a_{n}$ ≤n.

a. Show all possible such sequences for n = 1, n=2, and n =3.

b.(i) Find an explicit formula for $T_{n}$. (ii) Justify your answer.

c.(i) Find a reccurence for $T_{n}$. (ii) Justify your answer.

I can two part a. B is just clearling the Catalan number, but justifying it is a little hard. I guess the best way would be to draw a 1-1 correspondence with the number of +1's and -1's in a permutation, anyone able to help me with this?