When to take into account a subset's permutation

53 Views Asked by At

Although this question had been asked many times before, I will use it as an example for my question.

Q: We have $m$ ones and $n$ zeros, where $m > n$. How many different ways of ordering them in a string without having any consecutive ones.

My answer: First we choose where to put the ones, which is $\binom{m+1}{n}$. Now we order the zeros and ones: $m! \cdot n!$

But the correct answer is just: $\binom{m+1}{n}$

My question: Why did we not take into consideration the ordering of the $0$ or the $1$?

1

There are 1 best solutions below

0
On BEST ANSWER

You don't need to worry about the permutations of the $0$'s and $1$'s in any given combination. As far as a combintion is concerned ${\color{red}{0}}{\color{black}{1}}{\color{blue}{0}}$ is the same as ${\color{blue}{0}}{\color{black}{1}}{\color{red}{0}}$. That means you don't need to label each $0$ and $1$ individually and multiply by the number of the permutations each of the sets of $0$'s and $1$'s would make once you have calculated the correct number of combinations.