counting with constraints

Question

I have to count all the chains of $1$ and $2$ of length $n$ where every $1$ is followed by at list $d$ $2$'s.

I started by the simpler case where $d=1$ and the number of $1$'s is maximum (i.e it can not be another 1 because it will be less than $d$ from the next or the previous one). I realized in this case the maximum number of 1's is $\lfloor\frac{n}{2}\rfloor$ and in general it is $\lfloor\frac{n}{d+1}\rfloor$.

Also when the $n=(d+1)q+1$ the number of chains with maximum number of $1$'s is $1$ for general $n$ and $d$.

But I'm stuck in other cases... Naturally, I can count all the chains with $k$ ones, but how I discard those which don't satisfy the restriction?

Thanks in advance!

Answer 1

Supposing "chain" means string, i.e. word, then we are dealing with binary words of lenght $n$, where

a) all the ones (including the last) shall be followd by at least $d$ two's

In this case we can figure out that each one be followed by a "bumper" string of $d$ two's.
Assuming that the word contains $q$ ones, that is the same as deleting $qd$ two's from the total length and distributing the $q$ ones into $n-qd$ places.
That can be done in $$ \bbox[lightyellow] { N\left( {n,d,q} \right) = \left( \matrix{ n - qd \cr q \cr} \right) = \left( \matrix{ n - qd \cr n - q\left( {d + 1} \right) \cr} \right) } \tag{a.1} $$ where the second writing shall be preferred, because it ensures that $N(n,d,q)$ be null when $n<q(d+1)$, taking for the binomial the definition through falling factorial.

Then the answer to your question is $$ \bbox[lightyellow] { N\left( {n,d} \right) = \sum\limits_{\left( {0\, \le } \right)\,q\,\left( { \le \left\lfloor {n/\left( {d + 1} \right)} \right\rfloor \, \le \,n} \right)\;} {\left( \matrix{ n - qd \cr n - q\left( {d + 1} \right) \cr} \right)} \quad \left| {\;0 \le n,d \in Z} \right. } \tag{a.2} $$ where the bounds for $q$ can be generally extended to $0,\,cdots,\, n$, since the actual bounds are intrinsic to the binomial.

In the hypothesis (user's comment) that the first one is not preceded by any two, then the position of the first $d+1$ block of letters would be fixed, and the number of ways of obtaining such a configuration would just become $N(n-(d+1),\, d,\, q-1)$.

b) all the ones (except the last) shall be followed by at least $d$ two's, i.e. the ones are separated by at least $d$ two's.

In this alternative interpretation, it also means that each $1$ occupies $d+1$ consecutive places, except the last, which can be followed by whichever number of $2$'s.
Let's place the last one at position $j$, with $1 \le j \le n$.
Then we are left with $j-1$ positions where to place $q-1$ ones occupying $d+1$ places.
That is the same as telling that we are disposing $q-1$ identical objects into a total of $j-1-(q-1)d$ cells.

So the total number of ways of arranging $q$ ones will be $$ \eqalign{ & N\left( {n,d,q} \right) = \sum\limits_{1\, \le \,j\, \le \,n} {\left( \matrix{ j - 1 - \left( {q - 1} \right)d \cr q - 1 \cr} \right)} = \sum\limits_{0\, \le \,k\, \le \,n - 1} {\left( \matrix{ k - \left( {q - 1} \right)d \cr k - \left( {q - 1} \right)\left( {d + 1} \right) \cr} \right)} = \cr & = \sum\limits_{(0\, \le) \,k\, (\le \,n - 1)} {\left( \matrix{ n - 1 - k \cr n - 1 - k \cr} \right)\left( \matrix{ k - \left( {q - 1} \right)d \cr k - \left( {q - 1} \right)\left( {d + 1} \right) \cr} \right)} = \left( \matrix{ n - \left( {q - 1} \right)d \cr n - 1 - \left( {q - 1} \right)\left( {d + 1} \right) \cr} \right) \cr} $$ where the steps are:
-1) change index range
-2) bring index range inside the sum, as an additional binomial, so as to let $k$ free of bounds
-3) apply the "double convolution" formula
$$ \eqalign{ & \sum\limits_k {\left( \matrix{ a - k \cr m - k \cr} \right)\left( \matrix{ b + k \cr n + k \cr} \right)} = \sum\limits_k {\left( { - 1} \right)^{\,m - k} \left( \matrix{ m - a - 1 \cr m - k \cr} \right)\left( { - 1} \right)^{\,n + k} \left( \matrix{ n - b - 1 \cr n + k \cr} \right)} = \cr & = \left( { - 1} \right)^{\,m + n} \left( \matrix{ m + n - a - b - 2 \cr n + m \cr} \right) = \left( \matrix{ a + b + 1 \cr n + m \cr} \right) \cr} $$

