0
$\begingroup$

Question: Find a recurrence for the number $h_n$ of sequences of length $2n$ of $+1$'s and $-1$'s such that: every partial sum is non-negative, and the entire sum is zero.

I tried to consider the possible last two entries of the sequence and consider them separately. There are four possibilities, the sequence ends in $-1$,$-1$ or $+1$,$+1$ or $-1$,$+1$ or $+1$,$-1$. For each, this necessarily means, to ensure that the entire sum is zero, that there must be two $1$'s of the exact opposite sign that came before. So we must choose where those two opposite singed $1$'s go. For example, for the sequence ending in $-1$,$-1$, there must be two $+1$'s somewhere in the first $2n-2$ positions, and the rest reduces down to $h_{n-4}$, so we have ${{2n-2} \choose 2} \cdot h_{n-4}$ sequences that end in $-1$,$-1$. I am unsure how to do the other 3 cases, mainly because there will at least be a $-1$ that i need to put in the previous entries, and I cannot just put it anywhere because the partial sums might not all be non-negative. In the previous case that I did, I am free to choose wherever to put the $+1$'s because they will not make any partial some negative. I am unsure if all this is the right approach. Help is appreciated.

$\endgroup$
  • 3
    $\begingroup$ This is one characterization of the Catalan Numbers $\endgroup$ – lulu Jul 17 '17 at 20:39
  • $\begingroup$ Your sequence cannot end in $+1$ because the sum before that would be $-1$ $\endgroup$ – Ross Millikan Jul 17 '17 at 20:54
0
$\begingroup$

As @lulu notes, these are the Catalan numbers. Here's a sketch for finding recurrence relation for them:

Consider the first time $2k$ for $k > 0$ for which the partial sum is equal to $0$. This gives a first sequence of length $2k$ and a last sequence of length $2n - 2k$ too. Both of these sequences must start with $+1$ and end with $-1$, so if we remove these, we get a sequence of length $2k-2$ and $2n - 2k - 2$ that both satisfy the same condition. This implies that $$h_{n+1} = \sum_{k=0}^n h_k h_{n-k}.$$

$\endgroup$

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.