# How many permutations can there be?

Suppose I have a set $$\{1,...,1,2,...,2,3,...,3,...,n,...,n\}.$$ How many permutations can I have? I did try to solve this but I could only do it by brute force and for small $$n$$. I think the answer is $$\frac{N!}{k_1!k_2!\cdot\cdot\cdot k_n!}$$ Where $$k_i$$ is the amount of $$i$$ in the sum and $$N$$ is the total number of elements.

I have trouble excluding cases where I count a permutation multiple times.

• en.wikipedia.org/wiki/Multinomial_theorem Commented Oct 12, 2018 at 15:38
• You've not phrased your problem in an easy to understand fashion. A permutation is conventionally an arrangement of distinct items, but you are asking something about a multiset, a collection containing repeated (identical) items. Is a "permutation" in your sense determined by a mapping of locations to values? Commented Oct 13, 2018 at 4:45

Suppose you have this set $$\{x_1,x_2,...,x_n\}.$$ For this set you will have $$n!$$ permutations. Every permutation will contain $$x_1, x_2$$ and $$x_3$$ somewhere in them. Suppose you have an arbitrary permutation, where you remove $$x_1,x_2$$ and $$x_3$$ and fill their spots with a blank. Given this one 'permutation' how many permutations can you generate by placing your three elements? $$3!,$$ because that is how many ways you have to arrange $$x_1,x_2$$ and $$x_3$$ onto those blanks. Now suppose $$x_1=x_2=x_3.$$ This means all the $$3!$$ permutations are the same. So for any arbitrary permutation you have $$3!-1$$ permutations that are the same. In other words the $$3!$$ permutations that were unique when all your elements where unique are now the same. So the total amount of permutations is $$n!/3!.$$ - The argument holds for any number of identical elements.
Now suppose $$x_1=x_2=x_3\neq x_4=x_5.$$ Assume all the elements are the same so the total number of permutations is $$n!$$ then say that $$x_1=x_2=x_3$$ and say that the total number of permutations is $$n!/3!.$$ Finally say that $$x_4=x_5$$ and say that now the total number of permutations is $$n!/(3!2!).$$