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
    • “Or” means add
  • The number of ways to enumerate r items from a set of n distinct elements:

    • Order matters; repetition allowed:
      n×n×n×n=nrn \times n \times n \ldots \times n = n^r
    • Order matters; repetition not allowed (permutation):
      P(n,r)=n!(nr)!P(n,r) = \frac{n!}{(n-r)!}
    • Order does not matter; repetition not allowed (combination):
      C(n,k)=n!k!(nr)!=(nr)C(n,k) = \frac{n!}{k!(n-r)!} = \binom{n}{r}
    • Order does not matter; repetition allowed:
      C(r+n1,r)=(r+n1)!r!(n1)!C(r + n - 1, r) = \frac{(r + n - 1)!}{r!(n-1)!}
  • Permutations of a multiset:

    P(n;r1,r2,,rk)=n!r1!r2!rk!=(nr1)(nr1r2)(nr1rk1rk)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.

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

Excellent work!!

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?