Permutations

In the world of mathematics, the concept of a permutation involves the arrangement of a set's elements in a specific sequence or order.

Take, for instance, a sequence of colored balls: red, blue, green. This is a classic example of a permutation.

By altering the sequence of these balls, we craft a new permutation. A rearrangement to blue, green, red showcases this beautifully.

When dealing with a set of n elements, a permutation represents any possible arrangement of these elements in a sequence.

A Closer Look at Permutations

Consider a simple set of three elements as an example:

$$ X = \{1, 2, 3\} $$

The beauty of permutations lies in the myriad ways we can order these three numbers.

For three distinct items, there exist 6 unique permutations.

$$ 3! = 3 \times 2 \times 1 = 6 $$

And here are all the possible permutations of the set $1, 2, 3$:

\(123\)

\(132\)

\(213\)

\(231\)

\(312\)

\(321\)

What makes each permutation distinct is the unique order of the same numbers.

On a broader scale, for any set comprising \(n\) objects, the total permutations are $ n! $ (n factorial), symbolizing

$$ n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1 $$

Permutations are crucial in various disciplines, from probability and statistics to game theory and cryptography, illuminating patterns and solving complex problems.

Permutations can be elegantly represented using specific notations:

$$ \begin{pmatrix} a_1 & a_2 & a_3 & \dots \\ b_1 & b_2 & b_3 & \dots   \end{pmatrix}  $$

This notation, with the first row (a₁, a₂, ...) indicating the initial arrangement and the second row (b₁, b₂, ...) the final one, shows how each element transitions from its original to its new position.

An example of this is the transition from (123) to (213):

$$ \begin{pmatrix} 1 & 2 & 3  \\ 2 & 1 & 3  \end{pmatrix}  $$

This notation indicates that the positions of 1 and 2 are swapped, while 3 remains unchanged.

A more concise representation is possible by only noting changes, leaving out elements that stay the same:

$$ (1,2) $$

Or even more streamlined,

$$ (12) $$

This implies a swap between elements 1 and 2, with the unchanged element 3 not mentioned for brevity.

Further Exploration

Delving into a more complex example, consider a set of five elements:

$$ X = \{1, 2, 3, 4, 5\} $$

To depict the permutation from (12345) to (31254), we can employ the following notation:

$$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5  \\ 3 & 1 & 2 & 5 & 4   \end{pmatrix}  $$

A more compact way to express the same permutation is through the product of disjoint cycles:

$$ (132) (45) $$

Here, (132) signifies a cycle where 1 is replaced by 3, 3 by 2, and 2 by 1. Meanwhile, (45) represents a simple swap between 4 and 5. This approach not only simplifies the representation but also provides insight into the permutation's structure.

Even the cycle (321) can be decomposed into transpositions: (321)=(32)(31).

$$ (32) (31) (45) $$

In this scenario, 3 takes the place of 2, then 3 replaces 1, and finally, 4 swaps with 5, leading to the same end result: (31254).

Verification. Starting from the original permutation: $$ (12345) $$ Applying the transposition (32) swaps 3 with 2 $$ (13245) $$ Next, the transposition (31) exchanges 3 and 1's positions  $$ (31245) $$ Lastly, applying the transposition (45) swaps 4 with 5 $$ (31253) $$ The end result remains consistent.

Exploring Permutation Types

Permutations fall into two primary categories:

• Permutations Without Repetition
  This type refers to arranging all elements of a set uniquely, without leaving any out or duplicating any.

  Take the set {1, 2, 3}, for instance. The permutations we can derive from it are 123, 132, 213, 231, 312, and 321. For a set containing n elements, the total number of such permutations is n! (n factorial), representing the product of all positive integers up to n.

• Permutations With Repetition
  When elements within the set repeat, we deal with permutations with repetition. Calculating the number of possible permutations in these instances requires a consideration of these repetitions.

  For example, with the set {1, 1, 2}, the permutations are limited because the two '1's are indistinguishable. Thus, only three permutations are possible: 112, 121, 211. The formula to calculate permutations in such cases is to divide n! by the factorial product of the frequencies of each repeated element, h!k! $$ \frac{n!}{h!k!} $$. Here, with n=3 elements and one element repeating twice (h=2), the calculation is $$ \frac{n!}{h!k!} = \frac{3!}{2!} = \frac{3 \cdot 2 \cdot 1}{2 \cdot 1} = \frac{6}{2} = 3 $$

The Art of Permutation Composition

Composing permutations is about sequentially applying two or more permutations to a set.

This process is like executing a series of moves, one after the other. You start with the initial permutation and layer on the next, observing how each step transforms the arrangement.

Important to note is the right-to-left order of composition. The permutation positioned on the right is applied first, leading to a scenario where the composition of permutations may not be commutative. That is, the outcome of \( p \circ q \) can differ from \( q \circ p \), showcasing the intricacies involved in permutation composition within the context of \( S_3 \).

An Illustrative Example

Consider two permutations, \( p \) and \( q \), applied to the set \( \{1, 2, 3\} \), starting with the sequence 123.

Let's say \( p \) swaps 1 with 2 but keeps 3 as is, while \( q \) swaps 1 with 3, leaving 2 untouched. The permutations are thus represented as:

 \( p = (1 2) \)

 \( q = (1 3) \)

In action, p=(1,2) switches the positions of 1 and 2. Meanwhile, q=(1,3) swaps 1 with 3.

To compose \( p \circ q \), we first apply \( q \), and then \( p \), to the initial sequence.

By applying \( q = (1 3) \) to 123, we get:

\( q(1) = 3 \)

\( q(2) = 2 \)

\( q(3) = 1 \)

With q=(1,3), swapping 1 with 3 transforms the sequence from 123 to 321, keeping 2 in its original position.

Applying \( p  (1 2) \) to this new configuration \( 321 \):

\( p[q(1)] = p(3) = 3 \)

\( p[q(2)] = p(2) = 1 \)

\( p[q(3)] = p(1) = 2 \)

Here, p=(1,2) further modifies the sequence by swapping 1 and 2, resulting in a final configuration of 312.

The culmination of \( p \circ q \) offers us the permutation \( (1 3 2) \), showcasing a sophisticated dance of numbers that swaps 1 with 3 and then 3 with 2, revealing the elegance and complexity of permutation composition.