0
$\begingroup$

And should I use repetition allowed, or repetition not allowed formula?

A binary string is a string with 1's and 0's in a row. {0,1} is a different string from {1,0}. Say I'm considering binary strings of length 6 and I want to count the number of strings with 3 1s (and 3 0s). Should this be regarded as a combination or permutation problem? And is this considered to be "repetition allowed?" It seems like it's "repetition required."

$\endgroup$
1
$\begingroup$

You can often solve a counting problem by working out in how many ways you can choose the required object. When doing so, there are a number of questions that are nearly always worth asking yourself.

  1. What am I choosing? In this example, are you choosing the $1$ or the $0$s? No - you know all about these, there are three $1$s and three $0$s. What you are choosing is the places in which the $1$s and $0$s will occur. In this case, once you have chosen the places for the $1$s you know where the $0$s go (namely, in all the remaining places), so we only have to choose places for the $1$s.
  2. So, you have to choose three places from six possibilities. Is repetition allowed? If you are not sure, make up a specific instance and ask whether or not it makes sense. So, could we put three $1$s in places $6,6$ and $6$? Obviously not - the three $1$s must go in different places. Note how important question 1 is - if you thought you were choosing the $1$s (rather than the places) you would certainly say that repetition is allowed because there are three of them. This would be wrong.
  3. Is order important? Once again, if you are not sure, ask yourself about a specific instance. For example, if I choose to put $1$s in places $1,2$ and $4$, is that the same or different from putting them in places $2,4$ and $1$? I hope it is clear that it is the same (the word is $110100$ in both cases) and therefore order is not important.

So, we have to choose $3$ places from $6$, with repetition not allowed and order not important, and the number of ways to do this is $C(6,3)$.

$\endgroup$

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.