2
$\begingroup$

Consider the set $S$ (whose elements are indexed by $i\in\{1,...,\binom{l}{m}\}$) of bit strings of length $l$ that contain exactly $m$ $1$s and $l-m$ $0$s. For each string $s_i\in S$, define $x_{i,j}$ to be the number of $0$s between the $j^{th}$ $1$ and $(j+1)^{th}$ $1$ in $s_i$. Now consider the distribution of all the $x$s ($x\in\{0,...,l-m\}$). I have a formula (for which I have ample evidence empirically) stating the frequency of each possible value of $x$: $(l-x-m+1)\binom{l-x-1}{m-2}=(m-1)\binom{l-x-1}{m-1}$.

Why is the count of the object I've described equal to $(m-1)\binom{l-x-1}{m-1}$?

Here's an example where $l=5$ and $m=3$. $S=\{00111,01011,01101,01110,10011,10101,10110,11001,11010,11100\}$. $s_1=00111$ contributes two $0$s to $x$'s frequency count (since $x_{1,1}=0$ and $x_{1,2}=0$), $s_2=01011$ contributes a $1$ and a $0$ to the frequency count (since $x_{2,1}=1$ and $x_{2,2}=0$), while $s_5=10011$ contributes a $2$ and a $0$ to the frequency count (since $x_{5,1}=2$ and $x_{5,2}=0$). My formula states that there are $12$ instances of $x=0$, $6$ instances of $x=1$, and $2$ instances of $x=2$, which is all correct.

$\endgroup$
  • $\begingroup$ You started using the notation $x_{i,j}$ and then you just did not used anymore, is not clear to me how $j$ index is working here. Could you clarify that in your examples? $\endgroup$ – Carlos Mendoza Dec 13 '15 at 2:47
  • $\begingroup$ The $x_{i,j}$ notation was just to be able to completely define exactly what I'm counting. I included its use in the example in the question. Does that make it clear? $\endgroup$ – user1145925 Dec 13 '15 at 2:57
  • $\begingroup$ Not yet. If $s_1 = 00111$, then $x_{1,1}$ (you put $x_{2,1}$ but I guess is a typo) should be $0$, not $1$, because according to your notation it represents the number of $0$s in between the first $1$ and second $1$. I don't get how you move from $x_{i,j}$ to $x$, what is exactly $x$? What are we counting when $x=1$, for example? $\endgroup$ – Carlos Mendoza Dec 13 '15 at 3:28
  • $\begingroup$ @CarlosMendoza My example is already correct and has no typo; I think you misread (specifically, read my statement for $s_2$ instead of $s_1$). For $s_1=00111$, I say that $x_{1,1}=0$, as you agree it should be. When $x=1$, we are counting the number of the $x_{i,j}$ (over allowed $i$ and $j$) that take on value $1$. In the example, there are $6$ instances of $x=1$, since only $x_{2,1}=x_{3,2}=x_{6,1}=x_{6,2}=x_{7,1}=x_{9,2}=1$. $\endgroup$ – user1145925 Dec 13 '15 at 3:56
  • $\begingroup$ Now is clearer. I would recommend to add your last two sentences of the comment at the end of the question to make it even more clear. $\endgroup$ – Carlos Mendoza Dec 13 '15 at 4:26
1
$\begingroup$

Let's ask a different question: Given a sequence of $m$ 1's, how many ways can we insert $l-m$ 0's into the sequence so that there are exactly $x$ 0's between some consecutive pair of 1's?

Since we can collapse that part of the sequence into a single 1, this is the same as the number of ways to insert $l-m-x$ 0's into a sequence of $m-1$ 1's.

But this is a ball in urn problem, with $l-m-x$ balls and $m$ urns, so the answer is ${l-x-1 \choose m-1}$.

Since we fixed some particular consecutive pair of 1's, we should multiply by the total number of such pairs, which is $m-1$. This gives us $(m-1){l-x-1 \choose m-1}$, the total count of substrings "100...001" with exactly $x$ 0's, across all strings with $m$ 1's and $l-m$ 0's.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How is this not overcounting? When doing the ball in urn bit, won't that already give us a count which includes cases where other pairs of consecutive $1$s (different from the one we fixed originally) also have $x$ $0$s in between them? Don't those cases need to be subtracted out after we multiply by $m-1$? $\endgroup$ – user1145925 Dec 13 '15 at 2:38
  • 1
    $\begingroup$ @user1145925 It's important to overcount, because a substring "$100...001$" with exactly $x$ 0's may appear multiple times in a given string, and we are counting the total number of such appearances, not the number of strings. Counting the total number of strings that have a substring "$100...001$" with exactly $x$ 0's will give us a different, lower number. $\endgroup$ – Slade Dec 13 '15 at 3:01
  • 1
    $\begingroup$ @user1145925 Take your example, with $x=1$. There are three strings of the form $\square101\square1\square$, each contributing to the count, and three strings of the form $\square1\square101\square$, each contributing to the count, for a total of $6$. Yes, I double-counted the string $10101$, but you also double-counted $10101$. $\endgroup$ – Slade Dec 13 '15 at 3:09
  • $\begingroup$ I think I understand now. If $x=1$ and $l=7$, if one ball in urn thing counted $1010101$, it would only be counting for one of the three $101$s in there. A second ball in urn thing would again include the case $1010101$, but it would essentially just be counting the second $101$ in there, and the same idea the third time. Thus, the count will work out. Thanks! $\endgroup$ – user1145925 Dec 13 '15 at 3:21

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.