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

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

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

c.(i) Find a reccurence for $\displaystyle 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?