Why is the number of bit strings of length n that contain r 1's a problem solved using the formula for combinations instead of permutations?

My textbook answer key uses the generalized combination formula for these types of problems, but I thought since the order of the bits in the string mattered it should be a permutation scenario.


closed as off-topic by Namaste, KonKan, José Carlos Santos, Stefan4024, Shailesh Dec 2 '17 at 2:40

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Stefan4024, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What exactly do you mean by "combination problem"? Order matters, yes, but the name of the type of the solution doesn't. $\endgroup$ – vrugtehagel Dec 1 '17 at 19:14
  • $\begingroup$ My textbook says this is solved via combination c(n,r). I thought the combination formula was used for scenarios where the order of the elements doesn't matter, but when we are talking about bit strings shouldn't the order in which the digits 0 and 1 appear matter? $\endgroup$ – foobarbaz Dec 1 '17 at 19:16
  • $\begingroup$ The length-6 string with two ones 101000 could be described as the string where you have a $1$ in the first position and a $1$ in the third position and in no others. This could also be described as the string where you have a $1$ in the third position and a $1$ in the first position. In this sense, the "order" in which I tell you which of the spaces were filled doesn't actually matter (though which positions they are absolutely does matter). Both sentences described the same string. $\endgroup$ – JMoravitz Dec 1 '17 at 19:28
  • $\begingroup$ I recommend instead thinking of the binomial coefficient c(n,r) (which you'll commonly instead see notated as $\binom{n}{r}$) as the number of ways to select an $r$-element subset from a set of $n$ elements. In this case, we are selecting which $r$ of the positions are to be occupied by ones. That "order doesn't matter" is just a reference to the fact that sets and subsets can be written in many equivalent ways and these are not tuples or sequences. $\endgroup$ – JMoravitz Dec 1 '17 at 19:29

It's because all the 1's are indistinguishable. For example, if you have 1001 and the 1's and 0's were distinguishable, you have $4!$ options, but since they aren't you have $4!$ divided by $2! * 2!$ (which is equivalent to 4 choose 2).

As a result, to find out the total number of ways to have r 1's in a string of length n, you have to find the total way to choose r positions out of the n total to assign 1 to.


Yes the order matters, but we still use $c(n,r)$ (more commonly denoted ${n\choose r}$) because we essentially want to find the number of ways to pick $r$ zeroes out of a string with length $n$ and change those to $1$'s, resulting in the amount of strings with exactly $r$ ones.


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