MDM4U-B - Unit 2: Combinatorics Notes

Unit 2: Combinatorics

Introduction to Combinatorics

  • Combinatorics deals with counting the number of ways in which something can be done.

  • It includes techniques such as counting principles, permutations, combinations, and applications involving Venn diagrams and Pascal's Triangle.

Key Concepts

  • Combinatorics: The branch of mathematics dealing with counting, arrangements, and combinations of objects.

  • Additive Counting Principle: If the number of ways to complete tasks are a, b, c, etc., the total is a + b + c + …

  • Multiplicative Counting Principle: If tasks can occur independently, the total number of ways to complete them is a × b × c × …

  • Permutations: Arrangements of objects where order matters (denoted as P(n, r)).

  • Combinations: Selections of objects where order does not matter (denoted as C(n, r)).

  • Factorials: The product of all positive integers up to n, denoted as n!.

  • Pascal's Triangle: A triangular array of binomial coefficients that shows the coefficients of (a + b)^n.

Lesson 6: Organized Counting and Permutations

  • Multiplicative Counting Principle example:

    • If there are 3 routes to market, 3 routes to the grocery store, and 2 routes home: Total Routes = 3×3×2=183 × 3 × 2 = 18.

  • Permutations:

    • If order matters:

    • Example: If a track team has 12 members and you need to choose 4, order matters.

  • Factorial Notation:

    • Notation: n! = n × (n-1)!
      also relates to permutations and combinations.

Lesson 7: Combinations

  • Combinations Defined: The number of ways to select items where the order does not matter: C(n, r) = n! / [(n - r)! r!].

  • Example: Choosing 3 from 10:

    • C(10, 3) = 10!/(7!3!)=12010! / (7! 3!) = 120.

  • Applications: Practical situations where combinations matter, such as voting, lottery, etc.

Lesson 8: Combinatorics Problems Involving Repetition and Overlaps

  • Repetition in Permutations: For the arrangement of letters in “APPLE,” if letters are repeated, adjust using factorials to account for repeats: Total arrangements = n! / (r1! r2! …).

  • Venn Diagrams and the Inclusion-Exclusion Principle:

    • Used to calculate the number of items in two overlapping sets without double-counting.

Lesson 9: Pascal's Triangle and Its Applications

  • Pascal's Triangle shows relationships in combinations where each value is derived from the sum of the two numbers directly above it.

  • Connection to Combinations: Each element of Pascal’s Triangle corresponds to C(n, r).

    • Example: To find number of paths in a grid, use C(n, k) where n is total moves and k is specific direction moves.

  • Sum of Elements in a Row: Sum of elements in row n = 2^n.

Important Formulas

  • Multiplicative Principle: If task 1 can happen in a ways and task 2 in b ways, then both can happen in a × b ways.

  • Additive Principle: If task 1 can happen in a ways or task 2 can happen in b ways (but not both), the total is a + b.

  • Number of Combinations: C(n, r) = n! / [(n - r)! r!].

  • Number of Permutations: P(n, r) = n! / (n - r)!

Overall Expectations

  • Be able to apply counting techniques to find the number of possibilities in a situation with discrete outcomes.

  • Use factorials to simplify equations.

  • Solve problems involving permutations and combinations for probability calculations.

Practice Problems

  1. Find number of arrangements for the word "AARDVARK".

  2. Calculate the number of combinations for groups under specific constraints.

  3. Develop total unique arrangements considering overlaps in data sets.

  4. Create Venn diagrams to represent complex relations in data.

  5. Work with Pascal's triangle for combinatorial problems and route counting in grids.

Mid-Course Review

  • Use review lessons to assess understanding of combinatorics and statistics to prepare for further studies in data management.