9
$\begingroup$

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$$

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ 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)? $\endgroup$ – mau Apr 3 '13 at 12:47
  • $\begingroup$ Yes, you're right. I edited the question to mention this. $\endgroup$ – Igor Apr 3 '13 at 12:54
  • $\begingroup$ that's more tricky, indeed :-( $\endgroup$ – mau Apr 3 '13 at 12:56
1
$\begingroup$

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]$.

$\endgroup$
  • $\begingroup$ 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) \;. $$ $\endgroup$ – joriki Apr 4 '13 at 12:48
  • $\begingroup$ 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. $\endgroup$ – user62453 Apr 4 '13 at 16:14
0
$\begingroup$

$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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.