1

There is a multiset $\{\frac{n-1}{2} a, \frac{n+1}{2} b\}$ where $n$ is an odd number. How many permutations of this multiset have the property that reading from left to right $b$ exceeds $a$ only for the complete permutation?

For $n=5$ I get $a, b, a, b, b$ and $a, a, b, b, b$ so the answer is 2.

In other words: I draw red and blue balls. How many permutations of $n$ draws have the property that the number of blue balls exceeds the number of red balls only after the $n$'th draw?

I am looking for a general result. I calculated the result for $n=1,3,...,13,15$ and found the sequence 1, 1, 2, 5, 14, 42, 142, 552. OEIS does not know the sequence. Unfortunately my sequence does not consist of the Catalan Numbers.

DFL
  • 54
  • If $a$ means moving to the right and $b$ moving up, then you are computing the number of paths from $(0,0)$ to $((n-1)/2,(n+1)/2)$ that don't go above the diagonal. Imitate this reflection principle. – MoonLightSyzygy Dec 23 '19 at 14:52
  • Thanks a lot. Actually my problem is identical to the problem you linked because the last ball has to be blue (b). Apparently I made some errors and my results should be the catalan numbers. Can you change your comment to an answer? – DFL Dec 23 '19 at 16:06
  • Finish it and you can add your own computation as an answer. – MoonLightSyzygy Dec 23 '19 at 16:08

1 Answers1

0

The number of possible combinations of a and b that lead to b exceeding a after the $n$'th draw (for the first time) is given by the catalan number $C_{\frac{n-1}{2}}={n-1 \choose (n+1)/2}-{n-1 \choose (n+1)/2}$. This is because the last draw has to be b and then the problem is equivalent to finding the restricted number of paths as cited in the comments.

DFL
  • 54