In how many ways can 'n' red and 'n' blue balls be arranged, such that at any point from the left hand side, the number of red balls is always greater than or equal to the number of blue balls ? Example : n = 2 RRBB RBRB Answer = 2


closed as off-topic by Scientifica, Shailesh, Namaste, Don Thousand, N. F. Taussig Oct 6 '18 at 20:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Scientifica, Shailesh, Namaste, Don Thousand, N. F. Taussig
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ To prevent your question from getting negative attention it is recommended that you study the guide for new askers. $\endgroup$ – Jyrki Lahtonen Oct 6 '18 at 12:59
  • 3
    $\begingroup$ Hint: Use the Catalan numbers. $\endgroup$ – ArsenBerk Oct 6 '18 at 12:59

This is exactly equal to the $n$-th Catalan number. They're a well studied and interesting group of numbers, and arise from a fundamental recurrence relation which you can actually obtain from your problem as well. This is $$C_n=\sum_{k=0}^{n-1}C_kC_{n-k-1}$$, where $C_0=1$. They also have a closed form binary expression, and you can find a derivation starting from the recurrence here.

Another useful link is this. You will notice that the same problem can be reformulated in a number of ways, such as the number of acceptable parantheses sequences (which is exactly your problem, replace red with '(' and blue with ')'), monotonic lattice paths, and what are known as Dyck paths (essentially the same).


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