# Combinatorial possibilities in counting correct Even and Odd bytes

A byte is a series of $8$ digits $0$ or $1$. There are $2^8$ different bytes.

Now we add a rule: we use the $8$th digit (leftmost/MSB) to indicate if the number of $1$'s in the rest of the byte is even or not.

For example: $0$ in the MSB means the number of $1$'s in the rest of the $7$ digits is odd. $1$ in the MSB means the number of $1$'s in the rest of the $7$ digits is even.

Now I got stuck in this question that needs to be solved in a combinatorial way.

In how many bytes the $8$th digit is correct regarding Odd/Even number of $1$'s in the rest of the byte according to the rules explained above?

This is what I thought about so far:

Divide into two sub-problems. Let us consider $x$ as the $8$th (MSB) digit. And consider the rest as $x_1$ to $x_7$. Thus, we consider a byte like this: $x, x_7, x_6, x_5, x_4, x_3, x_2, x_1$

Problem #1: $x=0$. then we need $x_7+x_6+x_5+x_4+x_3+x_2+x_1=2^n+1$ Problem #2: $x=1$. then we need $x_7+x_6+x_5+x_4+x_3+x_2+x_1=2^n+1$

But now I have no idea on how to solve such equations (how many possibilities...)

The simple way to approach it is to say you can pick bits $1$ through $7$ any way you want, for $2^7$ possibilities. For each possibility, one choice of bit $0$ is correct and one is incorrect. So there are $2^7$ correct bytes and $2^7$ incorrect ones.