Glossary
Practice Quizzes

13.5 Counting Principles

3 min read•june 24, 2024

Counting principles are essential tools for solving complex problems in mathematics and everyday life. They provide methods to calculate the number of possible outcomes in various scenarios, from simple choices to intricate arrangements.

These principles include addition and multiplication rules, , and . Understanding these concepts allows us to tackle problems involving distinct objects, repeated elements, and subset selection, providing a foundation for and applications.

Counting Principles

Addition principle in counting

Top images from around the web for Addition principle in counting

  • Counting Principles | College Algebra View original

    Is this image relevant?

  • 3.3 Compound Events – Significant Statistics View original

    Is this image relevant?

  • Counting Principles | College Algebra View original

    Is this image relevant?

1 of 3

Top images from around the web for Addition principle in counting

  • Counting Principles | College Algebra View original

    Is this image relevant?

  • 3.3 Compound Events – Significant Statistics View original

    Is this image relevant?

  • Counting Principles | College Algebra View original

    Is this image relevant?

1 of 3
  • States if there are n1n_1 ways to do something and n2n_2 ways to do another thing, and these two things cannot be done at the same time, then there are n1+n2n_1 + n_2 ways to choose one of the things to do
  • Extends to more than two events: if there are n1n_1, n2n_2, ..., nkn_k mutually exclusive ways for kk events to occur, then there are n1+n2+...+nkn_1 + n_2 + ... + n_k ways for any of the events to occur
  • Useful when solving problems where you need to choose between different options or count the total number of possible outcomes from separate events (choosing an appetizer or main course from a menu)

Multiplication principle applications

  • States if one event can occur in mm ways, and another independent event can occur in nn ways, then the two events can occur together in m×nm \times n ways
  • Extends to more than two events: if there are n1n_1 ways for event 1, n2n_2 ways for event 2, ..., and nkn_k ways for event kk, then there are n1×n2×...×nkn_1 \times n_2 \times ... \times n_k ways for all kk events to occur together
  • Applies when solving problems involving the total number of possible combinations or arrangements of multiple independent choices (types of bread and fillings for sandwiches, clothing combinations)
  • Also known as the

Permutations of distinct objects

  • Ordered arrangement where the order matters and all objects are distinct
  • Number of permutations of nn distinct objects denoted as P(n)P(n) or n!n!
    • Formula: n!=n×(n−1)×(n−2)×...×3×2×1n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1
  • Number of permutations of nn distinct objects taken rr at a time denoted as P(n,r)P(n,r) or nPr_{n}P_{r}
    • Formula: P(n,r)=n!(n−r)!=n×(n−1)×...×(n−r+1)P(n,r) = \frac{n!}{(n-r)!} = n \times (n-1) \times ... \times (n-r+1)
  • Used when solving problems involving arranging distinct objects in a specific order (ranking preferences, arranging books on a shelf)

Combinations in counting problems

  • Selection of objects where the order does not matter
  • Number of combinations of nn distinct objects taken rr at a time denoted as C(n,r)C(n,r), nCr_{n}C_{r}, or (nr)\binom{n}{r}
    • Formula: C(n,r)=n!r!(n−r)!=P(n,r)r!C(n,r) = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}
  • Applicable when solving problems involving selecting a group of objects without considering the order (forming teams, choosing committee members)

Number of subsets calculation

  • Selection of elements from a set
  • Number of of a set with nn elements is 2n2^n, including the empty set and the set itself
  • Number of subsets with rr elements from a set with nn elements is equal to C(n,r)C(n,r)
  • Useful when determining the total number of possible subsets or the number of subsets with a specific size (number of possible pizza toppings combinations)

Permutations with repeated elements

  • When a set contains repeated elements, the number of distinct permutations is reduced
  • If there are nn elements in total, with n1n_1 of one kind, n2n_2 of another kind, ..., and nkn_k of the kk-th kind, then the number of distinct permutations is:
    • Formula: n!n1!×n2!×...×nk!\frac{n!}{n_1! \times n_2! \times ... \times n_k!}
  • Example: The number of distinct permutations of the letters in "MISSISSIPPI" (1 M, 4 I, 4 S, 2 P) is:
    • 11!1!×4!×4!×2!=34,650\frac{11!}{1! \times 4! \times 4! \times 2!} = 34,650
  • Applied when solving problems involving arranging objects with repeated elements (anagrams of words with repeated letters, license plate numbers with repeated digits)

