Counting sequences using Catalan Numbers

337 Views Asked by At

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.

2

There are 2 best solutions below

0
On

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.

0
On

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}. $$