Suppose I have a set of elements $$ S = \lbrace A,B,B,D,E \rbrace$$

Then the number of distinct permutations of size 5 is

$$\frac{5!}{2!} = 60$$

This is because $S$ contains a ‘copy’ of B.

But by definition, in a set of elements, each element is distinct. However, now I’m essentially saying “wait actually B and B aren’t distinct.”

So why isn’t the set $$ S = \lbrace A,B,D,E \rbrace$$ if the B elements are not distinct? Notice the permutations of this set are very different

$$4! = 24$$

Are there two different kinds of being distinct here?

  • 3
    $\begingroup$ You should think of $S$ as a multiset, not a set; one in which multiple copies do matter. Alternatively, put a yellow sticker on one of the $B$s and a green sticker on the other one so that they are now distinct. Count the number of permutations; then remove the stickets. Figure out how many ways the final permutation could have occurred to get the correct divisor. $\endgroup$ – Arturo Magidin Dec 17 '18 at 22:43
  • 2
    $\begingroup$ @ArturoMagidin Can you add this as an answer? I think this is what I am looking for. Perhaps expand a bit if you can. $\endgroup$ – Stan Shunpike Dec 17 '18 at 22:49

You should see the counts as the number of outputs of two different experiments:

First we have a bag of 5 letter tiles (a la Scrabble say) with $A,B,B,D,E$ tiles. We draw 5 tiles from the bag and put them in a row in order we draw them. We have 5 draws, so $5!$ many permutations of the tiles. But in reality we cannot (in the end) distinguish the two B's (We could have marked them and then we'd have $5!$ different results): so the number of end results (sequences of 5 letters) is halved, because for every permutation $\ldots B_1\ldots B_2\ldots$ have a seocnd equivalent one $\ldots B_2\ldots B_1\ldots$.

The second experiment we have a bag with four tiles $A,B,D,E$ and counts the number of possible permutations from a draw of $4$ letters put in a row, so there we count sequences of $4$ letters, not of $5$. Hence the difference in counts.


take a simpler case $\{A,B,B\}$ vs $\{A,B\}$. First one will have $ABB,BBA,BAB$, however the second one only $AB,BA$. Note that when $BB$ are next to each other it can be mapped to the single instance case one-to-one, but not when there are separated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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