Skip to the content ForoHackers
Log inJoin

Combinatorics: start here

Combinatorics
#3415 · · Quote · 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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply