Permutations and combinations
51 flashcards covering Permutations and combinations for the GMAT Quantitative section.
Permutations and combinations are essential tools for counting possibilities in math and probability. A permutation is an arrangement of items where the order matters, such as lining up people for a photo. A combination, by contrast, is a selection of items where order doesn't matter, like picking a committee from a group. These concepts help solve problems involving choices and arrangements, making them foundational for more complex topics like probability.
On the GMAT Quantitative section, permutations and combinations show up in problem-solving questions that require precise counting, often in word problems or data interpretation. You'll face scenarios involving arrangements, selections, or probability calculations, with common traps like confusing the two concepts or overlooking restrictions that affect counts. Focus on understanding the key formulas—such as nPr and nCr—and practicing how to identify when order is relevant to avoid errors.
A good tip: Always ask if the problem cares about sequence before choosing your approach.
Terms (51)
- 01
Permutation
A permutation is an arrangement of objects in a specific order, where the sequence matters.
- 02
Combination
A combination is a selection of objects where the order does not matter.
- 03
Factorial
The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers from 1 to n; for example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
- 04
nPr formula
The formula for permutations of n items taken r at a time is nPr = n! / (n - r)!, used when order matters and items are distinct.
- 05
nCr formula
The formula for combinations of n items taken r at a time is nCr = n! / (r! × (n - r)!), used when order does not matter and items are distinct.
- 06
Difference between permutation and combination
Permutations consider the order of selection, while combinations do not, so permutations yield more arrangements than combinations for the same items.
- 07
Permutations of distinct objects
For n distinct objects, the total number of permutations is n!, representing all possible ways to arrange them in a sequence.
- 08
Permutations with identical objects
When some objects are identical, the number of distinct permutations of n objects is n! divided by the product of the factorials of the counts of each identical type.
- 09
Adjusting permutations for identical items
To account for identical items in permutations, divide the total factorial by the factorials of the frequencies of the identical items to avoid overcounting.
- 10
Circular permutations
In circular permutations, arrangements are considered the same if they can be rotated into each other, so for n distinct objects, the number is (n - 1)!.
- 11
Arrangements around a table
For seating n distinct people around a circular table, the number of distinct arrangements is (n - 1)!, as rotations are identical.
- 12
Linear arrangements
Linear arrangements are permutations where the order matters and the positions are in a straight line, calculated as n! for n distinct items.
- 13
Selecting r items from n without order
The number of ways to select r items from n distinct items without regard to order is given by nCr, which is used for combinations.
- 14
Binomial coefficient
The binomial coefficient, denoted as C(n, k) or nCk, represents the number of ways to choose k successes out of n trials in a binomial experiment.
- 15
Calculating n choose k
To calculate n choose k, use the formula nCr = n! / (k! × (n - k)!), which gives the number of subsets of size k from a set of n elements.
- 16
Common mistake: Treating combinations as permutations
A common error is calculating permutations when combinations are needed, leading to overcounting by considering different orders as distinct.
- 17
When to use permutations vs. combinations
Use permutations when the problem involves arranging items in a specific order, and use combinations when only the selection matters, not the sequence.
- 18
Permutations with restrictions
Permutations with restrictions involve arranging items under specific conditions, such as fixing certain positions, which requires adjusting the total permutations accordingly.
- 19
Arranging letters with vowels together
For arranging letters where vowels must be together, treat the vowels as a single unit, then permute the units and the vowels within their unit.
- 20
Combinations with repetition
Combinations with repetition allowed, also called multichoose, calculate the number of ways to select r items from n types with repetition, using the formula C(n + r - 1, r).
- 21
Multichoose formula
The multichoose formula, C(n + r - 1, r), gives the number of ways to choose r items from n categories with repetition allowed, often used in distribution problems.
- 22
Stars and bars method
The stars and bars method is a technique to solve combinations with repetition, representing items as stars and dividers as bars to distribute identical items into distinct groups.
- 23
Distributing identical items to distinct groups
The number of ways to distribute r identical items into n distinct groups is given by C(r + n - 1, r), using the stars and bars theorem.
- 24
Probability using combinations
In probability problems, combinations calculate the total possible outcomes and favorable outcomes when order doesn't matter, such as drawing cards from a deck.
- 25
Hypergeometric distribution
The hypergeometric distribution calculates the probability of k successes in r draws without replacement from a finite population, using combinations for both draws and population subsets.
- 26
Overlap in selections
In combination problems with overlap, such as selecting items with certain shared characteristics, use inclusion-exclusion to avoid double-counting the overlapping sets.
- 27
Inclusion of certain elements
When problems require including specific elements in selections, calculate the total combinations and subtract those that exclude the required elements to get the correct count.
- 28
Exclusion of certain elements
For combinations where certain elements must be excluded, subtract the combinations that include those elements from the total possible combinations.
- 29
Derangements
Derangements are permutations where no element appears in its original position, calculated using the formula !n = n! × Σ (-1)^k / k! for k from 0 to n.
- 30
Factorial for small numbers
For small values of n, factorials are straightforward: 0! = 1, 1! = 1, 2! = 2, 3! = 6, and 4! = 24, which are often used in basic permutation calculations.
- 31
Simplifying expressions with factorials
To simplify factorial expressions, cancel common terms in numerators and denominators, such as in nPr = n! / (n - r)!, to make calculations easier.
- 32
Canceling terms in permutations
In permutation formulas, cancel out factorials by recognizing that n! / (n - r)! simplifies to n × (n - 1) × ... × (n - r + 1), reducing computation.
- 33
Word problems: Number of ways to choose a committee
In committee selection problems, use combinations if order doesn't matter, such as C(n, k) for choosing k members from n people.
- 34
Number of ways to arrange books on a shelf
Arranging n distinct books on a shelf is a permutation problem, giving n! ways, but adjust for identical books by dividing by the factorials of their counts.
- 35
Seating arrangements with conditions
For seating with conditions, like certain people not sitting together, calculate total permutations and subtract the invalid ones using inclusion-exclusion.
- 36
Handshakes problem
The handshakes problem, such as in a room of n people, uses combinations to find the number of unique pairs, calculated as C(n, 2).
- 37
Poker hand probabilities
Poker hand probabilities involve combinations, such as C(52, 5) for total hands and specific subsets for hands like pairs or flushes.
- 38
Lottery winning numbers
Lottery problems use combinations to determine the odds, such as C(49, 6) for a lottery drawing 6 numbers from 49.
- 39
Code formation with digits
Forming codes with digits uses permutations if order matters, adjusted for repetitions, such as arranging digits with some identical.
- 40
Password creation
Password problems often involve permutations with or without repetition, depending on whether digits or letters can repeat.
- 41
Strategy for counting problems
A key strategy is to identify whether order matters and if repetitions are allowed, then choose the appropriate permutation or combination formula.
- 42
Avoiding double-counting
In counting problems, avoid double-counting by ensuring that identical arrangements are not counted separately, especially when dealing with identical objects.
- 43
When order matters
Order matters in problems involving arrangements, sequences, or rankings, making permutations the correct approach.
- 44
When order doesn't matter
Order doesn't matter in problems involving selections, groups, or sets, where combinations are used.
- 45
Permutations of a multiset
For a multiset with n items where some are identical, the number of distinct permutations is n! divided by the product of the factorials of the counts of each identical item.
- 46
Combinations of multisets
Combinations of multisets involve selecting subsets while accounting for identical items, often requiring adjusted formulas like multichoose.
- 47
Permutations with ties
In permutations with ties, such as ranking with shared positions, calculate by considering the tied items as identical and adjusting the total arrangements.
- 48
Arranging people in a line with height order
Arranging people by height in a line is a permutation with restrictions, often requiring factorial calculations after sorting.
- 49
Selecting fruits with at least one of each type
To select fruits with at least one of each type, use inclusion-exclusion on combinations, subtracting cases where one or more types are missing.
- 50
Trap: Forgetting to divide by repetitions
A common trap is calculating permutations without dividing by the factorials of identical items, resulting in an overcount of distinct arrangements.
- 51
Trap: Misapplying circular permutation
Misapplying circular permutation occurs when treating linear arrangements as circular or vice versa, leading to incorrect counts for problems like seating.