Given $n_1 $ number of $1 $'s, $n_2 $ number of $2 $'s, $n_3 $ number of $3 $'s, $n_4 $ number of $4 $'s.
form a sequence using all these numbers such that two adjacent numbers should not be same.
I have tries lot of things but nothing worked.
can somebody tell me how to solve this problem?
Best Answer
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
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}$$