Generating functions - combinatorics problem of Mirko couting vehicles through the toll

Question

Through the toll plaza vehicles pass each other. Mirko keeps a record order of passing vehicles according to the following types: motorcycle, bus and truck. How many possible sequence of passage of vehicles through the toll on a given day if it is known that there were 250 vehicles, motorcycles were even numbers, buses odd and trucks were exactly 5 and no two trucks were not adjacent?
My work:
I try first solve problem without no two trucks were not adjacent. Idea is to use generating function. $$(1+x^2+x^4+...)*(x^1+x^3+...)*x^5$$ and we are looking for the coefficient $<x^{250}>$. If we rewrite a little ... $$(1+x^2+x^4+...)^2$$ and we are looking for the coefficient $<x^{244}>$. $$\frac{1}{(1-x^2)^2}=(1-x^2)^{-2}$$ We know $$-2+122-1\choose{2}$$$$=<x^{244}>.$$ What about the othere part of task?

Answer 1

Here is an answer based upon generating functions. We can reformulate the problem as follows.

We encode (m)otorcycles, (b)usses and (t)rucks by their initial character and consider the alphabet \begin{align*} V=\{m,b,t\} \end{align*} We are looking for the number of words built from $V$ of length $250$ which contain an even number of $m$'s, and odd number of $b$'s and $5$ $t$'s.

In order to obtain a generating function which respects that no two consecutive $t$'s occur, we consider Smirnov words built from $V$. These are words with no consecutive equal letters at all. See e.g. example III.24 in Analytic Combinatorics by P. Flajolet and R. Sedgewick. So,
\begin{align*} mtbmtmtmbtbt \end{align*} is a Smirnov word, while $mmt$ is not a Smirnov word.

According to the referred section in the book we know the Smirnov words of a three letter alphabet $V$ are represented by a generating function $S(m,b,t)$ with \begin{align*} S(m,b,t)=\left(1-\frac{m}{1+m}-\frac{b}{1+b}-\frac{t}{1+t}\right)^{-1}\tag{1} \end{align*}

The idea is, to take all Smirnov words and replace each $m$ with one or more $m$'s, each $b$ with one or more $b$'s. Then, in order to find the wanted number of words, we extract the coefficient of $t^5$.

Replacing $m$ with one or more $m$'s means to substitute \begin{align*} m\rightarrow m+m^2+m^3+\cdots=\frac{m}{1-m} \end{align*} and the same holds for $b$. We also need later to count the number of $m$'s and $b$'s and so we tag them with $z$.

We consider the generating function \begin{align*} S\left(\frac{mz}{1-mz},\frac{bz}{1-bz},t\right) &=\left(1-\frac{\frac{mz}{1-mz}}{1+\frac{mz}{1-mz}}-\frac{\frac{bz}{1-bz}}{1+\frac{bz}{1-bz}}-\frac{t}{1+t}\right)^{-1}\\ &=\left(1-(b+m)z-\frac{t}{1+t}\right)^{-1} \end{align*}

We use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ in a series and obtain with some help of Wolfram Alpha \begin{align*} [t^5]S\left(\frac{mz}{1-mz},\frac{bz}{1-bz},t\right)&=[t^5]\left(1-(b+m)z-\frac{t}{1+t}\right)^{-1}\\ &=\frac{(b+m)^4z^4}{(1-(b+m)z)^6} \end{align*} Since we want to find the number of words of length $250$ and $5$ characters were already used for $t^5$ we obtain \begin{align*} [z^{245}]\frac{(b+m)^4z^4}{(1-(b+m)z)^6}&=(b+m)^4[z^{241}]\frac{1}{(1-(b+m)z)^6}\tag{2}\\ &=(b+m)^4[z^{241}]\sum_{j=0}^\infty\binom{-6}{j}(b+m)^j(-z)^j\tag{3}\\ &=(b+m)^4[z^{241}]\sum_{j=0}^\infty\binom{j+5}{j}(b+m)^jz^j\tag{4}\\ &=(b+m)^4\binom{246}{241}(b+m)^{241}\tag{5}\\ &=(b+m)^{245}\binom{246}{5}\tag{6}\\ \end{align*}

From (6) we finally conclude the number of all words without restriction to parity of $b$ or $m$ is $2^{245}\binom{246}{5}$ and since we are looking for words with even $b$ only we get due to symmetry the answer \begin{align*} 2^{244}\binom{246}{5} \end{align*}

Comment:

• In (2) we apply the linearity of the coefficient of operator and use the rule $$[z^p]z^qA(z)=[z^{p-q}]A(z)$$

• In (3) we use the binomial series expansion.

• In (4) we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$

• In (5) we select the coefficient of $z^{241}$.

Answer 2

We can treat the trucks up until the very end.

First lets solve the problem in which we have an even number of motorcycles, an even number of buses and $245$ vehicles. We just have to select the positions occupied by the motorcycles.

The number of possibilities is $\sum\limits_{i=0}^{122}\binom{245}{2i}=2^{245-1}$.

After this notice that there are going to be $246$ positions where we can select to insert one of the trucks. So we have to multiply this by $\binom{246}{5}$.

Hence the final answer is $2^{244}\binom{246}{5}$.