1
$\begingroup$

Now I know the answer is the summation of $32$ choose $0$ all the way to $32$ choose $15$. My class came up with this formula. I thought I understood how we got it but now I don't. If anyone would explain this method of shortening that calculation that would be great.

if $n$ is even $\ \ 2^{n-1 } -$ $n-1 \choose n/2$.

$\endgroup$
3
  • 2
    $\begingroup$ How many 32-bit strings have exactly the same number of 1s and 0s? $\endgroup$
    – Will Jagy
    Jul 22 '13 at 21:56
  • $\begingroup$ @Will Jagy 32 choose 16 $\endgroup$
    – Kasper-34
    Jul 22 '13 at 21:58
  • 1
    $\begingroup$ along with @WillJagy's hint use the following: how many strings are there in total? And the fact that the number of strings with fewer 1's then 0's is the same as that with fewer 0's then 1's. $\endgroup$
    – sigmatau
    Jul 22 '13 at 21:59
12
$\begingroup$

There's a bijection between the strings with fewer 0s than 1s and vice versa; you only need to count the number of strings with exactly the same number of each. There are $\binom{32}{16}$ of these. Of the remaining strings, half satisfy your needs, so the answer is $$\frac{1}{2}\left(2^{32} - \binom{32}{16}\right).$$

$\endgroup$
5
  • $\begingroup$ So did we just distribute the 1/2 into the equation? $\endgroup$
    – Kasper-34
    Jul 22 '13 at 22:05
  • $\begingroup$ @User58220 Not quite, it's $\frac12\cdot 2^{32} - \binom{31}{16}$, so the only thing that remains is $\binom{32}{16} = 2\binom{31}{16}$. $\endgroup$ Jul 22 '13 at 22:05
  • $\begingroup$ So it's as if you are taking out the middle part of the total (evenly distributed 1s and 0s) then taking half of that total to get your answer? $\endgroup$
    – Kasper-34
    Jul 22 '13 at 22:15
  • $\begingroup$ Yes, but to see why: take a string with more 0s than 1s, and replace all of the 0s with 1s and all of the 1s with 0s. This gives a string with more 1s than 0s. This is an invertible map, so it gives you a bijection between strings with more 0s than 1s and strings with more 1s than 0s. Therefore, exactly half of the "unbalanced" strings have more 0s than 1s. $\endgroup$ Jul 22 '13 at 22:27
  • $\begingroup$ Is it safe to conclude that both of these formulas are correct in these types of problems when $n$ is even, $\ \ 2^{n-1 } -$ $n-1 \choose n/2$ = $\frac{1}{2}\left(2^{n} - \binom{n}{n/2}\right)$ $\endgroup$
    – Kasper-34
    Jul 22 '13 at 23:03
4
$\begingroup$

Eric's answer is perfect, but let me just elaborate on what's going on.

Define a function $\tau$ on the set of 32-bit strings that swaps all $0$s for $1$s and vice-versa. So, for example,

$\tau(11100000000000000000000000000000) = 00011111111111111111111111111111$ $\tau(01010101010101010000000000000001) = 10101010101010101111111111111110$

Obviously $\tau$ will send all strings with $n$ digit $1$s to strings with $32-n$ digit $1$s, for all $n$. So you have three cases:

  • Strings with between 0 and 15 digit 1s
  • Strings with exactly 16 digit 1s
  • Strings with between 17 and 32 digit 1s

$\tau$ swaps the first and third category with each other, and keeps the second category fixed (though swaps its members around). So the first and third categories must have the same number of elements. Also, the number of elements in the three categories add up to $2^{32}$; and the number of elements in the second category is $\binom{32}{16}$; so the number of elements in the first category is $\frac{2^{32} - \binom{32}{16}}{2}$.

$\endgroup$
0
$\begingroup$

Hint:

There are 2^32 bitstrings of length 32...

Your question is equivalent to finding the number of subsets of 32 elements that have more than 16 elements...

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