1
$\begingroup$

What is the error in the following solution to the question: In how many strings of length $n$ composed of $\{0,1\}$ there's at least $m$ zeros?

Solution: choose $m$ places for the zeros, in the rest of the places choose either $0$ or $1$ therefore: $\binom n m 2^{n-m}$.

From trying out small numbers I can see that it's wrong but I don't see why it's wrong to choose places for the zeros other than maybe making a distinction of 'first' zeros, dividing by $m!$ to cancel that isn't right either.

$\endgroup$

1 Answer 1

1
$\begingroup$

You are overcounting. For example the solution that has $n$ zeros is counted $\binom{n}{m}$ times.

You can try to solve this using inclusion exclusion to get a rather unpleasant sum.

Alternatively count the sequences with exactly $m$ zeros, exactly $m+1$ zeros and so on and then add them, this yields $\sum\limits_{i=m}^n \binom{n}{m}$ which does not have a nice closed form.

$\endgroup$
9
  • $\begingroup$ If there's $n$ ones then there are no zeros so $\binom n 0 =1$... $\endgroup$
    – shinzou
    Mar 15, 2015 at 19:28
  • $\begingroup$ yeah, I swapped one with zero, fixed. $\endgroup$
    – Asinomás
    Mar 15, 2015 at 19:29
  • $\begingroup$ It's the same since $\binom n n =1$ $\endgroup$
    – shinzou
    Mar 15, 2015 at 19:31
  • $\begingroup$ Maybe you meant it's counted $2^n$ times? $\endgroup$
    – shinzou
    Mar 15, 2015 at 19:34
  • 1
    $\begingroup$ I got it, we just look at a string of only zeros which has only one way to form, but with the wrong solution it's over counted. Thank you. $\endgroup$
    – shinzou
    Mar 15, 2015 at 19:52

You must log in to answer this question.

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