Permutation Notation, Counting, and Algebraic Structure

All flashcards

Permutation

A bijection from a finite set to itself, equivalently a rearrangement of all its elements.

One-line notation

A list of the images of the inputs in a chosen order.

Symmetric group $S_n$

The group of all permutations of an $n$-element set, with composition as its operation.

Cycle type

The list of lengths of the disjoint cycles in a permutation.

Multiset arrangement count

For multiplicities $m_1,\ldots,m_r$ among $n$ objects, the number of distinct arrangements is $\frac{n!}{m_1!\cdots m_r!}$.

Quiz questions

1. Under the convention $(\sigma\tau)(x)=\sigma(\tau(x))$, which permutation acts first?Answer: $\tau$ acts first.
2. How many circular arrangements are possible for $n$ distinct objects when rotations count as identical?Answer: $(n-1)!$
3. How many distinct arrangements can be made from five objects when exactly two are identical and the other three are distinct?Answer: $\frac{5!}{2!}=60$
4. What is the inverse of the cycle $(1\ 4\ 3)$?Answer: $(1\ 3\ 4)$
5. What is the parity of the permutation with one-line notation $231$?Answer: Even, because it has two inversions.