# Counting bit strings

Given integers $$m$$ and $$n$$ such that $$0 \le m \le n$$,

1. What is the total number of bit-strings that are of length $$n + 1$$ and have exactly $$m$$ 1's?

2. Consider an integer $$l$$ such that $$0 \le l \le m$$. How many bit-strings of length $$n + 1$$, have exactly $$m$$ 1's, and start with $$l$$ copies of 1? (i.e. $$\underbrace{1,\dotsc,1}_{l},0\dotsc,0$$)

So for the first part looking at it I think its a simple counting question. Out of the $$n + 1$$ elements I am trying to choose m 1's so I think the answer is $$n + 1 \choose m$$. I am stuck on the second part and I am not sure how do determine this number. I was trying to visualize this by drawing a matrix that was $$n+1$$ * $$n+1 \choose m$$. With the first bunch of bit-strings being the ones that start with 1's of length $$l$$. I think this is wrong so if anyone has any better suggestions that would be awesome.

Thanks

• It seems that you fill up the first $\ell$ positions with 1's, then you have $m - \ell$ 1's left to place and $n+1 - \ell$ positions left to choose from. Sep 30 '15 at 1:56
• I maybe wrong but for question 2 I think that it is $n+1 \choose l - m$. The reason for this is because you are choosing just the the bit-strings that start with 1's. So out I think you need to do a $l-m$. Sep 30 '15 at 1:56
• $\ell - m$ cannot have a meaningful counting interpretation since it is negative. Sep 30 '15 at 2:05

1. We have $n+1$ bits, and we need to choose $m$ of them to be 1's, so we have $\binom{n+1}m$ bit-strings that are of length $n+1$ and have exactly $m$ 1's.
2. We know that the string needs to start with $l$ 1's, which makes the remaining part of the string length $n-l+1$ with $m-l$ 1's, so wee need to choose $m-l$ bits from the total $n-l+1$ bits to be 1's, so we have $\binom{n-l+1}{m-l}$ bit-strings of length $n+1$, have exactly $m$ 1's, and start with $l$ copies of 1.