How to approach this type of combinatorics problems Say we have a $16$ letter long word consisting only of $\{a,b,c\}$. How many possible words are there in which the letter $c$ appears $4$ times but there are no $2$ $c$'s next to one another?
For example I know that if the $4$ $c$'s had to be next to one another we would choose $1$ out of $13$ (as in $1$ "seat" for all the $c$'s) and then deal with the rest.
I need this kind of approach to use in my upcoming exam in case I am asked to.
Thank you.
 A: Hint: Treat $a$ and $b$ as indistinguishable initially. Call it $AB$.
Question: How many ways are there to arrange the blocks $AB$ and $c$, such that $c$ appears 4 times, and no 2 c's are next to each other?

 Hint: By Stars and Bars, this is equivalent to finding the (total) number of solutions in positive integers to $p+q+r+s+t=14, p+q+r+s=14, q+r+s+t=14$.

Question: How does the above question relate to your answer?

 Hint: Multiply by $2^{12}$.

A: First arrange the a's and the b's, which can be done in $2^{12}$ ways since each of these 12 letters can be either a or b.
This leaves 13 gaps, and you can choose 4 of these gaps in which to put the c's in $\binom{13}{4}$ ways.  
Therefore there should be $2^{12}\binom{13}{4}$ words of this type.
A: This answer may not be useful from an exam point of view, but good to know at some point of time.
We can easily get the generating function by writing the regular expression for the given problem, and hence a closed form when possible.
It's explained in ``Analytic combinatorics''.
The RE for a pattern of 4 $c$ with no two of them being consecutive is:
\begin{align*}
  {\rm (a+b)^* c (a+b)(a+b)^*c (a+b)(a+b)^*c (a+b)(a+b)^*c (a+b)^*}
\end{align*}
and the corresponding generating function is:
\begin{align*}
  G(x) &= \mathrm{SEQ}(2x)\, x\, (2x)\, \mathrm{SEQ}(2x)\, x\, (2x)\, \mathrm{SEQ}(2x)\, x\, (2x)\, \mathrm{SEQ}(2x)\, x\, \mathrm{SEQ}(2x) \\
  &= \frac{8x^7}{\left(1-2x\right)^5}
\end{align*}
For any $n$ character string with 4 $c$, the formula is given by 
\begin{align*}
  [x^n]G(x)  &= 2^{n-4}\binom{n-3}{4}
\end{align*}
A: Okay.. so I stumbled upon a similar problem while I was studying and I was able to find the answer quite easily.
The problem was: How many possible ways to seat 4 boys and 3 girls in a row where no 2 girls are next to each other
This was my approach:


*

*4! possible ways to seat the boys.

*3! possible ways to seat the girls

*Consider the 4 boys as if they were standing next to each other, and there is a gap between every 2 boys, this gap is a possible slot for a girl. So in total there are 3 gaps and 2 other possible slots on the far left/right. Finally we pick 3 out of the 5 possible slots.


Multiply to get: 4!3!5!/2!.
This method seems to be very easy to wrap your head around and I can't seem to think of a flaw in it. Thanks for everyone who helped :)
