About repeated permutations

Question

I have a string of letters that consist exactly of $n$ times the letter X and $n$ times the letter Y.

How many are the permutations in which X comes immediately before Y for exactly $k$ times?

Answer 1

Start with a string of $n$ Y’s. Start by choosing $k$ of the Y’s and inserting an X immediately in front of each. There are only $k+1$ places where the remaining $n-k$ X’s can go: you can expand any of the original $k$ X’s to a block of consecutive X’s, and you can put a block of X’s at the end of the whole string, after all of the Y’s.

There are $\binom{n}k$ ways to choose the $k$ Y’s that will immediately follow an X. We put an X immediately in front of each; call these $k$ X’s the original X’s. We must now count the ways to distribute the remaining $n-k$ X’s. For $i=1,\ldots,k$ let $m_i$ be the number of X’s that we add to the $i$-th original X to form a block of consecutive X’s, and let $m_{k+1}$ be the number that we place at the end of the string. These numbers must satisfy the equation $\sum_{i=1}^{k+1}m_i=n-k$, and any $(k+1)$-tuple $\langle m_1,\ldots,m_{k+1}\rangle$ of non-negative integers satisfying the equation represents one acceptable permutation. This is a standard stars-and-bars problem, and there are $\binom{n-k-1}k$ such solutions. The final answer, then, is that there are $\binom{n}k\binom{n-k-1}k$ acceptable permutations.