How many odd binary numbers with four zero's?

Question

Question: How many 8-bit numbers are odd or have exactly 4 bits that equal 0?

Examples: 01001011 satisfies conditions, 01001110 and 01001111 do not.

---

Progress:

I can use inclusion-exclusion, I suppose. So: $$Odd\cup FourZeros = Odd + FourZeros - Odd\cap FourZeros$$

So I think that Odd = $2^7$, since the one's digit must be one, right?

And then I think FourZeros = ${8 \choose 4} = 70$, since we're choosing four from 8 total.

How do I find the union? Can I just pick four of the seven spots to place zeros and then randomly fill the other 3? ${7 \choose 4} * 2^3$? But that number is 280--too large to work with the inclusion-exclusion equation above (becasue 128 + 70 - 280 is below zero.

What did I do wrong?

Answer 1

If you mean both odd and have four one bits, you must have the last bit $1$ and can choose any three of the other seven, so there are ${7 \choose 3}=35$. Your example indicates you allow leading zeros.

Added: If you want either odd or four zeros there are $2^7$ odd ones because you just have to set the last bit. Among the evens there are ${7 \choose 4}=35$ that have four zeros, so a total of $128+35=163$

Answer 2

Allowing leading zeroes (as per your example) and assuming that you mean exactly four zeroes, you know that the last (units) digit is $1$ and the four zeroes must go in $4$ of the remaining $7$ locations.

This is clearly just $\binom 74$.

Forbidding a leading zero will likewise get you to $\binom 64$.

Taking the challenge as at least four zeroes, for the numbers involved here, probably the simplest approach is to add up the cases of four zeroes, five zeroes, six zeroes and (if appropriate) seven zeroes.