Permutation

Permutations RGB

Rubik's cube

Permutations with repetition cropped

Symmetric group 3; Cayley table; matrices

15-Puzzle

Permutation generation algorithms10

Permutation refers to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. Permutations differ from combinations, which are selections of some members of a set regardless of order. In the context of mathematics, particularly in algebra and combinatorics, permutations are essential in various problems and equations.

Definition

A permutation of a set is a rearrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The number of permutations of a set with n distinct elements is denoted as n!, read as n factorial, and represents the product of all positive integers less than or equal to n. For example, the number of permutations of a set with three elements {a, b, c} is 3! = 3 × 2 × 1 = 6.

Types of Permutations

There are two main types of permutations:

1. Permutations without Repetition: This is the scenario where the order of selection matters, and each item can only be selected once. The formula to calculate the number of permutations in this case is n! / (n-r)!, where n is the total number of items, and r is the number of items to be chosen.

2. Permutations with Repetition: In this case, items can be chosen more than once, and the order of selection still matters. The formula for calculating permutations with repetition is n^r, where n is the total number of items, and r is the number of items to be chosen.

Applications

Permutations have applications in various fields such as mathematics, computer science, cryptography, and game theory. They are used in analyzing algorithms, developing cryptographic systems, solving puzzles like the Rubik's Cube, and in the mathematical study of games and decision processes.

Permutation Groups

In abstract algebra, a permutation group is a group that consists of permutations of a given set, with the group operation being the composition of permutations. This concept is a central organizing principle in the study of symmetric structures and algebraic equations.

Generating Permutations

There are several algorithms for generating all possible permutations of a given set, such as the Heap's algorithm and the Steinhaus–Johnson–Trotter algorithm. These algorithms are used in computer science for solving problems that require considering all possible arrangements of a set of items.

See Also

• Combination
• Factorial
• Permutation group
• Algorithm