How many bit strings contain exactly five $0$s and fourteen $1$s if every $0$ must be immediately followed by two $1$s?

What I need help with: For this question, the answer is 126-bit strings. However, I don't understand why the combination formula $n\choose r$ is used. I solved this question by using the permutation formula $\frac{n!}{n1!n2!}$ = $\frac{9!}{5!4!}$

Basically, can I look at the question as if it were asking "How many ways can one arrange five $0$s and fourteens $1$s such that every $0$ is followed by two $1$s?

Also, what is the difference between the two formulas above, I am very confused

The two formulas I'm talking about are the combination formula and the permutation one where you divide the total number of objects by the number of indistinguishable objects. Are these the same formulas? because I found that using either gives the same result for this question.

  • $\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ – José Carlos Santos Sep 18 '19 at 5:51
  • $\begingroup$ Do you mean the difference between $C(9,5)$ and $\frac{9!}{5!\cdot4!}$? There is none. Those are the same thing. $\endgroup$ – Arthur Sep 18 '19 at 5:51
  • $\begingroup$ Yes, but for C(9,5) the denominator is r! times (n-r)! where as the permutation formula has a denominator of any number of indistinguishable items multiplied by each other $\endgroup$ – curt tainn Sep 18 '19 at 5:53
  • $\begingroup$ What is the right approach to this question? Can I look at it as if it were asking "How many ways can one arrange five 0s and fourteens 1s such that every 0 is followed by two 1s? $\endgroup$ – curt tainn Sep 18 '19 at 6:01
  • $\begingroup$ The permutation formula is $P(n, k) = \frac{n!}{(n - k)!}$. What you have used is the combination formula $C(n, k) = \frac{n!}{k!(n - k)!}$. $\endgroup$ – N. F. Taussig Sep 18 '19 at 8:57

Let $a = 011$ and $b = 1$. What you are looking for is the number of words on the alphabet $\{a,b\}$ containing 5 $a$'s and $4$ $b$'s (since the number of $b$'s is $14 - 2 \times 5 = 4$). Such a word is determined by the positions of the $a$'s (or of the $b$'s, as you prefer). This gives you $\binom{9}{5} = \binom{9}{4} =216$ possibilities.


$\binom 9 5$ equals $\frac{9!}{5!4!}$ as does the number of ways to arrange 9 objects of two different kinds of 5 and 4 each.

Let us do some double counting. Consider $n$ objects out of which $r$ are of one kind and the remaining $n-r$ are of another. If we have $n$ spots to place these $n$ objects, we can make a unique arrangement by choosing the $r$ spots in which the type of object $r$ in number will go, giving us a bijection from this action to the arrangements of said objects. This action can be performed in $\binom n r$ ways, so that is also the number of arrangements. And of course the arrangements may also be counted the way you have done, which is simply de-permute the identical objects in the arrangements of $n$ objects.

A combination is essentially an unordered (depermuted) permutation. Think about how you would select 4 objects from 9: the number of options you have for the first selection is 9, 2nd is 8… 4th is 5, or essentially a permutation of 4 objects from a set of 9. But once you have chosen your 4 objects you simply have 4 objects and the order you chose: them in does not matter, so we depermute the arrangement to get the formula for $\binom n r$, which is $\frac{n!}{r!n-r!}$.


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.