Combinatorics

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures.

Combinatorics studies methods for counting combinations of objects. Usually, the goal is to find a way to count the combinations efficiently without generating each combination separately.

Competitive Programming

Combinatorics studies methods for counting combinations of objects. Usually, the goal is to find a way to count the combinations efficiently without generating each combination separately.

I always get confused about this topic, know when to use different formulas.

• Number of Permutations $\to$ use $n!$
  • This is when you use all the elements and just swap their positions
  • If it’s a subgroup, see Permutations and Combinations
• Number of different Subsets $\to$ use $2^n-1$
  • For each element, you can either choose to include them or not
  • $-1$ because we don’t include the empty subset
• Number of subarrays (contiguous substrings) $\to$ use $\frac{n(n+1)}{2}$
  • Even less because there is the consecutive constraint
  • This is just the Summation, you have $n$ choices starting from the first element, $n-1$ starting from the second element, and $1$ choice starting from the last array
    • Do not confused with when you choose $\frac{n(n-1)}{2}$ , that is is from $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$

OMG, this series is insanely good. https://www.youtube.com/watch?v=XPPYYM6WCuE&list=PLmdFyQYShrjfPLdHQxuNWvh2ct666Na3z&index=2

Note

When repetition is allowed, you can just exponentiate it $\to n^k$ When repetition is not allowed, you need to use factorial $\to n!$

Topics

• Burnside’s Lemma
• Cayley’s Formula