1
$\begingroup$

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

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

Hope this helps.

$\endgroup$

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.