Glossary
Practice Quizzes

7.3 Combinations

4 min read•june 18, 2024

are a key concept in counting problems. They help us figure out how many ways we can select items from a group when the order doesn't matter. This is super useful in real-life situations, like picking team members or choosing pizza toppings.

Understanding combinations is crucial for tackling more complex and statistics problems. By mastering this concept, you'll be better equipped to analyze data, make predictions, and solve practical math problems in various fields, from business to science.

Combinations

Combinations without order

Top images from around the web for Combinations without order

  • Calculando factoriales de números grandes - KS7000+WP View original

    Is this image relevant?

  • OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Solving Equations by Factoring View original

    Is this image relevant?

  • Calculando factoriales de números grandes - KS7000+WP View original

    Is this image relevant?

1 of 3

Top images from around the web for Combinations without order

  • Calculando factoriales de números grandes - KS7000+WP View original

    Is this image relevant?

  • OpenAlgebra.com: Free Algebra Study Guide & Video Tutorials: Solving Equations by Factoring View original

    Is this image relevant?

  • Calculando factoriales de números grandes - KS7000+WP View original

    Is this image relevant?

1 of 3
  • Combinations select items from a collection where order does not matter
    • Selecting a team of 3 students from a class of 20 (Alice, Bob, Charlie is the same as Charlie, Alice, Bob)
    • Choosing 2 toppings from 5 options for a pizza (pepperoni and mushroom is the same as mushroom and pepperoni)
  • Denoted as C(n,r)C(n,r) or (nr)\binom{n}{r} where:
    • nn is the total number of items in the set
    • rr is the number of items being selected
  • Formula for combinations: C(n,r)=[n!](https://www.fiveableKeyTerm:n!)r!(n−r)!C(n,r) = \frac{[n!](https://www.fiveableKeyTerm:n!)}{r!(n-r)!}
    • n!n! is the of nn, the product of all positive integers less than or equal to nn (5!=5⋅4⋅3⋅2⋅1=1205! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120)
    • r!r! is the factorial of rr
    • (n−r)!(n-r)! is the factorial of n−rn-r
  • To calculate combinations:
    1. Identify the total items nn and the number to select rr
    2. Plug nn and rr into the formula n!r!(n−r)!\frac{n!}{r!(n-r)!}
    3. Simplify the factorials and calculate the result
  • Example: Selecting 2 fruits from a basket of 5 fruits
    • n=5n = 5 (total fruits) and r=2r = 2 (fruits selected)
    • C(5,2)=5!2!(5−2)!=5!2!3!=5⋅4⋅3!2⋅1⋅3!=10C(5,2) = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{5 \cdot 4 \cdot 3!}{2 \cdot 1 \cdot 3!} = 10
    • There are 10 ways to select 2 fruits from 5 fruits where order doesn't matter
  • Combinations are fundamental to , as they help determine the number of subsets of a given size from a larger set

Permutations vs combinations

  • consider the order of selection, combinations do not
    • : Arranging the letters A, B, C (ABC, ACB, BAC, BCA, CAB, CBA are all different)
    • : Selecting 2 toppings from cheese, pepperoni, mushroom (cheese and pepperoni is the same as pepperoni and cheese)
  • Use permutations when:
    • Order matters
    • Each item is distinct and used only once
    • Arranging books on a shelf (Moby Dick then Huckleberry Finn is different than Huckleberry Finn then Moby Dick)
  • Use combinations when:
    • Order does not matter
    • Items are not distinct or can be used multiple times
    • Selecting 3 toppings for a pizza from 8 options (mushroom, pepperoni, olive is the same as olive, mushroom, pepperoni)
  • To decide between permutations and combinations:
    1. Determine if order matters
    2. Check if items are distinct or can be repeated
  • Example: Making a 4-digit PIN code using digits 0-9
    • Order matters (1234 is a different PIN than 4321)
    • Digits can be repeated (1111 is a valid PIN)
    • This requires permutations with repetition, not combinations

Applications of combination formula

  1. Identify the total items nn and number to select rr
  2. Substitute nn and rr into the formula n!r!(n−r)!\frac{n!}{r!(n-r)!}
  3. Simplify factorials by canceling common terms in numerator and denominator
  4. Calculate the final result to get the number of combinations
  • Example: A sundae bar has 10 toppings. How many 4-topping sundaes are possible?
    • n=10n = 10 toppings total, r=4r = 4 toppings per sundae
    • C(10,4)=10!4!(10−4)!=10!4!6!C(10,4) = \frac{10!}{4!(10-4)!} = \frac{10!}{4!6!}
    • 10⋅9⋅8⋅7⋅6!4⋅3⋅2⋅1⋅6!=210\frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6!}{4 \cdot 3 \cdot 2 \cdot 1 \cdot 6!} = 210
    • There are 210 different ways to make a 4-topping sundae from 10 toppings
  • Example: A jury of 12 must be selected from 50 candidates. How many possible juries are there?
    • n=50n = 50 candidates, r=12r = 12 jurors
    • C(50,12)=50!12!(50−12)!=50!12!38!≈1.24×1010C(50,12) = \frac{50!}{12!(50-12)!} = \frac{50!}{12!38!} \approx 1.24 \times 10^{10}
    • There are approximately 1.24×10101.24 \times 10^{10} possible 12-person juries from 50 candidates
  • Combinations are essential in probability calculations, especially when determining the number of ways to select a sample from a larger population

