Permutaci

Permutaci, or permutation, is a rearrangement of the elements of a set into a new order. If the set contains n distinct elements, the number of possible permutations is n!, and each permutation can be viewed as a bijection from the set to itself that reassigns each element to a position in the reordered arrangement. In practice, permutations are often written in one-line notation, listing the images of the elements, or in cycle notation, expressing the permutation as a product of disjoint cycles.

Key concepts include the identity permutation, which leaves all elements in place, and transpositions, which swap two elements. Any permutation can be decomposed into disjoint cycles, and this cycle structure determines many properties. The parity of a permutation is even or odd, depending on whether it can be written as an even or odd number of transpositions; this gives rise to the sign of the permutation. The set of all permutations on n elements forms the symmetric group S_n under composition of mappings.

Counting and structure: The total number of permutations is n!. The cycle type of a permutation determines its conjugacy class in S_n. Generating S_n can be done with transpositions, or with simple adjacent transpositions. Derangements, permutations with no fixed points, form a well-known subfamily with applications in probability and combinatorics.

Applications: permutations model reordering processes, sorting algorithms, seating arrangements, cryptographic algorithms, and many counting problems in mathematics and computer science. They provide a foundational concept in group theory and the study of symmetry.