Permutations and Combinations: Arranging and Selecting Objects
Understand permutations and combinations, fundamental concepts in discrete mathematics for counting arrangements and selections of objects. This guide explains permutations (order matters), combinations (order doesn't matter), and provides formulas and examples for calculating permutations and combinations.
Permutations and Combinations: Arranging and Selecting Objects
What is a Permutation?
A permutation is an arrangement of objects where the order matters. For example, arranging the letters ABC in different orders (ABC, ACB, BAC, etc.) creates different permutations. An r-permutation is an arrangement of r objects chosen from a set of n objects (where r ≤ n).
Permutation Notation:
The number of r-permutations of n objects is denoted as P(n, r).
Theorem: Permutations of n Objects Taken n at a Time
The number of permutations of n distinct objects taken all at a time is n!. (A proof of this theorem using induction or a combinatorial argument would be appropriate here.)
Permutations with Restrictions
Suppose you have n distinct objects and you want to arrange r of them, but certain objects are excluded or included:
- Objects Excluded: The number of permutations is P(n-p, r), where p is the number of excluded objects.
- Objects Included: The number of permutations is P(n-p, r-p) * P(p, p), where p is the number of included objects.
Example: Permutations with Restrictions
How many 6-digit numbers can be formed using digits 0-9 if the number must start with 30 and no digit is repeated?
Solution: We choose 4 digits from the remaining 7 digits: P(7, 4) = 840.
Permutations with Repeated Objects
Theorem:
The number of permutations of n objects taken r at a time with repetition allowed is nr. (A proof of this theorem would be appropriate here.)
Circular Permutations
A circular permutation is an arrangement of objects around a circle. The order matters, but rotations are considered the same arrangement.
Theorem: Number of Circular Permutations
The number of circular permutations of n distinct objects is (n-1)!. (A proof of this theorem would be appropriate here.)
What is a Combination?
A combination is a selection of objects where order *doesn't* matter. For example, selecting two letters from ABC (AB and BA are the same combination).
Combination Notation:
The number of combinations of n objects taken r at a time is denoted as nCr, C(n, r), or nCr.
Theorem: Relationship Between Permutations and Combinations:
P(n,r) = nCr * r! (A proof of this would be appropriate here.)
Example: Combinations
(An example problem involving combinations, such as selecting items from a set, should be included here.)
Conclusion
Permutations and combinations are fundamental counting principles used extensively in various fields, including probability, statistics, and computer science. Understanding their differences and how to calculate them is crucial for solving many problems involving arranging and selecting objects.