Let be the number of integer sequences satisfying ≤ ≤ ... ≤ and ≤ 1, ≤ 2, ..., ≤n.

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

b.(i) Find an explicit formula for . (ii) Justify your answer.

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