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
    $\begingroup$ This strikes me as a Dyck path that ends 7 above it's "ground level" if that makes sense $\endgroup$ – Phill Apr 19 '15 at 10:10
  • $\begingroup$ 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}$ ? $\endgroup$ – Astro Nauft Apr 19 '15 at 10:31
  • $\begingroup$ Or maybe (2015 choose 7)$\cdot C_{1004}$ $\endgroup$ – Astro Nauft Apr 19 '15 at 10:35
  • $\begingroup$ 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 $\endgroup$ – Phill Apr 21 '15 at 3:30
  • $\begingroup$ In principle though you should be able to work it out using Dyck paths, balls in bins and a bit of intuition $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.