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?