How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros How many arrangements are there with $n$ zeros($0$) and $m$ ones($1$) and $k$ runs of zeros.A run is the same digit occurring consecutively 1 or more times. For example:
$110010001110$ has 3 runs of zeros.
My professor explained this problem in lecture but I don't understand it..I have the solution to this but I don't know how we got there. Can anyone please explain how one would go about doing this problem? I might get something similar in my exam on Wednesday and I want to make sure I can do problems like these. Thank you!
 A: Start with a string of $n$ zeroes. You want to divide it into $k$ blocks, so you have to insert $k-1$ markers separating the blocks. You can insert these into any $k-1$ of the slots between adjacent zeroes, so there are $\binom{n-1}{k-1}$ ways to insert the markers and break up the zeroes into $k$ blocks. Now replace each marker with a $1$; that ensures that the blocks of zeroes really will be separated by ones and leaves you with $m-(k-1)=m-k+1$ ones still to be placed in the string. 
Each of these ones can go into one of the $k-1$ slots between blocks of zeroes, but each can also go on either end of the string, so there are $k+1$ possible locations for each of these ones. Counting the ways to distribute these $m-k+1$ ones among $k+1$ slots is a stars-and-bars problem whose answer is
$$\binom{(m-k+1)+(k+1)-1}{(k+1)-1}=\binom{m+1}k\;.$$
Thus, there are
$$\binom{n-1}{k-1}\binom{m+1}k$$
such strings.
Hagen’s first step is essentially the same as mine; his second step is done quite differently. Instead of distributing the ones, he took the $k$ blocks of zeroes and inserted them into a string of $m$ ones: counting the end slots, there are $m+1$ possible places to insert the blocks of zeroes, and there are $\binom{m+1}k$ ways to choose which $k$ of those places actually get a block of zeroes.
A: There are $n-1\choose k-1$ ways to "cut" $n$ zeroes into $k$ nonempty blocks (separate them at any of the $n-1$ places between zeroes).
And there are $m+1$ possible insertion points among the $m$ ones (including before the first/after the last), so $m+1\choose k$ ways to place the above zero-blocks. Thus we arrive at a total of
$$ {n-1\choose k-1}{m+1\choose k}.$$
