# Counting sequences using Catalan Numbers

Count the number of sequences $a_{1},...,a_{2015}$ such that:

$a_{i}\in \{-1,1\}$, and $\sum _{i=1} ^ {2015} a_{i}=7$, and $\sum _{i=1} ^{j} a_i >0$ for every $1\leq j\leq 2015$

I assume we have to use Catalan numbers somehow.

It's clear that the number of $1$'s = number of $-1$'s $+7$. From the third condition it's also clear that the sequence must start with $1$. Beyond that, I can't see how to proceed from here.

• This strikes me as a Dyck path that ends 7 above it's "ground level" if that makes sense – Phill Apr 19 '15 at 10:10
• basically it's like a balanced sequence (same number of positive and negative elements) after we choose where to put some $7$ ones. So maybe it's (2015 choose 7) $\cdot C_{2008}$ ? – Astro Nauft Apr 19 '15 at 10:31
• Or maybe (2015 choose 7)$\cdot C_{1004}$ – Astro Nauft Apr 19 '15 at 10:35
• I've deleted my answer because of what you pointed out and because I don't have the time right now to edit it correctly. Perhaps I'll leave it for someone else to attempt – Phill Apr 21 '15 at 3:30
• In principle though you should be able to work it out using Dyck paths, balls in bins and a bit of intuition – Phill Apr 21 '15 at 3:33

Use the reflection principle. Clearly $a_1 = 1$, so we can instead count the number of paths $a_1,\ldots,a_{2014}$ which sum to $6$ whose partial sums are always non-negative. Using the reflection principle, we find that the number of these paths is $$\binom{2014}{1010} - \binom{2014}{1003}.$$ More generally, if $2015$ is replaced by $n+1$ and $7$ is replaced by $t+1$, the answer is $$\binom{n}{(n+t)/2} - \binom{n}{(n-t)/2-1} = \\ \binom{n}{(n+t)/2} - \binom{n}{(n+t)/2+1} = \\ \binom{n}{(n+t)/2} \left(1 - \frac{(n-t)/2}{(n+t)/2+1} \right) = \\ \frac{t+1}{(n+t)/2+1} \binom{n}{(n+t)/2}.$$
Using your idea of "a balanced sequence and a choice of where to put seven 1s" we get the following: $$\sum_{i_1 + \cdots + i_7 = 1004} C_{i_1} \cdots C_{i_6}$$
where $i_1,\dotsc,i_6 \geq 0$ (there are six of them because we are forced to put the first one in position one, as you noted). That's a sum over $997 \choose 5$ terms though.