Let's call a sequence with $n$ occurrences of $L$ and $n$ occurrences of $R$ a balanced sequence if on counting from left to right the number of $L$'s is always greater than or equal to the number of $R$'s. How many such balanced sequences are there?

The answer given in my textbook is $$ {{2n}\choose{n}} \cdot \frac{1}{n+1}$$

I could devise no counting arguments for this.

EDIT: The number of balanced and unbalanced sequences is $$ {{2n}\choose{n}}$$

For finding the unbalanced sequences,I've taken hint that interchanging $R$ and $L$ from the place where the number of occurrences of $R$ exceeds the number of occurrences of $L$. This gives the number of such sequences to be$$ {{2n}\choose{n+1}} $$

I infer that this interchanging produces a bijection between unbalanced sequences with $n$ occurrences of $L$ and $n$ occurrences of $R$ and $n-1$ occurrences of $L$ and $n+1$ occurrences of $R$.

But I am not sure if my reason for this bijection is correct.After the interchange the number of occurrences of $R$ is always greater than that of $L$.So all the sequences will be unbalanced.But how could I prove that this will contain exactly the same number of unbalanced sequences as the original sequence?

  • 4
    $\begingroup$ This was a question from an archive that consists of problems with answers to choose from 4 options.I substituted some for smaller values of $n$, and guessed the answer.As I haven't been so familiar with Catalan numbers,I couldn't recognise it.I seem to hit a roadblock every time I tried it.As suggested in the meta post,for future posts,I will try to attempt the problem in a better manner and provide more context.Thanks for the suggestions and help provided. $\endgroup$ – user362405 May 1 '17 at 11:29
  • 2
    $\begingroup$ @TheGreatDuck The linked meta answer clearly explained that context != effort. We should not force the OP to post their attempts in this particular case. The very fact that other users already helped the OP by identifying the answer as Catalan numbers is enough; IMHO this question served its purpose. Important lessons one can learn are that (1) Catalan numbers occur in a vast variety of situations, and (2) it is an important math skill to recognize Catalan numbers. $\endgroup$ – Alex May 4 '17 at 20:00
  • 1
    $\begingroup$ @TheGreatDuck The question is closed because people voted to close it. That is it, no less no more. Once again, context != effort. The apparent lack of context is not a good enough reason to ask for more effort in this particular case. The question will likely remain closed, and OP has already been helped by being directed to learn more about Catalan numbers. $\endgroup$ – Alex May 4 '17 at 20:06
  • 2
    $\begingroup$ @TheGreatDuck ,Alex Thank you for your feedback and comments .Taking note of these, I have edited the post. $\endgroup$ – user362405 May 5 '17 at 2:55
  • 1
    $\begingroup$ I was a bit afraid at first.Will this question now be opened again? $\endgroup$ – user362405 May 5 '17 at 3:02

Your Answer

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

Browse other questions tagged or ask your own question.