Extension Combinatorics – Permutations and combinations

This lesson comprises two (2) master classes focusing on:

• Permutations
• Combinations
• Pigeonhole principle
• Pascal’s triangle

Content:

ME-A1.1

• List and count the number of ways an event can occur
• Use the fundamental counting principle (also known as the multiplication principle)
• Use factorial notation to describe and determine the number of ways n different items can be arranged in a line or a circle
  • solve problems involving cases where some items are not distinct (excluding arrangements in a circle)
• Solve simple problems and prove results using the pigeonhole principle
  • understand that if there are \( n \) pigeonholes and \( n+1 \) pigeons to go into them, then at least one pigeonhole must hold 2 or more pigeons
  • generalise to: If \( n \) pigeons are sitting in k pigeonholes, where \( n>k \), then there is at least one pigeonhole with at least \( \frac{n}{k} \) pigeons in it
  • prove the pigeonhole principle
• Understand and use permutations to solve problems
  • understand and use the notation \( ^nP_r \) and the formula \( ^nP_r =\frac{n!}{(n−r)!} \)
• Solve problems involving permutations and restrictions with or without repeated objects
• Understand and use combinations to solve problems
  • understand and use the notations \( \binom{n}{r} \) and \( ^nC_r \) and the formula \( ^nC_r=\frac{n!}{r!(n−r)!} \)
• Solve practical problems involving permutations and combinations, including those involving simple probability situations

ME-A1.2

• Expand \( (x+y)^n \) for small positive integers \( n \)
  • note the pattern formed by the coefficients of \( x \) in the expansion of \( (1+x)^n \) and recognise links to Pascal’s triangle
  • recognise the numbers \( \binom{n}{r} \) (also denoted \( ^nC_r \) ) as binomial coefficients
• Derive and use simple identities associated with Pascal’s triangle
  • establish combinatorial proofs of the Pascal’s triangle relations \( ^nC_0=1 \), \( ^nC_n=1 \); \( ^nC_r=^{n−1}C_{r−1}+^{n−1}C_r \) for \( 1 \le r \le n−1 \); and \( ^nC_r=^nC_{n−r} \)