0

Sorry if my question is not mathematically correct. Please help me fix it if there is a better way to phrase it.

So first of all, I know that if you have a list of numbers {1, 2, 3} then the number of permutations is 3 x 2 x 1 = 6 different combinations where order does matter.

But what if you have repeating elements? For example {1, 1, 2} So the order still matter but picking the first '1' followed by the second '1' is the same thing as picking the second '1' first before picking the first '1'? How many different combinations would there be?

Doing it by hand, I know that there are 3. They are {1, 1, 2} {1, 2, 1} and {2, 1, 1} but how do you generalise it? For example, say if you have {1, 1, 2, 2, 2, 3, 3, 3, 3}, how do you know how many permutations there are?

davidx1
  • 281

1 Answers1

1

I will give you a hint by answering your example.

You have $9$ places, first you take $4$ places for the $3$'s, you have $\binom{9}{4}$ possibilitis to do it.

Now you are left with $5$ places. Take $3$ of them for the $2$'s, you have $\binom{5}{3}$ possibilitis to do it.

Now you have exactly $2$ places for the ones. All in all you have $$\binom{9}{4}\binom{5}{3}$$ possibilitis.

Here $$\binom{n}{k}=\frac{n!}{(n-k)!k!}.$$

You can also think about it as follows.

You have $9!$ permutations, but you need to divide by the "inner" permutations of all the $3$'s, all the $2$'s and all the ones. Again, all in all you have $$\frac{9!}{4!3!2!}. $$

Ofir Schnabel
  • 3,891
  • Thank you for the fast reply! I think I'm beginning to understand... but why is it divide by the "inner" permutations and not minus the "inner" permutations? – davidx1 Jul 08 '15 at 10:03
  • try to understad it from your ${1,1,2}$ example. – Ofir Schnabel Jul 08 '15 at 10:05
  • Oh I get it, because while a repeating element like {1, 1} have N "inner" permutations, there are many places where this can occur, in this example, position [1 2], position [1 3] and position [2 3]. And since these inner permutations don't count, they effectively increased the total permutation count by N times. Thanks a lot! – davidx1 Jul 08 '15 at 10:18
  • You got it, well done. – Ofir Schnabel Jul 08 '15 at 10:19