Number of possible permutations of n1 1's, n2 2's, n3 3's, n4 4's such that no two adjacent elements are same?

Generalisation

Given a set called an alphabet $\{1, 2,\ldots , n\}$, the number of arrangements of $k_1$ $1$s, $k_2$ $2$s, ..., $k_n$ $n$s such that no two adjacent elements are the same is given by

$$A(k_1,k_2,\ldots , k_n)=\int_{0}^{\infty} e^{-t}\prod_{i=1}^{n} (-1)^{k_i}L_{k_i}^{(-1)}(t)\: dt\tag{*}\label{*}$$

where

$$L_{k_i}^{(\alpha)}(t)=\displaystyle\sum_{j=0}^{k_i}(-1)^j\dbinom{k_i+\alpha}{k_i-j}\frac{t^{j}}{j!}$$

are Modified Laguerre Polynomials.

Explanation

Consider a regular expression $R$ (see my answer here for more details on regular expressions) that generates all words using our alphabet such that no two identical letters are adjacent.

Also consider the regular expressions $R_i$ for valid words ending with letter $i$. Then we must have

$$R=\epsilon+\sum_{i=1}^{n}R_i$$

where $\epsilon$ is the empty word.

Now, any valid word that ends in an $\textbf{i}$ must be a valid word that does not end in a $\textbf{i}$ with an $\textbf{i}$ appended hence

$$R_i=(R-R_i)\textbf{i}$$

Then the generating function equivalents of the regular expressions are

$$g(x_1,x_2,\ldots ,x_n)=1+\sum_{i=1}^{n}g_i(x_1,x_2,\ldots ,x_n)$$

or simply

$$g=1+\sum_{i=1}^{n}g_i$$

and

$$g_i=(g-g_i)x_i$$ $$\implies g_i=\frac{gx_i}{1+x_i}$$

then we have the generating function

$$g=1+g\sum_{i=1}^{n}\frac{x_i}{1+x_i}$$ $$\implies g=\left(1-\sum_{i=1}^{n}\frac{x_i}{1+x_i}\right)^{-1}$$

Then we have that the desired count is the coefficient $\prod_{i=1}^{n}x_i^{k_i}$ in $g$, in other words

\begin{align} A(k_1,k_2,\ldots k_n)&=\left[\prod_{i=1}^{n}x_i^{k_i}\right]g\\ &=\left[\prod_{i=1}^{n}x_i^{k_i}\right]\left(1-\sum_{i=1}^{n}\frac{x_i}{1+x_i}\right)^{-1} \tag{1}\label{1}\end{align}

Now, it is straightforward to prove that for some function $f=f(x_1,x_2,\ldots x_n)$

$$\int_{0}^{\infty}e^{-t}e^{tf}\: dt=\frac{1}{1-f}\tag{2}\label{2}$$

by performing a Taylor expansion of $e^{tf}$ in $t$ and noting that

$$\int_{0}^{\infty}e^{-t}t^r=r!$$

for $r\in \mathbb{N}\cup\{0\}$.

So we may, in fact express $\eqref{1}$ using $\eqref{2}$

$$\begin{align} A(k_1,k_2,\ldots k_n)&=\left[\prod_{i=1}^{n}x_i^{k_i}\right]\int_{0}^{\infty}e^{-t}\exp\left(t\sum_{i=1}^{n}\frac{x_i}{1+x_i}\right)\: dt\\ &=\left[\prod_{i=1}^{n}x_i^{k_i}\right]\int_{0}^{\infty}e^{-t}\prod_{i=1}^{n}\exp\left(t\cdot\frac{x_i}{1+x_i}\right)\: dt\\ &=\int_{0}^{\infty}e^{-t}\prod_{i=1}^{n}[x_i^{k_i}]\exp\left(t\cdot\frac{x_i}{1+x_i}\right)\: dt \tag{3}\label{3}\end{align}$$

The next thing we will need is the generating function for $(-1)^lL_l^{(-1)}(t)$, we can show it is

$$\begin{align}\exp\left(\frac{ty}{1+y}\right)&=\sum_{j\ge 0}\frac{(-t)^j}{j!}\left(\frac{-y}{1+y}\right)^j\\ &=\sum_{j\ge 0}(-1)^j\frac{t^j}{j!}\sum_{l\ge j}(-1)^l\binom{l-1}{l-j}y^l\\ &=\sum_{l\ge 0}y^l(-1)^l\left(\sum_{j=0}^{l}\frac{1}{j!}(-1)^j\binom{l-1}{l-j}t^j\right)\\ &=\sum_{l\ge 0}y^l(-1)^lL_l^{(-1)}(t) \end{align}$$

Hence

$$[y^l]\exp\left(\frac{ty}{1+y}\right)=(-1)^lL_l^{(-1)}(t)$$

Thus, substituting this into $\eqref{3}$ for $y=x_i$

$$A(k_1,k_2,\ldots k_n)=\int_{0}^{\infty}e^{-t}\prod_{i=1}^{n}(-1)^{k_i}L_{k_i}^{(-1)}(t) \: dt$$

As asserted.

As an example consider the simple case of the alphabet $\{1,2,3,4\}$ and $k_1=4,\, k_2=3,\, k_3=3,\, k_4=2$ then

$$\begin{align}A(4,3,3,2)&=\int_{0}^{\infty}e^{-t}\left(\frac{1}{24}t^4-\frac{1}{2}t^3+\frac{3}{2}t^2-t\right)\left(\frac{1}{6}t^3-t^2+t\right)^2\left(\frac{1}{2}t^2-t\right)\: dt\\ &=23\,254 \end{align}$$

Here is a variation based upon generating functions of Smirnov words. These are words with no equal consecutive characters. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

We encode the digits \begin{align*} 1,2,3,4 \qquad\text{as}\qquad d_1,d_2,d_3,d_4 \end{align*} and look for Smirnov words of length $n_1+n_2+n_3+n_4$ built from $d_i,1\leq i\leq 4$ with each letter occurring exactly $n_i\geq 1$ times.

A generating function for the number of Smirnov words over a four letter alphabet $V=\{d_1,d_2,d_3,d_4\}$ is given by \begin{align*} \left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series $A(z)$. The number of all Smirnov words of length $n_1+n_2+n_3+n_4$ over a four letter alphabet is therefore \begin{align*} \left[z^{n_1+n_2+n_3+n_4}\right]\left(1-\frac{4z}{1+z}\right)^{-1} \end{align*}

Since we want to count the number of words of length $n_1+n_2+n_3+n_4$ with each character in $d_i$ occurring $n_i$ times, we keep track of each character. We obtain the number of wanted words as \begin{align*} \color{blue}{\left[d_1^{n_1}d_2^{n_2}d_3^{n_3}d_4^{n_4}\right]\left(1-\frac{d_1}{1+d_1}-\frac{d_2}{1+d_2}-\frac{d_3}{1+d_3}-\frac{d_4}{1+d_4}\right)^{-1}} \end{align*}

Example:

We consider the example of @N.Shales setting $(n_1,n_2,n_3,n_4)=(4,3,3,2)$ and we obtain in accordance with his result (and with some help of Wolfram Alpha) \begin{align*} \left[d_1^4d_2^3d_3^3d_4^2\right]\left(1-\frac{d_1}{1+d_1}-\frac{d_2}{1+d_2}-\frac{d_3}{1+d_3}-\frac{d_4}{1+d_4}\right)^{-1}\color{blue}{=23\,254} \end{align*}