Probability and Set Theory in Counting

  • is the measure of the likelihood of an event occurring
  • represents all possible outcomes of an experiment
  • Set theory provides a framework for organizing and analyzing collections of objects
  • are visual representations used to illustrate all possible outcomes of a sequence of events, helping to calculate probabilities and count outcomes

Key Terms to Review (19)

Addition Principle: The Addition Principle is a fundamental concept in counting and probability that states the total number of possible outcomes for two or more mutually exclusive events is the sum of their individual probabilities. It is a crucial tool for determining the number of possible outcomes in various counting problems.
Binomial Coefficient: The binomial coefficient is a mathematical concept that represents the number of ways to choose a certain number of items from a set, without regard to order. It is a fundamental principle in combinatorics and has applications in various areas of mathematics, including probability, statistics, and the binomial theorem.
Combinations: Combinations refer to the selection of items from a larger set where the order of selection does not matter. This concept is crucial when determining how many ways a certain number of items can be chosen from a larger collection without regard to the arrangement of those items, often represented mathematically using the notation $$C(n, r)$$ or $$\binom{n}{r}$$, where 'n' is the total number of items and 'r' is the number of items to choose. Understanding combinations helps in solving problems related to probability, statistics, and various real-world scenarios.
Factorial: A factorial, denoted by $n!$, is the product of all positive integers less than or equal to $n$. It is used in permutations, combinations, and other mathematical calculations.
Factorial: The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n. It is a fundamental concept in combinatorics and probability that has applications in various areas of mathematics, including the Binomial Theorem and Counting Principles.
Fundamental Counting Principle: The fundamental counting principle, also known as the multiplication principle, is a fundamental concept in combinatorics that allows us to determine the number of possible outcomes in a multi-step process. It states that if one task can be performed in $a$ ways and a second task can be performed in $b$ ways, then the total number of ways to perform both tasks is $a \times b$.
Increasing function: An increasing function is a function where the value of the output increases as the input increases. Mathematically, for any two values $x_1$ and $x_2$ such that $x_1 < x_2$, the function $f(x)$ satisfies $f(x_1) \leq f(x_2)$.
Multiplication Principle: The multiplication principle is a fundamental counting technique used to determine the total number of possible outcomes when multiple independent events or choices are involved. It states that if one event can occur in $m$ ways and a second event can occur in $n$ ways, then the total number of possible outcomes for the two events is $m \times n$.
NCr: nCr, also known as the binomial coefficient, is a fundamental concept in combinatorics that represents the number of ways to choose r items from a set of n items, without regard to order. It is a crucial term in understanding the Binomial Theorem and various counting principles.
NPr: nPr, also known as permutations, is a fundamental counting principle in mathematics that calculates the number of possible arrangements or orders of a set of distinct objects, where the order of the objects matters. It is a key concept in the topic of Counting Principles.
Permutations: Permutations refer to the ordered arrangements of a set of objects or elements. They describe the different ways in which a group of items can be ordered or positioned, taking into account the order or sequence of the items.
Permutations with Repetition: Permutations with repetition refer to the number of ways to arrange a set of elements, where some elements may be repeated. This concept is particularly relevant in the context of counting principles, as it allows for the calculation of the number of possible arrangements when the order of the elements matters, and when some elements may appear more than once in the arrangement.
Probability: Probability is the measure of the likelihood that an event will occur, expressed as a number between 0 and 1. It quantifies uncertainty and can be calculated using various formulas depending on the context.
Probability: Probability is the measure of the likelihood or chance of an event occurring. It is a mathematical concept that quantifies the uncertainty associated with the outcome of a random experiment or process.
Sample space: A sample space is the set of all possible outcomes of a probability experiment. It is denoted by $S$ and serves as the foundation for defining events in probability theory.
Sample Space: The sample space is the set of all possible outcomes or results of an experiment or random event. It represents the complete set of possibilities that could occur in a given situation.
Set Theory: Set theory is a branch of mathematics that deals with the study of sets, which are collections of distinct objects. It provides a fundamental framework for understanding and analyzing relationships between different groups or categories of elements.
Subsets: A subset is a collection of elements that are contained within a larger set. It represents a portion or a part of the original set, where all the elements in the subset are also members of the larger set.
Tree Diagrams: Tree diagrams are a graphical representation used to visualize and analyze the possible outcomes of a series of related events or decisions. They provide a structured way to map out all possible scenarios and their probabilities, making them a valuable tool in the context of counting principles.
© 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
13.6 Binomial Theorem