8
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Aside: notice your title indicates you can have zero $1$'s, but your summarization says you can't have zero $1$'s.... $\endgroup$
    – user14972
    Dec 18 '16 at 11:32
  • $\begingroup$ Upon reading this question, you must think that there is no reason that there should be more 19 bit strings with an even number of 1s than an even number of 0s because of symmetry. This should give you the intuition that it is $2^{n-1}$. Then you can search for ways to prove your intuition. $\endgroup$
    – Saikat
    Dec 19 '16 at 4:25
37
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Yep, this makes sense to me now. Before, I was thinking that a string with six 1's also has four 1's and also has two 1's, but that is obviously not true now that I conceptualize it. $\endgroup$
    – Meme_god
    Dec 17 '16 at 20:38
  • $\begingroup$ Ahh I see. Yes, you are counting strings with exactly four $1$s, not at least four $1$s so your method is good. $\endgroup$
    – TomGrubb
    Dec 17 '16 at 20:40
  • 1
    $\begingroup$ Stunning answer $\endgroup$
    – Saikat
    Dec 19 '16 at 4:19
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you explain why that function counts even number of 1's. $\endgroup$
    – Saikat
    Dec 19 '16 at 4:22
  • $\begingroup$ Because 0 times anything is 0 and 1 times anything is just that thing and $(-1)^2 = +1.$ For even $k$ it becomes $(1 + 1)/2 = 2/2 = 1$ and for odd $k$ it becomes $(1 - 1)/2 = 0/2 = 0.$ So terms of odd $k$ are being multiplied by $0$ and therefore are not counting toward the sum whereas terms of even $k$ are being multiplied by $1$ and therefore are counting normally. $\endgroup$
    – CR Drost
    Dec 19 '16 at 5:09
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.