# 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.
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.