Permutation Formulas to Know for Combinatorics

Understanding permutation formulas is key in Combinatorics, as they help us count arrangements of objects. From basic arrangements to complex scenarios with restrictions, these formulas reveal how order and selection impact the way we organize items.

1. Basic permutation formula: P(n, r) = n!/(n-r)!

   • Represents the number of ways to arrange r objects from a set of n distinct objects.
   • The factorial notation (n!) indicates the product of all positive integers up to n.
   • The formula accounts for the order of selection, making it crucial for arrangements.

2. Permutations with repetition: n^r

   • Used when selecting r objects from n options where repetition is allowed.
   • Each of the r positions can be filled by any of the n objects independently.
   • This results in a total of n multiplied by itself r times.

3. Circular permutations: (n-1)!

   • Applies when arranging n objects in a circle, where rotations are considered identical.
   • Fixing one object reduces the problem to arranging the remaining (n-1) objects linearly.
   • Useful in problems involving round tables or circular arrangements.

4. Permutations with indistinguishable objects: n! / (n1! * n2! * ... * nk!)

   • Used when some objects are identical, leading to overcounting in arrangements.
   • The denominator accounts for the indistinguishable objects by dividing by their factorials.
   • Essential for calculating arrangements in scenarios with repeated items.

5. Derangements (permutations with no fixed points): !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)

   • Represents the number of ways to permute n objects such that no object appears in its original position.
   • The formula uses the principle of inclusion-exclusion to count valid arrangements.
   • Important in problems involving matching or assignments where fixed positions are undesirable.

6. Partial derangements: D(n,k) = C(n,k) * !(n-k)

   • Calculates the number of derangements of n objects where exactly k objects are fixed.
   • Combines the selection of k fixed objects (C(n,k)) with the derangement of the remaining (n-k) objects.
   • Useful in scenarios where some items must remain in specific positions.

7. Permutations with restrictions (forbidden positions)

   • Involves counting arrangements where certain objects cannot occupy specific positions.
   • Often requires the use of complementary counting or inclusion-exclusion principles.
   • Important for solving problems with constraints on placement.

8. Lexicographic order of permutations

   • Refers to the arrangement of permutations in dictionary order based on the sequence of elements.
   • Useful for generating permutations systematically and efficiently.
   • Helps in understanding the structure and organization of permutation sets.

9. Inversions in permutations

   • An inversion is a pair of elements in a permutation where the first element appears after the second.
   • The count of inversions provides insight into the arrangement's order and can be used in sorting algorithms.
   • Important for analyzing the properties of permutations and their transformations.

10. Permutation groups and cycle notation

    • A permutation group is a set of permutations that can be combined through composition.
    • Cycle notation provides a compact way to represent permutations by showing the cycles of elements.
    • Essential for studying the algebraic structure of permutations and their symmetries.