0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Multinomial_theorem $\endgroup$
    – Angina Seng
    Commented Oct 12, 2018 at 15:38
  • $\begingroup$ 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? $\endgroup$
    – hardmath
    Commented Oct 13, 2018 at 4:45

1 Answer 1

Reset to default
0
$\begingroup$

Ok, I thought about it and it's not that hard after all.

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!).$

$\endgroup$
1
  • $\begingroup$ The answer you proposed in your original question is correct. $\endgroup$
    – N. F. Taussig
    Commented Oct 13, 2018 at 11:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .