Permutations of a multiset where a never exceeds b

42 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.