Given 7 letters: a,a,b,b,c,d,e, how many possible ways are there for us to arrange them so that matching letters are not in consecutive positions? (e.g. aabcdbe) is not legal.
I tried to solve the question by finding the total possible ways first. If there's no restriction, then there're $\frac{7!}{2!2!}$ ways. Here we don't want $aa$ and $bb$ appear in the string, so we need to subtract $2\cdot\frac{6!}{2!}$ from $\frac{7!}{2!2!}$. Is that right? Did I miss any unwanted cases? Thanks for the help!
Best Answer
The Laguerre polynomials have some remarkable combinatorial properties and one of them is precisely suited to answer problems of this kind. This is nicely presented in Counting words with Laguerre series by Jair Taylor. We find in section $3$ of this paper:
Here we consider an alphabet $\{a,b,c,d,e\}$ and words built from the letters $$a,a,b,b,c,d,e$$
Bad words: $\{aa,bb\}$
We have $m_1=m_2=2, n_1=n_2=2$ and we obtain with some help of Wolfram Alpha
\begin{align*} p_{2,2}(t)&=[x^2]\exp\left(\frac{t\left(x-x^2\right)}{1-x^2}\right)\\ &=[x^2]\left(1+tx+\frac{1}{2}(t-2)tx^2+\cdots\right)\\ &=\frac{1}{2}t^2-t \end{align*}
The letters $c,d,e$ contribute according to the paper $t^3$ and it follows
\begin{align*} \color{blue}{\int_0^\infty e^{-t}\left(\frac{1}{2}t^2-t\right)^2t^3\,dt=660} \end{align*}