Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many 32 digit binary number combinations are possible?

For example: $$00000000-00000000-00000000-00000000$$ $$00000000-00000000-00000000-00000001$$ $$00000000-00000000-00000000-00000010$$ $$.$$ $$.$$ $$.$$ $$11111111-11111111-11111111-11111110$$ $$11111111-11111111-11111111-11111111$$

Well, we can easily convert the last number to decimal to get the number of combinations and the answer would be $2^{32}$ combinations. But I need a general explanation with respect to general concepts like probability, permutations or combinations, as to how we get $2^{32}$ combinations.

P.S. I am not a mathematician. So, please try to explain in a simple way. Thanks a lot!

share|improve this question
    
You've asked for how we can say that there are 2^32 combinations. People have shown how. That's a proof. What more do you want to make it "formal"? There's no need to appeal to probability, and permutations/combinations only apply if we're selecting a subset. If you wanted to do it the hard way, you could relate the numbers expressible using k 1s to the number of ways to choose k objects from n (32 in this case), and sum all of those, and prove that sum equals 2^32, but that's redundant to the proofs already given. –  ConMan Aug 6 '13 at 0:39
add comment

4 Answers 4

up vote 9 down vote accepted

For each bit (binary digit) that you have, there are two possibilities: Either it can be a zero, or it can be a one.

Therefore, if you have one bit, you have two possible numbers. If you have two bits, each of them can be either a zero or a one, and since there are two possibilities for the first, and two possibilities for the second, there are $2^2 = 4$ total possibilities.

Similarly, if you have some number $n$ of bits, each of them can be a zero or a one, and there will therefore be $2^n$ possibilities.

share|improve this answer
4  
This is a formal proof. By the fundamental counting principle (see en.wikipedia.org/wiki/Rule_of_product), the number of ways to choose one of $\{0,1\}$ and then to do so again from the same set $n$ times is $|\{0,1\}|^n = 2^n$. –  Adriano Aug 5 '13 at 23:54
    
Thanks..now its clear! –  VISHNU VIVEK Aug 6 '13 at 1:03
add comment

It's based on this fundamental principle: If, for a given choice there are $n$ options, and for every choice of the first there are $m$ options, then there are $mn$ options for both choices.

This easily extends to more than two choices.

So for the 32 bits mentioned, there are 2 choices for each bit. For each choice of the first bit, there are 2 for the second. For each choice of the first and second, there are 2 for the third. For each choice of the first three bits, there are 2 for the fourth. And so on, which yields $2^{32}$ as the number of choices for all 32 bits by the multiplication principle just mentioned.

You can think of it as a tree, with each row of the tree except the root corresponding to each bit position, starting from the rightmost (though you could also start from the leftmost) and going left. There are two branches off each tree node corresponding to a choice of 1 or 0 for the given bit. How many nodes are there at the end of the tree? Since there's 2 nodes for every node in the previous row, then we see the answer is $2^{32}$.

These are actual proofs from the principle just mentioned.

The next section is a proof from set theory, adapted from one I found in the cited document. If this is too advanced for you, then you can ignore it, but you kept making comments about wanting a "Formal Proof" in the other answers you got. I'm not sure how else to satisfy this request.

A FORMAL PROOF OF THE MULTIPLICATION PRINCIPLE

One can give a formal proof of the multiplication principle in a restated form from set theory. See here: http://planetmath.org/node/38993/pdf

First one proves the addition principle, which says that given $m$ options for one choice and $n$ for another, and we only do one of the choices, there are $m + n$ options available. In set-theoretic terms, $|A \cup B| = |A| + |B|$ for disjoint sets $A$ and $B$, which are the sets representing the options, and the union represents the options when one is allowed either choice. The site gives a proof of this from the more fundamental principle

$$|A| = \sum_{a \in A} 1$$.

In particular, is $A$ and $B$ are disjoint, then

$$\begin{align}|A \cup B| &= \sum_{a \in A \cup B} 1 \\ &= \sum_{(a \in A) \lor (a \in B)} 1 \\ &= \left(\sum_{a \in A} 1\right) + \left(\sum_{a \in B} 1\right)\ (\mathrm{by\ disjoint\ hypothesis,\ either\ but\ not\ both\ of\ }a \in A\mathrm{\ and\ }a \in B\mathrm{\ are\ true}) \\ &= |A| + |B|\end{align}$$.

It is a simple inductive argument from this basic principle (or just that allows us to then say that $|A_1 \cup A_2 \cup ... \cup A_n| = |A_1| + |A_2| + ... + |A_n|$ when all the sets are pairwise disjoint.

So for the multiplication principle. Rephrased in set-theoretic terms, it says $|S \times T| = |S| * |T|$. That is because $S$ and $T$ are the option sets, and $S \times T$ contains pairs of options for both choices together. Write

$$S \times T = \bigcup_{s \in S} \{(s, t) : t \in T\}$$.

The sets on the right are all disjoint and have the same cardinality as $T$ (take the bijection sending $(s, t)$ to $t$). There are $|S|$ of them. So, by the just-given general addition principle, $|S \times T| = |T| + |T| + ... + |T|\ (|S|\ \mathrm{times}) = |S| * |T|$. One can then use another simple inductive argument to extend to multiple sets.

Taking the choice sets as $\{0, 1\}$, so the self-product of that with itself 32 times is essentially the 32-bit binary string you want, you get the desired result.

share|improve this answer
add comment
2^32 -1
4294967295

is the largest number you can represent in binary - 32 bits. If you consider all zeroes as the starting point you then have one more addition - 4,294,967,296 becomes to total. So from the all zeroes pattern counting on up to the all ones pattern gives four billion two hundred ninety-four million nine hundred sixty-seven thousand two hundred ninety-six different possiblities.

share|improve this answer
    
I'm just asking for a formal proof as to how you get $2^{32}$ combinations. You've re-written what I have explained in my solution in the question. –  VISHNU VIVEK Aug 5 '13 at 23:45
    
In this case proof by counting is logically defined. –  jim mcnamara Aug 6 '13 at 23:25
add comment

You say : "P.S. I am not a mathematician. So, please try to explain in a simple way"

There are 2 choices (0 or 1) for the first bit and 2 choices for the second bit. So there are 2 x 2 choices for the first two digits. Similarly, there are 2 x 2 x 2 choices for the first three digits. Continuing, you get 2 x 2 x ... x 2 (32 times) choices for a 32 digit string.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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