4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hell.. this remembered to me the problem of four-color map. $\endgroup$ – Masacroso Oct 16 '14 at 15:42
  • $\begingroup$ @Masacroso Like a map with countries forming a belt and with the determined number of countries with assigned color. And this number makes a difference. In the case for example 100 color_1 countries and 1 color_2,3,4 countries the proper coloring is impossible. $\endgroup$ – Widawensen Apr 25 '17 at 12:59
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice answer. (+1) I see you are a generatingfunctionologist. :-) I used this approach also for this related answer. $\endgroup$ – Markus Scheuer Aug 21 '17 at 6:25
  • $\begingroup$ Thanks @MarkusScheuer! I had to add my (+1) to your related answer. It seems that, despite this method being used several times here on MSE, many users are still relatively unaware of it's power. I'm trying to improve my understanding of generatingfunctionology and I have to say that many of your answers have been instrumental in helping :) I still struggle with Flajolet and Sedgewick though, as I find it quite dense. $\endgroup$ – N. Shales Aug 21 '17 at 8:08
  • 1
    $\begingroup$ You're welcome! Good to see that some answers are useful. :-) I also consider this book as a great treasure of knowledge and go again and again through some sections to deepen my understanding. I would like to additionally point to this MSE post as it contains two somewhat advanced representations of binomial coefficients which prove to be sometimes helpful. $\endgroup$ – Markus Scheuer Aug 21 '17 at 8:25
  • 1
    $\begingroup$ Thanks for that link, it's full of helpful tricks! The Beta function representation I have seen (I accidentally derived it recently) but I've not seen the residue representation and I have not seen that identity. I will read through the post but it might take me a while as my complex analysis is a little rusty. Thanks again! $\endgroup$ – N. Shales Aug 21 '17 at 8:41
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.