Can one produce permutations from permutations on the same elements

combinatoricspermutations

I've just started studying combinatorics and I'm currently trying to understand permutations. So far I'd like to say that I do understand:

  • Permutations without repetitions
  • Partial permutations without repetitions
  • Permutations with repetition

My question is if one can produce permutations out of permutations on the same elements?

Say for the 5 elements:
(A B C C D)
I first produce the possible permutations with only 2 of these 5 elements, $$5!/3!=20$$ permutations.

Now out of the 20 permutations with only 2 elements, I want to produce the permutations with regards to repetition, or in other words, filter out the repetitions that occur among the 20 permutations. Doing it manually by hand I came to the conclusion that there are 7 repetitions among the 20, so the amount of permutations I am looking for are 13.

Is there a way of producing these 13 permutations out of formulas? I'm not necessarily asking for the solution (unless they only involve the 3 types of permutations I mentioned), but if it is possible and which method(s) I should read about concerning such a problem. I found something called "Permutations on multisets", but I'm not really sure that's it?

Best Answer

First of all, for this particular problem, I prefer N.F.Taussig's direct approach to the one that I will present in this answer (i.e. an indirect approach). However, for other similar problems, sometimes an indirect approach will be easier.

Alternative approach:

You start with the computation of

$$\frac{5!}{(5-2)!} = 20.$$

Now, you look for a way of enumerating the repetitions from this group, so that they can be deducted.

There are two mutually exclusive ways that a repetition can occur:

  • If the two items selected contain exactly one C.
  • If the two items selected contain both C's.

To facilitate the enumeration, assume that the (C) elements are labeled C-1 and C-2.

There are $3 \times 2 = 6$ repeated items of form (C-1,x) or (x,C-1) $~: ~\text{x} \in \{\text{A}, \text{B}, \text{D}\}.$

The repetition comes from (C-2,x), (x,C-2).

There is also one more repetition.

In the $5 \times 4$ computation, the permutations (C-1,C-2) and (C-2,C-1) are also counted separately. So, to remove repetitions, one of these permutations must also be deducted.

Therefore, the final enumeration is

$$\frac{5!}{(5-2)!} - \left[3 \times 2\right] - 1.$$

Related Question