Arrangement of zeroes and ones

I'll be grateful for any ideas (or even solutions!) for the following task. I really want to know how to solve it.

Let $M$ be an arbitrary positive integer which represents the length of line constructed of $0$ and $1$ symbols. Let's call $M$-$N$-line a line of $M$ symbols in which there are exactly $N$ ($1 \leq N \leq M$) ones (all other elements are zeroes).

Also the number $L$ is given such that $1 \leq L \leq N$.

The task is to calculate the number of all $M$-$N$-lines in which there is a group of exactly $L$ consecutive ones and no group of more than $L$ consecutive ones.

For example if $M = 6$, $N = 4$, $L = 2$ then there are $6$ such $M$-$N$-lines:

$$1-1-0-0-1-1$$

$$1-1-0-1-0-1$$

$$1-1-0-1-1-0$$

$$0-1-1-0-1-1$$

$$1-0-1-0-1-1$$

$$1-0-1-1-0-1$$

• so, you accept a line with two or more L-groups (like 110011) but there should not be a group longer than L (like 111010)? – mau Apr 3 '13 at 12:47
• Yes, you're right. I edited the question to mention this. – Igor Apr 3 '13 at 12:54
• that's more tricky, indeed :-( – mau Apr 3 '13 at 12:56

First, list out the $M-N$ zero's as: $$\wedge_10\wedge_20\wedge_3\dots\wedge_{M-N}0\wedge_{M-N+1}$$ Then let each $\wedge_i$ be the generation function of $g_i(x)=(1+x+x^2+\dots+x^L)$, this means that for each $\wedge$ there are only allowed to have at most $L$ one's, since there are $(M-N+1)$ $\wedge$'s, thus the generating function $$G_1(x)=\prod_{i}^{M-N+1}g_i(x)=(1+x+x^2\dots+x^L)^{M-N+1}$$ and solve for $[x_1^N]$, this is the coefficient of $x^N$, and this is the number of arrangements that for each arrangement there exists groups of at most $L$ consecutive one's. But we are looking for the arrangements that exist groups of exactly $L$ consecutive one's, so we need to subtract the arrangements that for each $\wedge$ there have at most $(L-1)$ one's, then this will give you the arrangements that exist at least one exactly $L$ consecutive one's.

By the same method as above, the generating function for the arrangements that for each $\wedge$ has at most $(L-1)$ consecutive ones is $$G_2(x)=(1+x+x^2+\dots+x^{L-1})^{M-N+1}$$ and solve for $[x_2^N]$.

Finally, $[x_1^N]-[x_2^N]$ is the answer.

This is just the idea of the solution, if you want the general form of the solution it will take you a little time to actually solve for $[x_1^N]$ and $[x_2^N]$.

• Why are you introducing two separate variables and generating functions? More concisely, the desired count is $$[x^N]\left((1+x+x^2+\dotso+x^L)^{M-N+1}-(1+x+x^2+\dotso+x^{L-1})^{M-N+1}\right) \;.$$ – joriki Apr 4 '13 at 12:48
• I was solving the question by two separate parts, that's how I got two generating functions. And yes, I should have put those two generating functions into one, thank you for that. – user62453 Apr 4 '13 at 16:14

$m$...number of elements(zero or one),
$n$...number of ones,
$l$...length of sequence ones.

$d=\left\lfloor\frac{n}{l}\right\rfloor$...number of sequences length $l$ of ones
$r=n \mod l$...number of remaining ones($r \lt l$). These ones are furthermore marked using bar $\bar{1}$.

$z$...number of zeroes, $z=m-n$.
For example. If we have $z$ zeroes we want to insert $d=3$ sequences. Then, for any sequence $11...1$, and 4 zeroes $0000$, we can insert sequence to any $a_i, i={1...5}$ places $a_10a_20a_30a_40a_5$. To do this $\binom{5}{3}$ ways. One of the way is this: $11...1011...1011...10$(here I have replaced elements $a_1,a_2,a_3$) and now remain $2$ zeroes and $r$ $\bar{1}$ ones. These zeroes and $\bar{1}$ can be arranged $\binom{r+2}{1}$.

So total arrangements could be: $$a=\binom{z+1}{d}\binom{r+z-d}{z-d}$$