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$ @user362405 attempting to solve the problem /is/ context. You must make a useful attempt to solve problems like this. We have to prove you aren't just being lazy with your homework. $\endgroup$ – The Great Duck May 2 '17 at 15:15
  • 1
    $\begingroup$ @user362405 are you going to post your attempts or what? We're still waiting for you to attempt to solve the problem... $\endgroup$ – The Great Duck May 4 '17 at 16:58
  • 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
  • 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

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.