Given $m$ objects of type A and $n$ objects of type B, arrange them such that there are not more than two consecutive objects of type B.

Question

I came across this question on Quora and got interested in solving it.

Being given a number $m$ of objects of type A and a number $n$ of objects of type B, in how many ways can we create a bigger object of length $m+n$ combining them, such that in the final object there are not more than $2$ consecutive objects of type B?

My attempt:

Take away $2x$ number of objects of type B and create a new type called C such that— each object of type C is made up of two objects of type B.

Now we have: $\displaystyle \begin{array}{|c|c|} \hline \text{Type} & \text{No. of objects}\\ \hline A & m\\ \hline B & n-2x\\ \hline C & x\\ \hline \end{array} \tag*{}$ Let’s represent objects of type B by | (lone pipe) and type C by || (double pipe). We need to arrange the objects of type A (represented by period .) in between the arrangements of objects of types B and C. $\underbrace{…}_{a_0}|\underbrace{…}_{a_1}||\underbrace{…}_{a_2}||\cdots\cdots|\underbrace{…}_{a_{n-x}}\tag*{}$ Lone pipes and double pipes can permutate in $\displaystyle \frac{(n-2x+x)!}{(n-2x)!\cdot x!}=\binom{n-x}{x}\tag*{}$ ways. The figure is only representational, we are not sure about the order.

Number of ways to arrange $m$ periods in between those lone and double pipes can be given by the number of non-negative integer solution sets of the following equation: $m=a_0+(1+a_1)+(1+a_2)+\ldots+(1+a_{n-x-1})+a_{n-x}\\ \displaystyle \implies m -(n-x-1) = \sum_{i=0}^{n-x}a_i\tag*{}$ This equation has $\displaystyle \binom{m-(n-x-1)+n-x}{n-x}=\binom{m+1}{n-x}\tag*{}$ non-negative integer solution sets. (Why?).

Hence, we have $\displaystyle \binom{n-x}{x}\cdot \binom{m+1}{n-x}\tag*{}$ ways of arranging the double pipes, lone pipes and periods.

Now the number of double pipes can be varied from $0$ to $\lfloor n/2\rfloor$ which gives us: $\displaystyle \color{red}{\boxed{\sum_{x=0}^{\lfloor n/2\rfloor}\binom{n-x}{x}\cdot \binom{m+1}{n-x}}}\tag*{}$

I am not sure if this has a closed form or there is any mistake in my assesment. Any help or alternate solution would be appreciated.

Answer 1

Here is an alternative solution that confirms OPs result. We consider a binary alphabet built from letters $A,B$. Words which do not have any consecutive equal letters are called Smirnov words. A generating function for Smirnov words is given by \begin{align*} \left(1-\frac{Az}{1+Az}-\frac{Bz}{1+Bz}\right)^{-1}\tag{1} \end{align*} The coefficient $[z^n]$ of $z^n$ in the series (1) gives the number of binary words of length $n$ which do not have any consecutive letters.

In the current example we are looking for words which do not have any restriction on letters $A$. The letters $B$ may occur in runs of length one or two. We encode this situation as \begin{align*} Az\quad&\to\quad Az+\left(Az\right)^2+\left(Az\right)^3+\cdots=\frac{Az}{1+Az}\\ Bz\quad&\to\quad Bz+\left(Bz\right)^2\tag{2}\\ \end{align*}

Putting (2) into (1) we derive the generating function \begin{align*} &\left(1-\frac{\frac{Az}{1-Az}}{1+\frac{Az}{1-Az}}-\frac{Bz+B^2z^2}{1+Bz+B^2z^2}\right)^{-1}\\ &\qquad=\left(1-Az-\frac{Bz+B^2z^2}{1+Bz+B^2z^2}\right)^{-1}\\ &\qquad\,\,\color{blue}{=\frac{1+Bz+B^2z^2}{1-Az\left(1+Bz+B^2z^2\right)}}\tag{3} \end{align*}

The wanted number of arrangements is the coefficient of $A^mB^nz^{m+n}$ of the generating function in (3). We obtain \begin{align*} &\color{blue}{[A^mB^nz^{m+n}]\frac{1+Bz+B^2z^2}{1-Az\left(1+Bz+B^2z^2\right)}}\\ &\qquad=[A^mB^nz^{m+n}]\sum_{k=0}^{\infty}(Az)^k\left(1+Bz+B^2z^2\right)^{k+1}\tag{3.1}\\ &\qquad=[B^nz^n]\left(1+Bz+B^2z^2\right)^{m+1}\tag{3.2}\\ &\qquad=[B^nz^n]\sum_{k=0}^{m+1}\binom{m+1}{k}(Bz)^k(1+Bz)^k\\ &\qquad=\sum_{k=0}^{m+1}\binom{m+1}{k}[B^{n-k}z^{n-k}](1+Bz)^{k}\tag{3.3}\\ &\qquad\color{blue}{=\sum_{k=0}^{m+1}\binom{m+1}{k}\binom{k}{n-k}}\tag{3.4} \end{align*}

Comment:

• In (3.1) we use the geometric series expansion.

• In (3.2) we select the coefficient of $A^mz^m$.

• In (3.3) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

• In (3.4) we select the coefficient of $B^{n-k}z^{n-k}$.

Recalling that a binomial coefficient $\binom{p}{q}=0$ if $p,q$ are non-negative integer with $p<q$. We can transform the binomial sum (3.4) as \begin{align*} \color{blue}{\sum_{k=0}^{m+1}\binom{m+1}{k}\binom{k}{n-k}} &=\sum_{k=0}^n\binom{m+1}{k}\binom{k}{n-k}\\ &=\sum_{k=0}^n\binom{m+1}{n-k}\binom{n-k}{k}\tag{$k\to n-k$}\\ &\,\,\color{blue}{=\sum_{k=0}^{\lfloor{n/2}\rfloor}\binom{m+1}{n-k}\binom{n-k}{k}} \end{align*} in accordance with OPs result.

Note: Smirnov words can be found for instance in example III.24 in Analytic Combinatorics by P. Flajolet and R. Sedgewick.