Permutations: Arrangements and Order

• Permutation and combination are concepts in combinatorics, concerning the study of finite or countable discrete structures
• They count the number of ways to arrange or select objects from a set

Permutation

• An arrangement of objects in a specific order is a permutation
• The order of objects is important
• ABC, ACB, BAC, BCA, CAB, CBA are permutations of the letters ABC

Permutation Formula

• P(n, r) or nPr denotes the number of permutations of n distinct objects taken r at a time
• The formula is P(n, r) = n! / (n - r)! where n! (n factorial) is the product of all positive integers up to n
• n! = n × (n-1) × (n-2) × ... × 2 × 1
• P(5, 3) = 5! / (5-3)! = 5! / 2! = (5 × 4 × 3 × 2 × 1) / (2 × 1) = 60 is the number of permutations of 5 objects taken 3 at a time

Special Cases of Permutations

• When r = n, the number of permutations of n objects taken n at a time is P(n, n) = n!
• Arranging all n objects in all possible orders means this
• P(3, 3) = 3! = 3 × 2 × 1 = 6 (ABC, ACB, BAC, BCA, CAB, CBA) shows arranging 3 objects A, B, C in all possible orders

Permutations with Repetition

• When some objects are identical, the number of distinct permutations is reduced
• If there are n objects with n1 of one kind, n2 of another kind, ..., nk of the kth kind, the number of permutations is given by: n! / (n1! * n2*! ... * nk*!)
• 10! / (3! * 3! * 2! * 1! * 1!) = 50,400 is the number of permutations of the letters in the word "STATISTICS"

Combination

• A selection of objects without regard to order is a combination
• The order of objects is not important
• AB, AC, BC are combinations of the letters ABC if selecting 2 letters (BA is the same as AB, CA is the same as AC, and CB is the same as BC)

Combination Formula

• C(n, r) or nCr, or (n choose r) denotes the number of combinations of n distinct objects taken r at a time
• The formula is C(n, r) = n! / (r! * (n - r)!)
• C(5, 3) = 5! / (3! * (5-3)!) = 5! / (3! * 2!) = (5 × 4 × 3 × 2 × 1) / ((3 × 2 × 1) × (2 × 1)) = 10 is the number of combinations of 5 objects taken 3 at a time

Properties of Combinations

• C(n, 0) = 1 means there is one way to choose nothing
• C(n, n) = 1 means there is one way to choose everything
• C(n, r) = C(n, n - r) means choosing r objects is the same as excluding n - r objects
• C(5, 2) = C(5, 3) = 10

Relationship between Permutation and Combination

• Permutation considers order, while combination ignores order
• P(n, r) = C(n, r) * r! means permutation is combination multiplied by the number of ways to arrange the selected objects
• Combination is selecting a subset, while permutation is arranging that subset

Applications

• Permutation and combination are used in probability, statistics, computer science, and various other fields
• Calculating the probability of winning a lottery, arranging passwords, scheduling tasks, and grouping data are examples

Probability

• Permutation and combination calculate probabilities when outcomes are equally likely
• Probability = (Number of favorable outcomes) / (Total number of possible outcomes)
• Calculating the probability of drawing a specific hand in poker can be done using combination

Computer Science

• Algorithm design and analysis uses permutation and combination
• Finding all possible arrangements or groupings of data elements is an example

Examples

• The word "APPLE" has 5 letters, with P repeated twice when arranging it to find how many ways
• 5! / 2! = 60 arrangements can be made of the word "APPLE"
• C(10, 3) = 10! / (3! * 7!) = 120 is the number of ways to select a committee of 3 from 10 people
• P(10, 4) = 10! / 6! = 5040 possible codes can be made for a 4-digit lock with no repeated digits

Key Differences

• Arrangement order is important in Permutation, order matters
• Only selection of objects matters in Combination, order is irrelevant

Summary Table