1
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Thank you for responding so quickly. So if I understand you correctly, respectively, the answers would look like so: $\endgroup$ – Drew Williams Oct 18 '15 at 18:14
  • $\begingroup$ 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$ $\endgroup$ – JMoravitz Oct 18 '15 at 18:20
  • $\begingroup$ 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 $\endgroup$ – Drew Williams Oct 18 '15 at 18:24
  • $\begingroup$ @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. $\endgroup$ – JMoravitz Oct 18 '15 at 18:27
  • $\begingroup$ 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? $\endgroup$ – Drew Williams Oct 18 '15 at 18:42

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.