Friday 13 March 2015

Why is it not possible to calculate the amount of combinations for a byte using the Binomial coefficient



I'm trying to understand the Binomial coefficient.



I found this source which gives clear information:
https://www.calculatorsoup.com/calculators/discretemathematics/combinations.php




After reading, I was wondering if I could use the Binomial coefficient formula to calculate the amount of possibilities for a byte.



It seems that I can't calculate the amount of combinations by using the Binomial coefficient formula. Because the amount of combinations for bytes should be calculated differently.



For example: 8 bytes gives me 256 combinations. Calculation: 2^8 = 256.



Q: Why is it not possible to calculate the amount of combinations for a byte using the Binomial coefficient?


Answer



It is no wonder you are having trouble, since the page you read does not explain things very well. For example, they say this about the binomial coefficient, which is just simply wrong:





Basically, it shows how many different possible subsets can be made from the larger set.




The number of possible subsets of a set of $n$ elements is $2^n.$ You correctly applied that formula to count the number of possible bytes, in which any subset of the eight bits can be set to $1$ and the other bits set to $0.$
The total $2^8$ includes the empty set (which gives you the byte $00000000$), the set of all eight bits (which gives you the byte $11111111$), and subsets with any number of bits between zero and eight.



The binomial coefficient $\binom nr$ counts only the subsets that have exactly $r$ elements. You can't count all the bytes using just one binomial coefficient, because the bytes don't all have the same number of $1$s.
You can count all the bytes that have no $1$s (there is just one such byte, and we count it with $\binom 80 = 1$),
you can count the bytes that have eight $1$s (there is just one such byte, and we count it with $\binom 88 = 1$),

you can count the bytes that have one $1$ (there are $\binom 81$ of these),
you can count the bytes that have two $1$s (there are $\binom 82$ of these),
and so forth. But no matter which binomial coefficient you choose, there will be many possible bytes it doesn't count.
The only way to count all the bytes with binomial coefficients is to add up several coefficients. (This was shown in a comment.)


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...