# binary combinations/rule of sums

I'm currently working on this topic but I'm having a hard time. In an 8-bit string, there are 256 combinations (or is it permutations?). Either way, I know it is 2^8.

If at least 3 elements must be 1, how many combinations exist? What about exactly 3 1s? At most?

When I use the combinations formula (n! / r! (n-r)! ) on the entire length of the bit string, the answers produce a bell-shaped curve (lowest answer 1, highest [and middle] answer is 70). What am I doing wrong? Is it as simple as "if 3 elements must be 1s, then 2^5 is what's left? Where does that leave my other questions?

• Hint: You will be ok with the combination formula. – true blue anil Oct 18 '15 at 15:32

While the word combination is used loosely as any way of combining things (whether it relates to the binomial coefficient or not), a permutation is specifically a bijective function from a set $S$ to itself. If the set was ordered, then people will often write out the permutation as a string where the $i^{\text{th}}$ thing that appears is where the $i^{\text{th}}$ term in the unchanged set gets mapped to. For notation, we can also choose to write it as a matrix where the top row is the original list, and the bottom row is where it gets mapped.

For example, with $S$ being the set $\{A,B,C\}$, you have the following six permutations:

$\begin{pmatrix} A&B&C\\A&B&C\end{pmatrix},\begin{pmatrix} A&B&C\\A&C&B\end{pmatrix},\begin{pmatrix} A&B&C\\B&A&C\end{pmatrix},\begin{pmatrix} A&B&C\\B&C&A\end{pmatrix},\begin{pmatrix} A&B&C\\C&A&B\end{pmatrix},\begin{pmatrix} A&B&C\\C&B&A\end{pmatrix}$

or it can be written more succinctly as $ABC, ACB, BAC, BCA, CAB, CBA$.

The first question on the other hand is not about permutations, but rather is a question of how many functions from $\{1,2,3,\dots,8\}$ there are to the set $\{0,1\}$.

These can be written in a similar manner:

$\begin{pmatrix}1&2&3&4&5&6&7&8\\0&0&0&0&0&0&0&0\end{pmatrix}, \begin{pmatrix}1&2&3&4&5&6&7&8\\0&0&0&0&0&0&0&1\end{pmatrix}, \begin{pmatrix}1&2&3&4&5&6&7&8\\0&0&0&0&0&0&1&0\end{pmatrix},\dots$

or these can be written more succinctly as $00000000, 00000001, 00000010,\dots$

and as you say there are $2^8=256$ of these.

The question of "If at least three elements must be a one" we may approach this in two directions.

In this specific scenario, since there are only two possibilities for things to be mapped to (either zero or one), there are precisely $\binom{8}{k} =\frac{8!}{(8-k)!k!}$ number of binary sequences of length eight which have precisely $k$ ones. The problem becomes more complicated if the set we were mapping onto had more than two elements.

We may choose to answer as $\#(\text{At least 3 ones}) = \#(\text{Exactly 3 ones})+\#(\text{Exactly 4 ones})+\dots+\#(\text{Exactly 8 ones})$

or we may choose to use fewer arithmetic operations and do the following:

$\#(\text{At least 3 ones}) = \#(\text{Any number of ones}) - \#(\text{Exactly 2 ones}) - \#(\text{Exactly 1 ones}) - \#(\text{Exactly 0 ones})$

Similarly, you have

$\#(\text{At most 3 ones}) = \#(\text{Exactly 3 ones})+\#(\text{Exactly 2 ones})+\dots+\#(\text{Exactly 0 ones})$

The number $2^5$ would not count how many have exactly $3$ ones, nor would it count how many don't have exactly $3$ ones, but rather it counts how many length 8 binary sequences there are where specifically the first three terms are one and the remaining five terms can be anything (more ones or zeroes or a mix).

• Thank you for responding so quickly. So if I understand you correctly, respectively, the answers would look like so: – Drew Williams Oct 18 '15 at 18:14
• It would look like a summation of binomial coefficients. $\#(\text{At least 3 ones})=\sum\limits_{i=3}^8 \binom{8}{i}$. Notice the correlation to the binomial theorem, $\#(\text{At least 0 ones})=\sum\limits_{i=0}^8\binom{8}{i}=\sum\limits_{i=0}^81^{8-i}1^i\binom{8}{i}=(1+1)^8=2^8$ – JMoravitz Oct 18 '15 at 18:20
• This was the rest of what I was writing but I didn't know that this site accepts the carriage return as the submit button: C(8,3) + C(8,4) + ... C(8,8) or C(8,3) - C(8,2) - C(8,1); C(8,3) + C(8,2) + C (8,1) + C(8,0) ? Is there a way to sum/total these without working through the formula until it's been reduced to one term or must they all be worked out first? I haven't actually been introduced to the notation that you wrote here – Drew Williams Oct 18 '15 at 18:24
• @DrewWilliams Unfortunately, they should be worked out. Also, note that nowhere did I suggest C(8,3)-C(8,2)-C(8,1). I suggested $2^8 - \binom{8}{2} - \binom{8}{1}-\binom{8}{0}$. This one should be easier to work out than adding $\binom{8}{3}+\dots+\binom{8}{8}$ since there are fewer terms. – JMoravitz Oct 18 '15 at 18:27
• I apologize for being tedious, I have constant vertigo and it's very difficult for me to concentrate when it comes to new subjects, especially mathematics. So from your suggestion, I arrived at (256) - (31) = (225) for the answer. Is that correct? – Drew Williams Oct 18 '15 at 18:42