Placing a kth adjacent term in a row of k-1 non-adjacent terms

Solution 1:

Let $N(a,b)$ denote the wanted number of words obtained by counting all binary words of length $a\geq 2$ containing $b$ $1$s with

• either $b-2$ non-consecutive $1$s and one run of $1$s with length $2$ (counted twice),

• or $b-3$ non-consecutive $1$s and one run of $1$s with length $3$ (counted once).

The first case corresponds to the substitution of $0$s if we have a pattern of the form \begin{align*} xxx0010xxx\to xxx0110xxx\\ xxx0100xxx\to xxx0110xxx\\ \end{align*} Since there are two different patterns which both give the same result, we have to count it twice. The second case corresponds to the substitution of $0$ if we have a pattern of the form \begin{align*} xxx01010xxx\to xxx01110xxx\\ \end{align*}

A table with non-zero values $N(a,b)$, $2\leq b\leq a\leq 10$ with values calculated by OP marked in blue is given below. \begin{align*} \begin{array}{r|rrrrr} a\backslash b&2&3&4&5&6\\ \hline 2&2\\ 3&\color{blue}{4}&\color{blue}{1}\\ 4&\color{blue}{6}&\color{blue}{6}\\ 5&8&15&2\\ 6&10&28&12\\ 7&12&45&36&3\\ 8&14&66&80&20\\ 9&16&91&150&70&4\\ 10&18&120&252&180&30 \end{array} \end{align*}

We show the following is valid for $a\geq 2$: \begin{align*} \color{blue}{N(a,b)=\begin{cases}(a-b+1)\left(2\binom{a-b}{b-2}+\binom{a-b}{b-3}\right)&\quad 2\leq b \leq \left\lfloor\frac{a+1}{2}\right\rfloor+1\quad\tag{1}\\ 0&\quad \text{otherwise} \end{cases}} \end{align*}

We use generating functions in order to derive $N(a,b)$ and start with generating functions of binary 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.) Encoding $0$s with $x$ and $1$s with $y$ the generating function of Smirnov words is \begin{align*} \left(1-\frac{x}{1+x}-\frac{y}{1+y}\right)^{-1}\tag{2} \end{align*} The coefficient of $x^py^q$ in the generating function above gives all words of length $p+q$ with no runs of $0$s or $1$ with length $>1$. This is a convenient first step but we need some adaptations. At first we note that the runs of $0$s are not restricted. We therefore substitute occurrences of $0$s with one or more $0$s. \begin{align*} x\quad\to\quad x+x^2+x^3+\cdots=\frac{x}{1-x} \end{align*} Each of the wanted words has either one run of two $1$s or one run of three $1$s. We respect this by substituting \begin{align*} y\quad\to\quad y+sy^2+ty^3 \end{align*} We additionally mark $y^2$ with $s$ and $y^3$ with $t$ to be able to extract zero or one terms of them.

We obtain using the generating function (2) and the substitutions above the wanted generating function \begin{align*} \color{blue}{A(x,y;s,t)}&=\left(1-\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}-\frac{y+sy^2+ty^3}{1+y+sy^2+ty^3}\right)^{-1}\\ &\,\,\color{blue}{=\frac{1+y+sy^2+ty^3}{1-x-xy-xsy^2-txy^3}}\tag{3} \end{align*}

Since we are looking for words of length $a$ with $b$ $1$s, the number of $0$s is $b-a$ and we are looking for coefficients $[x^{a-b}y^b]$ in $A(x,y;s,t)$. We have either a $2$-run of $1$ weighted by $2$ since $11$ comes from $01$ or $10$ and a $3$-run of $1$.

We obtain \begin{align*} \color{blue}{N(a,b)=\left(2[x^{a-b}y^bs^1t^0]+[x^{a-b}y^bs^0t^1]\right)A(x,y;s,t)}\tag{4} \end{align*}

Step 1: Expansion in powers of $t$

We start calculating (4) by expanding (3) in powers of $t$.

\begin{align*} &A(x,y;s,t)=\frac{1+y+sy^2+ty^3}{1-x-xy-xsy^2-txy^3}\\ &\qquad=\frac{1+y+sy^2+ty^3}{\left(1-x-xy-sxy^2\right)\left(1-\frac{xy^3}{1-x-xy-sxy^2}t\right)}\\ &\qquad=\frac{1+y+sy^2+ty^3}{1-x-xy-sxy^2}\sum_{n=0}^\infty\left(\frac{xy^3}{1-x-xy-sxy^2}\right)^nt^n\\ &\qquad=\frac{1+y+sy^2+ty^3}{1-x-xy-sxy^2}\left(1+\frac{xy^3}{1-x-xy-sxy^2}t+O\left(t^2\right)\right)\tag{5.1} \end{align*}

We extract coefficients of $t^0$ and $t^1$: \begin{align*} [t^0](A(x.y;s,t)&=\frac{1+y+sy^2}{1-x-xy-sxy^2}\tag{5.2}\\ [t^1]A(x,y;s,t)&=\frac{\left(1+y+sy^2\right)xy^3}{\left(1-x-xy-sxy^2\right)^2}+\frac{y^3}{1-x-xy-sxy^2}\\ &=\frac{y^3}{\left(1-x-xy-sxy^2\right)^2}\tag{5.3}\\ \end{align*}

and obtain from (5.1) to (5.3) \begin{align*} \color{blue}{N(a,b)}&\color{blue}{=2[x^{a-b}y^bs^1]\frac{1+y+sy^2}{1-x-xy-sxy^2}}\\ &\qquad\color{blue}{+[x^{a-b}y^bs^0]\frac{y^3}{\left(1-x-xy-sxy^2\right)^2}}\tag{5.4} \end{align*}

Step 2: Expansion in powers of $s$

We extract from (5.4) coefficients of $s^0$ and $s^1$: \begin{align*} [s^0]&\frac{y^3}{(1-x-xy-sxy)^2}=\frac{y^3}{(1-x-xy)^2}\tag{6.1}\\ [s^1]&\frac{1+y+sy^2}{1-x-xy-sxy^2}\\ &=[s^1]\frac{1+y+sy^2}{(1-x-xy)\left(1-\frac{xy^2}{1-x-xy}s\right)}\\ &=[s^1]\frac{1+y+sy^2}{(1-x-xy)}\sum_{n=0}^\infty\left(\frac{xy^2}{1-x-xy}\right)^ns^n\\ &=\frac{(1+y)xy^2}{(1-x-xy)^2}+\frac{y^2}{1-x-xy}\\ &=\frac{y^2}{(1-x-xy)^2}\tag{6.2} \end{align*}

Step 3: Expansion in powers of $x$ and $y$

We finally obtain $N(a,b)$ from (5.4), (6.1) and (6.2) by extracting coefficients of $x^{a-b}$ and $y^b$: \begin{align*} \color{blue}{N(a,b)}&=2[x^{a-b}y^b]\frac{y^2}{\left(1-x(1+y)\right)^2}+[x^{a-b}y^b]\frac{y^3}{\left(1-x(1+y)^2\right)}\\ &=2[x^{a-b}y^{b-2}]\sum_{n=0}^\infty(n+1)x^n(1+y)^n\\ &\qquad+[x^{a-b}y^{b-3}]\sum_{n=0}^\infty(n+1)x^n(1+y)^n\\ &=2(a-b+1)\binom{a-b}{b-2}+(a-b+1)\binom{a-b}{b-3}\\ &\,\,\color{blue}{=(a-b+1)\left(2\binom{a-b}{b-2}+\binom{a-b}{b-3}\right)}\tag{6.3} \end{align*} and the claim (1) follows.