Combinatorics
52 flashcards covering Combinatorics for the GMAT Quantitative section.
Combinatorics is a branch of mathematics that focuses on counting, arranging, and selecting items from a set. It deals with questions like how many ways you can choose a team from a group of people or arrange books on a shelf. At its core, it provides tools to calculate possibilities efficiently, avoiding the need to list everything out manually, which is especially useful in real-world scenarios involving choices and probabilities.
On the GMAT Quantitative section, combinatorics shows up in problems involving permutations (where order matters) and combinations (where it doesn't). You'll face multiple-choice questions that test your ability to count outcomes in scenarios like arranging objects or selecting subsets, often combined with probability. Common traps include overcounting due to repeated items or mixing up permutation and combination formulas, so focus on understanding when to use each and double-checking your calculations. A key tip: Always determine if the order of items matters before applying a formula.
Terms (52)
- 01
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, and 0! is defined as 1.
- 02
Permutation
A permutation is an arrangement of objects in a specific order, calculated as nPr = n! / (n - r)! for selecting and arranging r objects from n distinct objects.
- 03
Combination
A combination is a selection of objects where order does not matter, calculated as nCr = n! / (r! × (n - r)!) for choosing r objects from n distinct objects.
- 04
Fundamental Counting Principle
This principle states that if there are m ways to do one thing and n ways to do another, then there are m × n ways to do both, extending to multiple events.
- 05
Addition Principle
If there are m ways to do one thing and n ways to do a mutually exclusive thing, then there are m + n ways to do either one or the other.
- 06
Multiplication Principle
For sequential events, the total number of outcomes is the product of the number of options at each step, assuming choices are independent.
- 07
Permutations of n Objects Taken r at a Time
The number of ways to arrange r objects out of n distinct objects is given by nPr = n! / (n - r)!, accounting for order.
- 08
Number of Subsets
For a set with n elements, the total number of subsets is 2^n, including the empty set and the set itself.
- 09
Arrangements with Repetition
When arranging n items where some are identical, the number of distinct arrangements is n! divided by the product of the factorials of the counts of each identical item.
- 10
Circular Permutations
For arranging n distinct objects in a circle, the number of ways is (n - 1)!, since rotations of the same arrangement are considered identical.
- 11
Combinations with Repetition
The number of ways to choose r items from n types with repetition allowed is given by the formula C(n + r - 1, r), also known as the stars and bars method.
- 12
Binomial Coefficient
A binomial coefficient, denoted as C(n, k) or nCk, represents the number of ways to choose k items from n without regard to order, calculated as n! / (k! × (n - k)!).
- 13
Probability of an Event
The probability of an event is the number of favorable outcomes divided by the total number of possible outcomes, assuming all outcomes are equally likely.
- 14
Independent Events
Two events are independent if the occurrence of one does not affect the probability of the other, and their combined probability is the product of their individual probabilities.
- 15
Mutually Exclusive Events
Mutually exclusive events cannot occur at the same time, so the probability of either occurring is the sum of their individual probabilities.
- 16
Overcounting Error
Overcounting happens when the same outcome is counted multiple times in a counting problem, often due to failing to account for indistinguishable arrangements, leading to inflated results.
- 17
Inclusion-Exclusion Principle for Two Sets
For two sets, the size of their union is the sum of the sizes of the sets minus the size of their intersection, to avoid double-counting overlapping elements.
- 18
Inclusion-Exclusion Principle for Three Sets
For three sets, the size of their union is the sum of individual sizes plus the pairwise intersections minus the triple intersection, ensuring accurate counting.
- 19
Arranging Letters in a Word
The number of distinct ways to arrange the letters in a word is the factorial of the total letters divided by the product of the factorials of the frequencies of each repeated letter.
- 20
Selecting Books from a Shelf
When selecting r books from n distinct books without regard to order, the number of ways is C(n, r), as the arrangement of the selected books does not matter.
- 21
Distributing Distinct Objects
The number of ways to distribute n distinct objects into k distinct groups is k^n, assuming objects can go into any group and groups can be empty.
- 22
Distributing Identical Objects
The number of ways to distribute n identical objects into k distinct groups is C(n + k - 1, k - 1), using the stars and bars theorem.
- 23
Handshakes Problem
In a group of n people, the number of unique handshakes if everyone shakes hands with everyone else is C(n, 2), as order does not matter.
- 24
Paths on a Grid
The number of shortest paths from one corner of a grid to another, moving only right and down, is given by C(m + n, m) for an m by n grid.
- 25
Dice Roll Outcomes
For rolling two dice, the total number of possible outcomes is 6 × 6 = 36, and specific sums can be found by counting favorable pairs.
- 26
Coin Flip Sequences
The number of possible sequences for n coin flips is 2^n, since each flip has 2 outcomes, and sequences account for order.
- 27
Lottery Drawing
In a lottery where order doesn't matter, the number of ways to choose k numbers from n is C(n, k), such as C(49, 6) for a common lotto.
- 28
Committee Formation
The number of ways to form a committee of r people from n is C(n, r), as the selection is without regard to positions unless specified.
- 29
Team Selection with Positions
If positions matter, such as captain and vice-captain, the number of ways to select and assign r people from n is P(n, r), accounting for order.
- 30
Password Formation
The number of possible passwords of length r from n characters with repetition allowed is n^r, but without repetition, it is P(n, r).
- 31
Code Combinations
For a code with r digits from n possibilities without repetition, the number is P(n, r), but with repetition, it is n^r.
- 32
Factorial of Zero
! is defined as 1, which is a convention used in combinatorics to simplify formulas like permutations and combinations.
- 33
Permutation Formula
The formula for permutations is nPr = n! / (n - r)!, used when the order of selection matters.
- 34
Combination Formula
The formula for combinations is nCr = n! / (r! × (n - r)!), used when only the selection matters, not the order.
- 35
Difference Between Permutation and Combination
Permutations consider order, so they yield more arrangements than combinations, which do not; for example, AB and BA are different permutations but the same combination.
- 36
When to Use Permutations vs Combinations
Use permutations when order matters, like assigning positions; use combinations when it does not, like selecting a group without roles.
- 37
Counting Principle for Multiple Choices
For problems with multiple stages, multiply the number of choices at each stage, such as 3 shirts and 2 pants yielding 3 × 2 = 6 outfits.
- 38
Arrangements with Constraints
For arrangements with conditions, like keeping certain items together, treat the constrained group as a single unit and adjust the factorial accordingly.
- 39
Derangements
A derangement is a permutation where no element appears in its original position, calculated using the formula !n = n! × Σ (-1^k / k!) from k=0 to n.
- 40
Pigeonhole Principle
If n items are put into m containers with n > m, at least one container must contain more than one item, useful for proving certain counting scenarios.
- 41
Basic Probability Formula
Probability is favorable outcomes divided by total outcomes, often derived from combinatorial counts like C(5, 2) / C(10, 2) for drawing two aces from a deck.
- 42
Complementary Counting
To find the probability of an event, calculate 1 minus the probability of its complement, which simplifies counting in complex scenarios.
- 43
At Least Problems
For 'at least k' events, use complementary counting by calculating total outcomes minus outcomes with fewer than k, then divide by total.
- 44
Exactly k Successes in n Trials
The number of ways to get exactly k successes in n independent trials is given by C(n, k) times the probability of success raised to k and failure to (n - k).
- 45
Hypergeometric Distribution
In sampling without replacement, the probability of k successes in n draws from a finite population is given by [C(K, k) × C(N - K, n - k)] / C(N, n).
- 46
Binomial Probability
For n independent trials with two outcomes, the probability of exactly k successes is C(n, k) × p^k × (1 - p)^(n - k), where p is the success probability.
- 47
Expected Value in Counting
The expected value is the sum of each outcome multiplied by its probability, often calculated in games or scenarios involving combinatorial probabilities.
- 48
Sample Space
The sample space is the set of all possible outcomes in a probability experiment, such as 2^3 = 8 for three coin flips.
- 49
Event
An event is a subset of the sample space, representing a specific outcome or set of outcomes, like getting at least two heads in three flips.
- 50
Favorable Outcomes
Favorable outcomes are the elements in the sample space that satisfy the condition of the event, used as the numerator in probability calculations.
- 51
Pascal's Identity
Pascal's identity states that C(n, k) = C(n - 1, k - 1) + C(n - 1, k), which is the basis for constructing Pascal's triangle.
- 52
Sum of Binomial Coefficients
The sum of C(n, k) for k from 0 to n equals 2^n, representing the total number of subsets of a set with n elements.