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$
5
  • $\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 H. Mendoza-Cardenas
    Dec 13, 2015 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, 2015 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 H. Mendoza-Cardenas
    Dec 13, 2015 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, 2015 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 H. Mendoza-Cardenas
    Dec 13, 2015 at 4:26

1 Answer 1

Reset to default
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.

$\endgroup$
4
  • $\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, 2015 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$
    – Andrew Dudzik
    Dec 13, 2015 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$
    – Andrew Dudzik
    Dec 13, 2015 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, 2015 at 3:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .