Skip to the content ForoHackers
Log inJoin

Combinatorics: start here

Combinatorics
#909 · Ophuscado · · Report

Combinatorics is the art of counting: how many arrangements, selections or structures meet a condition, and whether one exists at all. In computing it tells you how big a search space is, how many cases a test needs, and how an algorithm's work grows. It also gives the tools behind hashing, coding and probability.

Key concepts

  • Counting principles: the rules of sum and product, permutations and combinations, and binomial coefficients.
  • Inclusion-exclusion: counting a union by adding and subtracting overlaps.
  • Pigeonhole principle: with more items than boxes, some box holds two; it proves existence without construction.
  • Recurrences and generating functions: counting problems turned into equations on sequences.
  • Double counting and bijections: counting one set in two ways, or matching it to a set that is easier to count.

Vocabulary

  • Permutation and combination: an ordered or an unordered selection of items.
  • Binomial coefficient: the number of ways to choose k items from n.
  • Catalan numbers: a sequence counting balanced brackets, binary trees and many other structures.
  • Partition: a way to split a set, or write a number as a sum.

What to study, in order

  1. Permutations, combinations and the binomial theorem, with small examples checked by brute force.
  2. Write a program that enumerates all subsets or permutations, and compare its count with the formula.
  3. Use inclusion-exclusion and the pigeonhole principle on puzzles.
  4. Solve counting problems with recurrences and dynamic programming.
  5. Meet generating functions and use them to solve a recurrence in closed form.

Related tags

#discrete-math #probability #graph-theory #algorithms #puzzles

Log in or join to reply.