3.2 Permutations with and without Repetition

Permutations are all about arranging objects in different orders. They're key to solving counting problems where the sequence matters. Whether you're dealing with unique items or allowing repeats, permutations pop up everywhere from math to everyday life.

Understanding permutations is crucial for tackling more complex combinatorial problems. They're the building blocks for many counting techniques and help us make sense of arrangements in various fields, from computer science to genetics.

Permutations and their properties

Definition and key characteristics

Top images from around the web for Definition and key characteristics

• 

  Combinatorics Overview View original

  Is this image relevant?

• 

  Permutations | College Algebra View original

  Is this image relevant?

• 

  Category:Permutations - Wikimedia Commons View original

  Is this image relevant?

• 

  Combinatorics Overview View original

  Is this image relevant?

• 

  Permutations | College Algebra View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition and key characteristics

• 

  Combinatorics Overview View original

  Is this image relevant?

• 

  Permutations | College Algebra View original

  Is this image relevant?

• 

  Category:Permutations - Wikimedia Commons View original

  Is this image relevant?

• 

  Combinatorics Overview View original

  Is this image relevant?

• 

  Permutations | College Algebra View original

  Is this image relevant?

1 of 3

• Permutation is an arrangement of objects in a specific order, where the order matters
  • Arrangements are considered distinct if they differ in the order of objects
  • Changing the position of any object creates a new permutation (rearranging letters in a word, changing the order of numbers in a sequence)
• Permutations can be with or without repetition
  • Permutations without repetition involve arranging distinct objects, where each object can only be used once (arranging a set of unique books on a shelf)
  • Permutations with repetition allow objects to be repeated in the arrangement (creating a PIN code using digits 0-9, where digits can be repeated)
• The number of permutations is affected by the total number of objects and the number of objects being arranged
  • A larger pool of objects generally results in a greater number of possible permutations
  • The number of objects being arranged (r) determines the size of each permutation

Permutations vs. combinations

• Permutations are different from combinations, where the order does not matter
  • In combinations, arrangements are considered identical if they contain the same objects, regardless of the order (selecting a team of 5 people from a group of 10, where the order of selection doesn't matter)
  • The number of combinations is typically smaller than the number of permutations for the same set of objects
• Distinguishing between permutations and combinations is essential for solving counting problems accurately
  • Permutations are used when the order is important and arrangements with different orders are considered distinct
  • Combinations are used when the order is irrelevant and arrangements with the same objects are considered identical

Calculating permutations

Formula for permutations of distinct objects

• The number of permutations of n distinct objects is denoted as P(n, r) or nPr, where r is the number of objects being arranged
  • n represents the total number of objects available
  • r represents the number of objects being selected and arranged
• The formula for calculating the number of permutations of n distinct objects taken r at a time is: $P(n, r) = \frac{n!}{(n - r)!}$
  • $n!$ represents the factorial of n, which is the product of all positive integers less than or equal to n ($n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$)
  • The formula can be derived by considering the number of ways to fill r positions from n objects, where each object can only be used once

Special case: permutations of all objects

• When r = n, the formula simplifies to $P(n, n) = n!$, representing the number of permutations of all n objects
  • In this case, all available objects are being arranged, so the number of permutations is simply the factorial of n
  • This special case is known as a "full permutation" or "complete permutation" (arranging all the letters of the word "MATH" in different orders)
• The number of permutations is always a non-negative integer
  • Permutations involve counting distinct arrangements, so the result cannot be a fraction or a negative number
  • If the calculated result is not an integer, it indicates an error in the problem setup or formula application

Permutations with repetition

Calculating permutations with repetition

• When repetition is allowed, the number of permutations is calculated differently than when objects are distinct
  • Repetition means that an object can be used multiple times in the arrangement
  • The formula for permutations with repetition takes into account the number of objects of each type
• The number of permutations of n objects with repetition, where there are $n_1$ objects of type 1, $n_2$ objects of type 2, ..., and $n_k$ objects of type k, is given by the formula: $\frac{(n_1 + n_2 + ... + n_k)!}{n_1! \times n_2! \times ... \times n_k!}$
  • The numerator represents the total number of objects, while the denominator accounts for the repetition of objects within each type
  • This formula is derived using the multinomial coefficient, which generalizes the binomial coefficient for more than two types of objects

Unlimited supply of objects

• If there are n objects with k types and each type has an unlimited supply, the number of permutations is $k^n$
  • In this case, each position in the arrangement can be filled by any of the k types of objects independently
  • The number of permutations is calculated by multiplying the number of choices for each position (creating a 4-digit PIN code using digits 0-9, with repetition allowed)
• Permutations with unlimited supply are commonly used in problems involving password creation, product configurations, or experimental designs
  • The unlimited supply allows for a wide range of possible arrangements, as objects can be repeated without restriction
  • Identifying the number of types (k) and the length of the arrangement (n) is crucial for applying the $k^n$ formula correctly

Permutations in real-world applications

Fields of application

• Permutations are used in various fields to solve problems involving ordering and arrangement
  • Mathematics: studying properties of permutations, developing algorithms for generating and counting permutations
  • Computer Science: analyzing algorithms, designing data structures, creating secure passwords or encryption schemes
  • Statistics: designing experiments, sampling and randomization techniques, analyzing rankings and preferences
  • Other fields: logistics (routing and scheduling), genetics (DNA sequencing), linguistics (word order and sentence structure)

Solving permutation problems

• Identifying whether a problem involves permutations with or without repetition is crucial for selecting the appropriate formula
  • Carefully read the problem statement to determine if objects can be repeated or if they are distinct
  • Look for keywords such as "arrange," "order," or "sequence" to recognize permutation problems
• Breaking down the problem into smaller parts and organizing the given information can help in solving permutation problems efficiently
  • Identify the total number of objects (n) and the number of objects being arranged (r)
  • Determine if there are different types of objects and count the number of objects of each type
  • Select the appropriate formula based on whether repetition is allowed and substitute the given values
• Real-world examples of permutation problems include:
  • Arranging books on a shelf (distinct objects, no repetition)
  • Creating passwords or PIN codes (repetition allowed, unlimited supply of characters or digits)
  • Determining the number of possible routes between multiple locations (order matters, no repetition)
  • Analyzing the number of ways to distribute objects among people (distinct objects, no repetition)