3
$\begingroup$

Out of all bit strings of length $N$, we need to count how many of them are there in which all the ones are present in a window of length $K$.

For this, my initial thought was:

The starting point of the window can be placed at $(N - K)$ positions. In each window, each bit can either be $1$ or $0$. The number of bit strings would then be $(N - K) * 2^k$.

However, there is over-counting involved in this method.

How do I solve this problem?

$\endgroup$
2
$\begingroup$

Let $a(n,k)$ be the number of bit strings of length $n$ having all of their ones in a window of length $k$. Suppose that we increase the length of the string to $n+1$; the only new allowable strings are those that have a $1$ in the $(n+1)$-st position, meaning that the window is the last $k$ bits, and there are exactly $2^{k-1}$ of those. Thus, we have the recurrence

$$a(n+1,k)=a(n,k)+2^{k-1}\;,$$

valid for $k\ge 1$. It’s also clear that $a(n,n)=2^n$ for $n\ge 1$. From these it’s straightforward to derive a closed form for $a(n,k)$; I’ve left it in the spoiler-protected block below in case you’d like to try finishing the argument yourself.

Thus, for $1\le k\le n$ we have $a(n,k)=2^k+(n-k)2^{k-1}=(n-k+2)2^{k-1}$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

There are $N+1$ bit strings of length $N$ having zero or one $1$s.

If such a bit string has $\geq2$ ones it has a first $1$ and a last $1$, and anything in between. Let $r\geq2$ be the length of the window determined by the first and the last $1$. There are $N-r+1$ positions of such a window along the string. The total number $n$ of admissible strings is therefore given by $$n=N+1+\sum_{r=2}^K(N-r+1)2^{r-2}\ .$$ When you compute the sum you'll obtain a result so simple that it makes you think whether there is not an easier solution.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A bit string can have one one if it has length $1$... $\endgroup$ – 5xum Jun 13 '16 at 8:46

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.