This is [A168049][1] or, with slightly different indexing, the [Motzkin numbers][2]. The general question of counting nondecreasing sequences which stay below the diagonal is very common in combinatorics and goes by the name Lukasiewicz words. Stanley has a good discussion Enumerative Combinatorics II, Sections 5.3 and 5.4 and I [wrote up some notes][3] when I taught this material last Fall. In general, to count Lukaswiecz sequences from $(0,0)$ to $(n,n)$, one uses the generating function relation $$P = x W(P(x))$$ where $W = \sum w_k x^k$ and sequences are counted with weight $w_0^{a_0} \cdots w_i^{a_i}$, where $a_i$ is the number of times you increase by $i$. In your case, you want to permit increases by $(0,1,2)$, and not keep track of how many of each you are using, so you want to look at $$P = x(1+P+P^2)$$ which has the solution $P(x) = (-1 + x + \sqrt{1 - 2 x - 3 x^2})/(2 x)$. Unlike the Catalan case, I don't think you can get any simpler than this. To make my notes match up with your indexing, discard the final $2$ from your sequence, and take your $n_i$ to be my $d_i$, if I am not mistaken. To add a bit of self promotion, call your sequence $a(n)$. It starts out $1$, $1$, $2$, $4$, $9$, $21$, $51$ ... Define $b(n)$ so that $a(n) = b(n) + b(n+1)$. So the $b$'s start out $1$, $0$, $1$, $1$, $3$, $6$, $15$, $36$ ... That sequence is [A005043][4] and I [blogged about it][5]. [1]: http://oeis.org/A168049 [2]: http://oeis.org/A001006 [3]: http://www.math.lsa.umich.edu/~speyer/LagrangeInversion.pdf [4]: http://oeis.org/A005043 [5]: http://sbseminar.wordpress.com/2010/10/06/a-peculiar-numerical-coincidence/