# Finding how many 8-bit bytes contain an even number of zeros . . .

I believe I'm overthinking this or otherwise confused but I believe that the method to solve this would be $2^n$ where n is the length of the bytes? So in this particular case it would be $2^8$ equal 256 possible.

But then I feel like that isn't right and I'm mixed up. What I thought about is that there is 4 possible ways to have an even number f zeros (i.e. 2 zeros, 4 zeros, 6 zeros, or 8 zeros).

Any insight would be awesome as I'm confused...

• A couple things: $2^8 = 256$, not $64$. And also, your latter approach is sound but you need to consider the case when $0$ zeros appear (since 0 is an even number as well). Commented Mar 6, 2016 at 17:10
• Ah yes a dumb mistake on my part. I ended up going with that approach and noting the $C(8,0)$ as well which would come as 1 and added the values to show there are 128 possibilities. Thanks. Commented Mar 6, 2016 at 17:17
• Precisely half of them. Commented Mar 7, 2016 at 17:21

## 5 Answers

Any $7$-bit word can be completed to an $8$-bit word with an even number of $0$'s in exactly one way by choosing the eighth bit suitably. So the number of $8$-bit words with an even number of $0$'s is the same as the number of $7$-bit words. This is $2^7$.

• I read the question and immediately knew it was half of them but not why. Well here's why. Commented Mar 7, 2016 at 1:28
• Ah, the eighth bit is just a checksum digit. Commented Mar 7, 2016 at 18:30
• Each even bit pattern can be paired one to one with an odd pattern by flipping (wlog) the final bit. Commented Mar 7, 2016 at 21:40
• I agree with the conclusion, but I think there is a hole in the proof. You show that every 7-bit word has a unique corresponding 8-bit word with an even number of zeros. That only shows that the number of 8-bit words with an even number of zeros is >= the number of 7-bit words. You need to show that every 8-bit word with an even number of zeros has a unique corresponding 7-bit word as well. Commented Mar 8, 2016 at 3:37
• @Oddthinking: Yes, for absolute completeness one should add that every word with an even number of $0$'s arises in this way. Commented Mar 8, 2016 at 3:45

HINT

Divide the cases for the number of zeros, namely $0,2,4,6,8$, which gives us $$\binom{8}{0}+\binom{8}{2}+\binom{8}{4}+\binom{8}{6}+\binom{8}{8}=\frac{2^8}{2}$$ From the Binomial Theorem.

You could also use recurrence relations to solve this problem.

• I guess it goes without saying that this is nomenclature for the sum of binomial coefficients? Commented Apr 25 at 18:00

There are $2^8 = 256$ different bit-strings of ones and zeros. Because of symmetry$^{(*)}$ the number of strings with an odd number of zeros must be the same as the number of strings with an even number of zeros. Specifically, half of all the possible cases have an even number of zeros, so we have have $\frac{1}{2}2^8 = 2^7$ such bit-strings.

$(*)$ The symmetry I am thinking of here is the symmetry between an even and odd count of zeros. Because we are considering all bit-strings of length eight, if we are asking how many of them have an even/odd number of zeros, there is no reason to favor even or odd over the other, so there must be the same number of each.

• I think it would help to specify which particular symmetry you were thinking of. For example reversing the order of the bits left-to-right is "symmetrical", but doesn't help in answering the OP's question. When I read your post I my immediate thought was "yeah, take a number and replace all 0's by 1's and vice versa" - but that doesn't prove it either, because the number of 0's and 1's are either both odd, or both even! Commented Mar 7, 2016 at 3:57
• @alephzero: Try "toggle the lowest bit" (or the high bit, or whatever other bit you like). By inspection, that's an involution that toggles partiy, so it must be a bijection. Commented Mar 8, 2016 at 6:43

To find the number of ways to arrange the word

Moose, we take $\frac{5!}{2!1!1!1!}=\frac{5!}{2!}$ since we have $5$ letters in moose and only one repeated letter.

Here we are looking at the case where there are no zeroes, $2$ zeroes, $4$ zeroes, $6$ zeroes and $8$ zeroes in a 'word' of length $8$, with an alphabet consisting of $0$ and $1$.

$$\frac{8!}{8!}+\frac{8!}{6!2!}+\frac{8!}{4!4!}+\frac{8!}{2!6!}+\frac{8!}{8!}=128$$

Here's another way. The number of bytes with $n$ zeroes is the coefficient of $x^n$ in $$(1+x)^8$$ Now for any polynomial $p(x)$, the sum of the coefficients of even degree is $\frac{p(1)+p(-1)}{2}$. Hence the answer is:

$$\frac{(1+1)^8+(1-1)^8}{2} =2^7$$