Arrange letters to avoid consecutive positions

combinatorics

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:

Theorem: If $m_1,\ldots,m_k,n_1,\ldots,n_k$ are non-negative integers, and $p_{m,n}(t)$ are polynomials defined by \begin{align*} \sum_{n=0}^\infty p_{m,n}(t)x^n=\exp\left(\frac{t\left(x-x^m\right)}{1-x^m}\right) \end{align*} then the total number of $k$-ary words that use the letter $i$ exactly $n_i$ times and do not contain the subwords $i^{m_i}$ is \begin{align*} \int_0^\infty e^{-t}\prod_{j=1}^k p_{m_j,n_j}(t)\,dt \end{align*}

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*}

Related Question