Combinatorics and Counting Principles

  • is the branch of mathematics dealing with counting, arrangement, and combination of objects
  • The fundamental states that if one can occur in m ways, and another independent event can occur in n ways, then the two events can occur together in m × n ways
  • techniques in statistics often rely on combinations to determine the number of possible samples from a population
  • Combinations play a crucial role in various fields, including probability theory and statistical analysis

Key Terms to Review (29)

Addition Principle: The Addition Principle is a fundamental concept in set theory and combinatorics that states if two events cannot occur at the same time, the total number of ways that either event can occur is the sum of the individual counts of each event. This principle allows for the calculation of possibilities in scenarios involving multiple disjoint sets or choices, making it a crucial tool in both set operations and combinatorial analysis.
Binomial Theorem: The binomial theorem provides a way to expand expressions of the form $$(a + b)^n$$, where $$n$$ is a non-negative integer. This theorem allows us to express the expansion as a sum involving terms that are products of powers of $$a$$ and $$b$$, multiplied by specific coefficients known as binomial coefficients. These coefficients can be calculated using combinations, linking the theorem directly to the concept of counting and arrangements.
Blaise Pascal: Blaise Pascal was a French mathematician, physicist, and philosopher, renowned for his contributions to probability theory and combinatorics. His work laid the groundwork for modern statistical analysis and the mathematical understanding of chance, which is crucial for evaluating likelihoods and outcomes in various scenarios. Pascal's Triangle, a simple yet powerful mathematical structure he developed, plays a significant role in combinations and binomial coefficients, influencing how we calculate odds and expected values in probability.
Combination: A combination is a selection of items from a larger set where the order of selection does not matter. Understanding combinations helps in various scenarios such as calculating probabilities, forming groups, and organizing outcomes where the sequence is irrelevant, linking directly to concepts like counting rules, permutations, and probability calculations.
Combination formula: The combination formula is a mathematical equation used to determine the number of ways to choose a subset of items from a larger set, where the order of selection does not matter. This concept is crucial in combinatorics, allowing for calculations in various contexts like probability and statistics. It is expressed as $$C(n, r) = \frac{n!}{r!(n - r)!}$$, where 'n' is the total number of items, 'r' is the number of items to choose, and '!' denotes factorial.
Combinations: Combinations refer to the selection of items from a larger set where order does not matter. They are used to determine how many ways a subset of items can be chosen from the entire set without regard to the sequence of selection.
Combinatorics: Combinatorics is the branch of mathematics dealing with the study of finite or countable discrete structures. It involves counting, arranging, and finding patterns in sets of elements.
Combinatorics: Combinatorics is a branch of mathematics that focuses on counting, arrangement, and combination of objects. It plays a crucial role in various areas, such as probability and graph theory, by providing methods to analyze the possible configurations or selections from a given set. Understanding combinatorial principles is key for solving problems related to arrangements, selections, and pathways within complex structures.
Compound event: A compound event is an event that consists of two or more simple events. It can involve the union, intersection, or complement of these simple events.
Counting principle: The counting principle is a fundamental concept in combinatorics that allows us to determine the total number of possible outcomes in a given scenario by multiplying the number of choices available at each step. This principle is essential for solving problems involving sequences, arrangements, and selections, making it a crucial tool for calculating combinations and permutations in various contexts.
Empirical probability: Empirical probability is the probability of an event determined by conducting experiments or observing real-life occurrences. It is calculated as the ratio of the number of favorable outcomes to the total number of trials.
Event: An event is a specific outcome or a set of outcomes from a probability experiment, often relating to the occurrence of certain results when conducting trials. Understanding events is crucial in analyzing combinations of outcomes, visualizing possibilities through diagrams and tables, and calculating probabilities in various scenarios.
Factorial: A factorial, denoted by the symbol 'n!', is a mathematical operation that multiplies a whole number by all of the positive whole numbers less than it. Factorials are essential in counting arrangements and selections, making them pivotal in understanding permutations and combinations. The concept extends to the multiplication rule for counting as it helps in calculating the total number of ways to arrange or select items.
Jacob Bernoulli: Jacob Bernoulli was a Swiss mathematician known for his foundational contributions to probability theory and the study of combinations. He is most famous for Bernoulli's theorem, which laid the groundwork for the field of statistics and combinatorial mathematics, including the principles that govern how combinations are calculated. His work in this area continues to influence modern mathematics and the way we understand probabilities and outcomes.
Multiplication principle: The multiplication principle is a fundamental rule used to determine the number of possible outcomes in a sequence of events. It states that if one event can occur in 'm' ways and a second event can occur independently in 'n' ways, then the two events together can occur in m * n ways.
Multiplication Principle: The multiplication principle states that if there are multiple independent choices to be made, the total number of possible outcomes is found by multiplying the number of options for each choice. This principle is fundamental in counting scenarios where the arrangement or selection of items occurs in sequences, particularly in contexts involving arrangements and selections of groups.
N!: The notation 'n!' represents the factorial of a non-negative integer n, defined as the product of all positive integers less than or equal to n. This concept is crucial in combinatorial mathematics, as it is used to calculate the number of ways to arrange or select items from a set, forming the foundation for understanding arrangements and selections in various contexts.
NCr: nCr, or 'n choose r', is a mathematical notation that represents the number of combinations of n items taken r at a time without regard to the order of selection. This concept is essential for determining how many ways a certain number of items can be chosen from a larger set, which is crucial in various fields like probability, statistics, and combinatorics.
Outcome: An outcome is a possible result of a random experiment or event, which can be described in terms of the various scenarios that could occur. It connects to counting techniques, probability rules, and methods for organizing and visualizing data, all of which are essential for understanding how outcomes influence decision-making and predictions in uncertain situations.
Pascal's triangle: Pascal's triangle is a triangular array of numbers where each number is the sum of the two directly above it. This structure reveals deep connections between algebra and geometry, making it a powerful tool in combinatorics and graph theory.
Permutation: A permutation is an arrangement of objects in a specific order. The concept of permutations is essential for understanding how to count and organize different sequences, especially when considering distinct groups of items. Permutations are closely related to the multiplication rule, as the number of ways to arrange objects can often be calculated by multiplying the number of choices available at each step.
Permutations: Permutations are arrangements of objects in a specific order. The order of the objects is crucial and changing the order creates a different permutation.
Probability: Probability is a measure of the likelihood that an event will occur, expressed as a number between 0 and 1, where 0 indicates impossibility and 1 indicates certainty. It connects various mathematical concepts by providing a framework to assess and quantify uncertainty in different scenarios, helping to determine outcomes based on different arrangements, selections, and occurrences.
Sample space: Sample space is the set of all possible outcomes in a probability experiment. It provides a comprehensive list of everything that could happen during the experiment.
Sample Space: A sample space is the set of all possible outcomes of a random experiment. Understanding the sample space is crucial because it forms the foundation for calculating probabilities, counting outcomes, and analyzing events in various contexts.
Sampling: Sampling is the process of selecting a subset of individuals or items from a larger population to estimate characteristics of the whole group. This technique is essential in statistics, as it allows researchers to gather data without needing to study every member of the population, which can be impractical or impossible. Proper sampling methods ensure that the sample represents the population accurately, helping to draw valid conclusions and make informed decisions.
Set theory: Set theory is a branch of mathematical logic that studies sets, which are collections of objects. It provides a foundational framework for various mathematical concepts and operations, including relationships between different groups, classifications, and how elements interact within those groups. This framework is crucial for understanding concepts like subsets, Venn diagrams, and various set operations, which are fundamental in both theoretical and applied mathematics.
With replacement: With replacement refers to a method of sampling where an item is selected from a set and then returned to the set before the next selection. This means that each selection is independent of the others, as the total number of items remains constant. In this approach, it's possible for the same item to be chosen multiple times in a series of selections, which impacts the calculation of combinations and probabilities.
Without replacement: The term 'without replacement' refers to a sampling method where once an item is selected from a set, it is not returned to the set for potential re-selection. This approach significantly affects the total number of possible outcomes because each selection decreases the available options, leading to unique combinations of items being formed. Understanding this concept is crucial when calculating probabilities and combinations since it influences how we count and arrange elements in a finite sample space.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Glossary
Glossary
7.4 Tree Diagrams, Tables, and Outcomes