Problem 3 - Applied Discrete Structures

Question

Let \(A=\\{1,2,3\\}\). (a) List all permutations of \(A\). (b) Find the inverse and square of each of the permutations of part a, where the square of a permutation, \(f,\) is the composition \(f \circ f\). (c) Show that the composition of any two permutations of \(A\) is a permutation of \(A\). (d) Prove that if \(A\) is any set where \(|A|=n,\) then the number of permutations of \(A\) is \(n !\)

Step-by-Step Solution

Answer

There are 6 permutations of \(A\), each having inverses and squares; compositions are permutations, and permutations count is \(n!\).

Step 1: Listing Permutations

We start by listing all possible permutations of set \(A=\{1,2,3\}\). A permutation is an arrangement of all the elements of a set. For the set \(A\), we have the following permutations: \((1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)\).

Step 2: Find Inverses of Permutations

For each permutation, we find its inverse. The inverse of a permutation \(f\) is the permutation that, when composed with \(f\), results in the identity permutation \((1,2,3)\). The inverses are:- Inverse of \((1,2,3)\) is \((1,2,3)\)- Inverse of \((1,3,2)\) is \((1,3,2)\)- Inverse of \((2,1,3)\) is \((2,1,3)\)- Inverse of \((2,3,1)\) is \((3,1,2)\)- Inverse of \((3,1,2)\) is \((2,3,1)\)- Inverse of \((3,2,1)\) is \((3,2,1)\)

Step 3: Find Squares of Permutations

For each permutation, the square is calculated by composing the permutation with itself. The squares are:- \((1,2,3) \circ (1,2,3) = (1,2,3)\)- \((1,3,2) \circ (1,3,2) = (1,2,3)\)- \((2,1,3) \circ (2,1,3) = (1,2,3)\)- \((2,3,1) \circ (2,3,1) = (3,2,1)\)- \((3,1,2) \circ (3,1,2) = (2,3,1)\)- \((3,2,1) \circ (3,2,1) = (1,2,3)\)

Step 4: Composition of Two Permutations

By definition, a permutation is a bijective function from the set to itself. The composition of two bijective functions is also bijective. Hence, the composition of any two permutations of \(A=\{1,2,3\}\) results in another permutation of the same set. Example:- \((1,2,3) \circ (2,3,1) = (2,1,3)\), which is a permutation of \(\{1,2,3\}\).

Step 5: Prove Number of Permutations is n!

The number of permutations of a set \(A\) of size \(n\) is given by \(n!\), which is the factorial of \(n\). This arises because for the first position in the permutation, there are \(n\) choices, for the second position \(n-1\) choices, down to 1 choice for the last position. Therefore, the total number of permutations is the product \(n \times (n-1) \times (n-2) \times \ldots \times 1 = n!\). For \(|A|=3\), there are \(3! = 3 \times 2 \times 1 = 6\) permutations.

Key Concepts

Inverse Permutation

An inverse permutation is essentially the reverse of a given permutation. If you think of a permutation as mapping elements to new positions, the inverse permutation undoes this process, returning the elements to their original places.
To find the inverse of a permutation, you swap the positions back to their original order. For example, if a permutation swaps the first and second elements, its inverse will swap them again.
Here's a simple way to understand it:

• Find where the first element went in the permutation, and then place it back in the first position.
• Repeat this for all elements.

The role of the inverse permutation is vital in group theory, especially when verifying if two permutations can be reversed to return to the original order.

Composition of Permutations

The composition of permutations involves combining two permutations to form a new one. Think of it as performing one shuffle followed by another.
For permutations, this operation must maintain order without losing any elements.
The composition is associative, meaning \((f \circ g) \circ h = f \circ (g \circ h)\). This helps in larger computations and proofs.
Consider permutations as functions. When you compose two permutations, you perform the first shuffle and then the next. This results in a single shuffle that is the combination of both initial ones.

• This is best visualized by tracing the path of each element throughout the compositions.
• For example, if one permutation changes 1 to 2, and another changes 2 to 3, the composition changes 1 to 3 directly.

Understanding compositions helps in studying permutation cycles and their structures.

Factorial

Factorials are key in counting permutations. The notation \(!n\) means the product of all positive integers up to \(n\). So, \(n! = n \times (n-1) \times \cdots \times 1\).
Given this formula, we calculate how many ways we can organize items. For \(n = 3\), the factorial \(3!\) equals \(6\), indicating six distinct permutations.
It arises mainly in probability and combinatorics to simplify counting tasks.

• The factorial grows fast as \(n\) increases, which is important in complexity analysis too.
• Understanding factorials is crucial as they appear frequently in mathematical proofs and calculations related to arrangements.

Bijective Function

A bijective function is a perfect pairing between two sets where every element in one set maps onto a unique element in another, with no leftovers or repeats. Every element connects directly to one in the opposite set.
For permutations, considering them as bijective ensures every position in a permutation is filled exactly once.
This property of bijections makes permutations reversible, allowing for inverses.
An easy way to think of it is like a matching game:

• Each card (element) matches only one other, leaving no cards unmatched.
• In mathematics, this concept ensures transformations maintain the entire structure.

Using bijective concepts helps us to solidify our understanding of both individual permutations and composed permutations.