Congratulations on getting this far! We’ve covered a lot of topics in the fundamentals of combinatorics and as of now, you should have a solid understanding of the topic! Let’s briefly recap the important concepts and formulas.

• Enumeration means arranging or selecting items from a set/multiset.

• The Addition and Multiplication Principle

  • “And” or “for every” means multiply
  • “Or” means add

• The number of ways to enumerate r items from a set of n distinct elements:

  • Order matters; repetition allowed:

    $n \times n \times n \ldots \times n = n^r$

  • Order matters; repetition not allowed (permutation):

    $P(n,r) = \frac{n!}{(n-r)!}$

  • Order does not matter; repetition not allowed (combination):

    $C(n,k) = \frac{n!}{k!(n-r)!} = \binom{n}{r}$

  • Order does not matter; repetition allowed:

    $C(r + n - 1, r) = \frac{(r + n - 1)!}{r!(n-1)!}$

• Permutations of a multiset:

  $P(n; r_1, r_2, \ldots, r_k) = \frac{n!}{r_1! r_2! \ldots r_k!}  = \binom{n}{r_1} \binom{n-r_1}{r_2} \ldots \binom{n - r_1 - \ldots - r_{k-1}}{r_k}$

• Solving an enumeration problem sometimes requires breaking it down into subcases, solving those, and then combining those solutions.

• If you have a case where there are more cases allowed than not allowed, it may be easier to deduct the disallowed cases from the total to determine the number of allowed cases.

$\sum{subcases \ allowed} = total \ number \ of \ ways - \sum{subcases \ not \ allowed}$

Excellent work!!