1
$\begingroup$

I am reading the structure of multipartite entanglement from section 3.3. It is stated there that the number of possible partitions of $N$ parties into $m$ parts is given by $\frac{m^N}{m!}$.

I could not understand how they are doing the calculation. Can anyone please help as to how should I proceed?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is a purely combinatorics problem. Let us index our registers by $1,\cdots,N$. We have $m$ "bags" $P_1,\cdots,P_m$ into which which we want to put our indexes.

  • For the first index ($1$), we have $m$ choices: we can put it in any of the $P_i$.
  • For the second index ($2$), well, it's still the case, so we also have $m$ choices.
  • ...
  • For the last index ($N$), we still have $m$ choices.

All in all, this results in $m^N$ possibilities. However, we mustn't count the order of the partitions. For instance, if $N=3$ and $m=2$, $P_1=\{1\}$ and $P_2=\{2, 3\}$ corresponds to the same partition as $P_1=\{2, 3\}$ and $P_2=\{1\}$.

That is, the way we counted our sets, we have counted each configuration along with all its permutations. There are $m!$ of them, so we must divide by this number in order to get the final result.

Note that the way they counted, they allow for $P_i$ to be nil sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.