Consider the following multiset: $$ \begin{align*} \{a_1,a_2,\cdots, a_k,\underbrace{x,x,\cdots,x}_{\text{m times}},\underbrace{y,y\cdots y}_{\text{n times}}\} \end{align*} $$ How many sequences can be made using all symbols of the multiset with the restriction that every y is separated by at least one x at the left and at the right?
My Answer:
First make a sequence with all the y's: $\frac{n!}{n!} = 1$.
After that, distribute the x's in the spaces created by y's considering the restriction: $$ (\underbrace{\_}_{\text{slot 1}} y \underbrace{\_}_{\text{slot 2}} \cdots \underbrace{\_}_{\text{slot n}} y \underbrace{\_}_{\text{slot n+1}}) \rightarrow s_1+s_2+\cdots + s_{n+1} = m \text{ such that } s_i \geq 1 $$ To solve the number of solutions of that equation, use stars and bars method: $$ \begin{align*} s_1+s_2+\cdots +s_{n+1} &= m \text{ such that } s_i \geq 1\\ s_1'+s_2'+\cdots +s'_{n+1} &= m -(n+1) = m-n-1\text{ such that } s'_i \geq 0 \end{align*} $$ The number of solutions is: $$ {m-n-1+n \choose n} = {m-1 \choose n} $$ Now we have a sequence with $n+m$ elements considering the restriction. Let's distribute the $a_i$'s in the sequence with no restriction: $$ s_1+s_2+\cdots +s_{n+m+1} = k \text{ such that } s_i\geq 0 $$ The number of solutions is: $$ {n+m+k\choose n+m} $$ Then, for each of those distributions of $a_i$'s, organize them in all possible ways: $k!$. Hence my final answer is: $$ 1{m-1 \choose n}{n+m+k\choose n+m} k! $$
Sanity Check: As a good practice, I'm always trying to do some sanity checks in my answers, since combinatorics can be very subtle sometimes...
Considering the multiset with $k = 1$, $n=1$ and $m=2$ we would have the following sequences: $$ (a_1xyx)\\ (xa_1yx)\\ (xya_1x)\\ (xyxa_1) $$ Validating my answer: $$ 1{2-1 \choose 1}{1+2+1\choose 1+2} 1! = 1\cdot 1 \cdot {4 \choose 3} \cdot 1 = 4 $$
Is everything correct? Any help and critics are highly appreciated!
Thanks!