# 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. – Austin Mohr 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$. – Steph Sep 30 '15 at 1:56
• $\ell - m$ cannot have a meaningful counting interpretation since it is negative. – Austin Mohr 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.