Counting and combinations
58 flashcards covering Counting and combinations for the ACT Math section.
Counting and combinations is a branch of math that deals with figuring out how many ways you can select or arrange items. At its core, counting helps you calculate the total possibilities in a scenario, like how many outfits you can make from a set of clothes. Combinations specifically focus on selections where the order doesn't matter—for example, choosing a team from a group of players without caring about who picks first. This topic builds on basic addition and multiplication but introduces tools like formulas to handle more complex situations efficiently.
On the ACT Math section, counting and combinations appear in problems that test your ability to apply these concepts to real-world scenarios, such as probability questions or arranging objects. You'll encounter multiple-choice questions that might involve permutations (where order matters) or combinations (where it doesn't), and common traps include overcounting possibilities or confusing the two. Focus on mastering key formulas, like the combination formula C(n, k) = n! / (k!(n-k)!), and practice identifying whether order is relevant in word problems to avoid errors.
Remember to double-check if the problem involves repetition before applying a formula.
Terms (58)
- 01
Addition Principle
The addition principle states that if there are m ways to perform one event and n ways to perform a mutually exclusive event, then there are m + n ways to perform either event.
- 02
Multiplication Principle
The multiplication principle states that if there are m ways to perform one event and n ways to perform another event that follows it, then there are m × n ways to perform both events in sequence.
- 03
Factorial
Factorial of a non-negative integer n, denoted n!, is the product of all positive integers from 1 to n, with 0! defined as 1.
- 04
Permutation
A permutation is an arrangement of objects in a specific order, where the number of ways to arrange r objects from n distinct objects is given by nPr = n! / (n - r)!.
- 05
Combination
A combination is a selection of objects where order does not matter, and the number of ways to choose r objects from n distinct objects is given by nCr = n! / (r! × (n - r)!).
- 06
nPr Formula
The formula for permutations of r items from n is nPr = n! / (n - r)!, used when the order of selection matters.
- 07
nCr Formula
The formula for combinations of r items from n is nCr = n! / (r! × (n - r)!), used when the order of selection does not matter.
- 08
Distinguishable Permutations
For permutations of a multiset, the number of distinct arrangements of n objects where some are identical is n! divided by the product of the factorials of the counts of each identical item.
- 09
Circular Permutations
In circular permutations, arrangements of n distinct objects in a circle are calculated as (n - 1)!, since rotations of the same arrangement are considered identical.
- 10
Binomial Coefficient
A binomial coefficient, denoted C(n, k) or nCk, represents the number of ways to choose k successes in n trials and is calculated as n! / (k! × (n - k)!).
- 11
Pascal's Triangle
Pascal's triangle is a triangular array where each number is the sum of the two numbers directly above it, used to find binomial coefficients with the entry in row n and position k being nCk.
- 12
Inclusion-Exclusion Principle
The inclusion-exclusion principle calculates the size of the union of multiple sets by adding and subtracting the sizes of their intersections, such as for two sets: |A ∪ B| = |A| + |B| - |A ∩ B|.
- 13
Overcounting
Overcounting occurs when a counting method includes the same outcome multiple times, often requiring adjustments like dividing by symmetries to get the correct total.
- 14
Undercounting
Undercounting happens when a counting method misses some possible outcomes, which can be avoided by ensuring all cases are systematically considered.
- 15
Arranging with Repetitions
The number of ways to arrange n items where repetitions are allowed is given by the appropriate power, such as for a sequence of length r from an alphabet of n letters, it is n^r.
- 16
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), accounting for multisets.
- 17
Probability Using Combinations
Probability of an event can be calculated using combinations by dividing the number of favorable outcomes by the total number of possible outcomes, both determined via combinations.
- 18
Complementary Counting
Complementary counting involves calculating the total number of outcomes and subtracting the number of unfavorable outcomes to find the desired count more efficiently.
- 19
At Least One
To count outcomes with at least one of a certain item, use complementary counting by subtracting the cases with none from the total.
- 20
Exactly One
Exactly one means counting cases where precisely one specific condition is met, often by considering each possibility separately and summing.
- 21
Bridge Hand Distribution
In card problems like bridge, the number of ways to distribute hands is calculated using combinations, such as dividing 52 cards into four hands of 13 each.
- 22
Lottery Selection
For a lottery, the number of possible tickets is a combination, such as C(49, 6) for choosing 6 numbers from 49 without regard to order.
- 23
Team Selection
The number of ways to select a team of r members from n people is a combination, C(n, r), since the order of selection does not matter.
- 24
Committee Formation
Forming a committee with specific roles uses permutations if order matters, or combinations if it does not, adjusted for any restrictions.
- 25
Arranging in a Line
Arranging n distinct objects in a straight line gives n! possibilities, but adjustments are needed if some objects are identical.
- 26
Factorial of Zero
! is defined as 1, which is used in formulas like permutations and combinations to handle edge cases where no items are selected.
- 27
Simplifying Factorials
Factorials can be simplified by canceling common terms in equations, such as in nCr = n! / (r! (n - r)!) by expanding and reducing.
- 28
Binomial Theorem
The binomial theorem expands (a + b)^n as the sum of terms C(n, k) a^(n-k) b^k for k from 0 to n, relating to counting coefficients.
- 29
Common Mistake: Permutations vs. Combinations
A common error is using permutations when combinations are needed or vice versa, so determine if order matters before applying the formula.
- 30
When to Use Permutations
Use permutations when the order of items matters, such as in arranging people in seats, rather than just selecting them.
- 31
Permutations with Identical Items
For permutations of objects with identical items, divide the total factorial by the factorials of the counts of identical items to avoid overcounting.
- 32
Multinomial Coefficients
Multinomial coefficients generalize binomial coefficients for dividing n items into multiple groups, calculated as n! / (n1! n2! ... nk!) for groups of sizes n1 through nk.
- 33
Partitioning Sets
Partitioning a set into subsets uses multinomial coefficients if the subsets have specified sizes, or Stirling numbers for unspecified sizes.
- 34
Venn Diagrams for Counting
Venn diagrams help visualize overlapping sets for counting, aiding in applying the inclusion-exclusion principle.
- 35
Word Problems in Counting
In word problems, identify whether order matters and if repetitions are allowed to choose the correct counting method.
- 36
Example: Choosing 2 from 5
The number of ways to choose 2 items from 5 is C(5, 2) = 10, illustrating a basic combination.
- 37
Example: Arranging 3 Books
Arranging 3 distinct books on a shelf gives 3! = 6 ways, showing a simple permutation.
- 38
Strategy for Grid Paths
To count paths on a grid from point A to B, use combinations to calculate routes, such as C(m + n, m) for an m by n grid.
- 39
Handshake Problem
The handshake problem counts ways people shake hands, such as C(n, 2) for n people each shaking once with each other.
- 40
Telephone Keypad Counting
Counting sequences on a telephone keypad involves the multiplication principle, like 3^7 for a 7-digit code using 3 options per digit.
- 41
License Plate Possibilities
The number of possible license plates is calculated using permutations or the multiplication principle based on the format, such as letters and digits.
- 42
Password Combinations
For passwords, use the multiplication principle for sequences with or without repetition, adjusted for case sensitivity or character sets.
- 43
Dice Roll Outcomes
The number of outcomes for rolling multiple dice is 6^n for n dice, using the multiplication principle.
- 44
Card Drawing Probabilities
Probabilities in card drawing use combinations, like the chance of drawing 2 aces from 52 cards is C(4, 2) / C(52, 2).
- 45
Coin Flip Sequences
The number of possible sequences for n coin flips is 2^n, as each flip has 2 outcomes.
- 46
Subsets of a Set
The number of subsets of a set with n elements is 2^n, including the empty set and the set itself.
- 47
Power Set
A power set is the set of all subsets of a given set, with its size being 2^n for a set of n elements.
- 48
Cartesian Product
The Cartesian product of two sets is the set of all ordered pairs from the sets, with size m × n for sets of sizes m and n.
- 49
Arranging with Restrictions
When arranging with restrictions, subtract invalid arrangements from total, such as excluding cases where certain items are together.
- 50
Selecting with Conditions
For selections with conditions, use combinations and adjust for the conditions, like requiring at least one of a specific type.
- 51
Binomial Expansion Coefficient
In binomial expansion, coefficients are binomial coefficients, indicating the number of ways to choose terms in the expansion.
- 52
Factorial Simplification in Equations
In equations involving factorials, simplify by canceling common factors before calculating, especially for large numbers.
- 53
Counting Paths with Obstacles
For paths with obstacles, subtract the blocked paths from total paths, using complementary counting.
- 54
Example: Arranging Letters with Repeats
Arranging the letters in 'BOOK' gives 4! / (2!) = 12 distinct ways, accounting for the two O's.
- 55
Example: Committee with Positions
Selecting a president and vice-president from 5 people is P(5, 2) = 20, since order matters for the roles.
- 56
Strategy for Overlapping Events
For overlapping events in counting, apply inclusion-exclusion to avoid double-counting shared elements.
- 57
Permutations of Subsets
The number of ways to arrange a subset and then permute it is the product of choosing the subset and arranging it.
- 58
Combinations in Probability
Combinations are used in probability to count equally likely outcomes, ensuring accurate fractions.