Learn

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
• 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!!