Now let's check the validity of the above for low values of $q,\, n,\, d$ :
- $0$ ones can be placed in $1$ way, checks with ${{n+d} \choose {n+d}}$;
- $1$ one can be placed in $n$ ways, checks with ${{n} \choose {n-1}}$;
- $2$ ones can be placed in ${{n-d} \choose {2}}$, checks with ${{n-d} \choose {n-2-d}}$;
- for $n=q=0$ we get $1$, the empty string;
- for $d=0$ we get ${{n} \choose {n-q}}$ as it shall be.

Thus we can conclude that $$ \bbox[lightyellow] { N\left( {n,d,q} \right) = \left( \matrix{ n - \left( {q - 1} \right)d \cr n - 1 - \left( {q - 1} \right)\left( {d + 1} \right) \cr} \right)\quad \left| {\;0 \le n,q,d \in \mathbb Z} \right. } \tag{b.1} $$ and of course the answer to your question will be the sum of $N(n,d,q)$ over $q$ $$ \bbox[lightyellow] { N\left( {n,d} \right) = \sum\limits_{\left( {0\, \le } \right)\,q\,\left( { \le \,n} \right)} {\left( \matrix{ n - \left( {q - 1} \right)d \cr n - 1 - \left( {q - 1} \right)\left( {d + 1} \right) \cr} \right)} \quad \left| {\;0 \le n,d \in \mathbb Z} \right. } \tag{b.2} $$ where the bounds for $q$ can be generally extended to $0,\,\cdots,\, n$, since the actual ones are intrinsic to the binomial.

Example

$n=5,\; d=2,\; q=2 \quad \Rightarrow \quad N(n,d,q)=3$
$$(1,\, 0,\, 0,\, 1,\, 0) ,\; (1,\, 0,\, 0,\, 0,\, 1) ,\; (0,\, 1,\, 0,\, 0,\, 1) $$

$n=6,\; d=2,\; q=2 \quad \Rightarrow \quad N(n,d,q)=6$
$$(1,\, 0,\, 0,\, 1,\, 0,\, 0) ,\; (1,\, 0,\, 0,\, 0,\, 1,\, 0) ,\; (1,\, 0,\, 0,\, 0,\, 0,\, 1) ,\; (0,\, 1,\, 0,\, 0,\, 1,\, 0) ,\; (0,\, 1,\, 0,\, 0,\, 0,\, 1) ,\; (0,\, 0,\, 1,\, 0,\, 0,\, 1) $$

Answer 2

We interprete the problem as follows: Given is the alphabet $V=\{1,2\}$. Find the number of strings consisting of characters of $V$ of length $n\geq 0$ so that each occurrence of $1$ is followed by at least $d$ characters $2$. We do so by encoding the problem using generating functions.

Each of the admissible strings starts with zero or more $2$'s. This can be encoded as \begin{align*} 1+z+z^2+\cdots=\frac{1}{1-z}\tag{1} \end{align*}

Each so created string can be followed by zero or more $1$'s, whereby each occurrence of $1$ is replaced by $1$ followed by at least $d$ $2$'s. This can be encoded as \begin{align*} 1+z(z^d+z^{d+1}+\cdots)+z^2(z^d+z^{d+1}+\cdots)^2+\cdots&=\frac{1}{1-z\left(z^d+z^{d+1}\cdots\right)}\\ &=\frac{1}{1-\frac{z^{d+1}}{1-z}}\tag{2} \end{align*}

Multiplying (1) and (2) together we get a generating function $A(z)$ where $[z^n]$, i.e. the coefficient of $z^n$, contains the number of admissible strings of length $n$.

We obtain \begin{align*} \color{blue}{[z^n]A(z)}&=[z^n]\left(\frac{1}{1-z}\cdot\frac{1}{1-\frac{z^{d+1}}{1-z}}\right)=[z^n]\frac{1}{1-z(1+z^d)}\\ &=[z^n]\sum_{j=0}^\infty z^j(1+z^d)^j\tag{3}\\ &=\sum_{j=0}^n [z^{n-j}](1+z^d)^j\tag{4}\\ &=\sum_{j=0}^n [z^j](1+z^d)^{n-j}\tag{5}\\ &=\sum_{j=0}^n[z^j]\sum_{k=0}^{n-j}\binom{n-j}{k}z^{dk}\tag{6}\\ &=\sum_{j=0}^{\left\lfloor\frac{n}{d}\right\rfloor}[z^{dj}]\sum_{k=0}^{n-dj}\binom{n-dj}{k}z^{dk}\tag{7}\\ &\,\,\color{blue}{=\sum_{j=0}^{\left\lfloor\frac{n}{d}\right\rfloor}\binom{n-dj}{j}}\tag{8} \end{align*}

Comment:

• In (3) we apply the geometric series expansion.

• In (4) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We also set the upper limit of the series to $n$ since the exponent of $z$ is non-negative.

• In (5) we change the order of summation $j\to n-j$.

• In (6) we apply the binomial theorem.

• In (7) we observe that we need only multiples of $d$ as exponent.

• In (8) we select the coefficient accordingly.