# Compositions & Transpositions of permutations

Consider the set of all permutations $$S_n$$.

Fix an element $$\tau\in S_n$$.

Then the sets $$\{\sigma\circ\tau\mid \sigma\in S_n\}= \{\tau \circ\sigma\mid \sigma\in S_n\}$$ have exactly $$n!$$ elements.

I am confused what the above theorem stands for? How can $$\{\sigma\circ\tau \mid \sigma\in S_n\}=\{\tau \circ\sigma \mid \sigma \in S_n\} = S_n$$?

(This has been stated as an equivalence statement of the above theorem)? What is the logic behind? Does the term element above refer to a complete permutation? See link.

## 2 Answers

If $$\sigma \in S_n$$ then $$\sigma \circ \tau^{-1} \in S_n$$, and $$\tau^{-1} \circ \sigma \in S_n$$ so multiplying by $$\sigma$$ on either side is a surjective map $$S_n \rightarrow S_n$$.

The first thing you should note is that if $$\tau, \sigma \in S_n$$, then $$\tau \circ \sigma \in S_n$$. This means that if you have two permutations, then their product is also a permutation of the same permutation group.

You also know that $$S_n$$ has exactly $$n!$$ elements.

Now imagine I give you a set $$A$$ where all of its elements are permutations from $$S_n$$. Mathematically speaking this means that $$A \subset S_n$$.

Now let's think about how many elements $$A$$ can have.

If $$A = S_n$$, then $$A$$ contains all permutations from $$S_n$$. So how many elements does $$A$$ have? Exactly $$n!$$, since there are exactly $$n!$$ permutations in $$S_n$$.

What if $$A$$ contains exactly $$n!$$ permutations from $$S_n$$? Then $$A$$ must contain all permutations from $$S_n$$, since there are only $$n!$$ elements in $$S_n$$. So $$A = S_n$$

What I have shown is that any set $$A$$ that only contains permutations from $$S_n$$ has exactly $$n!$$ elements if and only if $$A = S_n$$.

The key point here is that $$A$$ only has permutations from $$S_n$$ as its elements. And if it has $$n!$$ permutations (that is, all permutations) as its elements, then it must be equal to $$S_n$$ (and vice versa).

This is essentially all the proposition says.

The set $$\left\{\sigma \circ \tau : \sigma \in S_n\right\}$$ is a subset of $$S_n$$, that is it only contains permutations from $$S_n$$. Why? See my first statement at the top of this post.

So $$\left\{\sigma \circ \tau : \sigma \in S_n\right\} = S_n$$ is equivalent to saying that $$\left\{\sigma \circ \tau : \sigma \in S_n\right\}$$ has exactly $$n!$$ elements.

The same holds for $$\left\{\tau \circ \sigma: \sigma \in S_n\right\} = S_n$$