How many 19-bit strings can be generated from having an even number of ones?

Question

So essentially how many 19-bit strings can you make with 2 1's or 4 1's or .... or 18 1's?

I know the # of 19-bit strings that can be produced with 2 1's would be 19!/17!2! and the number of 19-bit strings that can be produced with 4 1's would be 19!/15!4! ..... up until 19!/18! in the case where there are 18 1's. The thing I don't understand is how much overlap occurs.

I know this problem has to do with inclusion-exclusion principle, I am just confused on how to calculate the intersection of every single possible outcome.

Answer 1

make any string with the fist 18 digits. The last digit is forced to be a 1 or a 0, based on the number of 1s in the first 18.

Answer 2

There is no overlap in what you counted; if a string has four $1$s, then it cannot also have six $1$s. So you just need to take a sum over these possibilities.

A simpler way uses the following trick: if a string of length $19$ has an odd number of 1s, then its complement (replace all $0$s with $1$s and $1$s with $0$s) has an even number of ones, and vice versa. So take all possible binary strings and just divide by $2$.

Answer 3

Let $c=(x_1,\cdots,x_{19})$ and $\bar c=(1-x_1,\cdots,1-x_{19})$. We have a map $$c \to \bar c \to \bar{\bar c}=c.$$ Since $19$ is odd, for any odd(even)$c$ we will get an even(odd) $\bar c$. Therefore, the number is $$2^{19}/2=2^{18}.$$

Note that: $c_1\ne c_2$ implies (trivially) $\bar c_1\ne \bar c_2.$

Answer 4

I like the accepted solution but I just wanted to say something about doing the mathematics the "hard" way. You know that there are $\binom m k = \frac{m!}{k!(m-k)!}$ ways to choose a set of $k$ items from a set of $m$ items. Those items can be numbered bits chosen to be 1s or 0s. Of course you know the identity that: $$\sum_{k=0}^m \binom m k = 2^m$$ because of course if you sum up all the ways you might choose $k$ bits to be 1, then you get all possible bitstrings. However there is a simple proof of this which hinges on the idea that these coefficients appear in the binomial expansion, $$\sum_{k=0}^m \binom m k ~x^k ~y^{m-k}= (x + y)^m.$$ Just plug in $x = y = 1$ to find the above formula as a special case.

Well now you want to consider only even bitstrings, and so we can still "do it the hard way" by asking for a function of $k$ that is $1$ if $k$ is even or $0$ if $k$ is odd, and a great example is $[1 + (-1)^k]/2.$ Plugging that in, the sum that you want is just $$\sum_{k=0}^m \binom mk \frac{1 + (-1)^k}2 = \frac12 \sum_{k=0}^m \binom mk + \frac12 \sum_{k=0}^m \binom mk (-1)^k.$$ The first sum is clearly $2^m/2 = 2^{m-1}$ and the second sum we can use the above formula to reason that it is actually $(-1 + 1)^m/2 = 0^m/2 = 0.$

So you can do this the hard way if you'd prefer and you'll definitely get the same result.

Answer 5

From the approach you took to the problem, my first thought was to use the fact that $\binom{19}{k}=\binom{19}{19-k}$; because $19$ is odd it follows that $$\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{k} =\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{19-k} =\sum_{\substack{k=0\\k\text{ odd}}}^{19}\binom{19}{k}.$$ Adding the left hand side and right hand side together we get the sum over all $k$, so $$2\times\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{k}=\sum_{\substack{k=0\\k\text{ even}}}^{19}\binom{19}{k}+\sum_{\substack{k=0\\k\text{ odd}}}^{19}\binom{19}{k}=\sum_{k=0}^{19}\binom{19}{k},$$ and this equals $2^{19}$ by the binomial theorem, see also CR Drost's answer. So your answer is $2^{18}$.

But I like Doug M's answer much better.