Saltar al contenido ForoHackers

Combinatorics: start here

Combinatoria
#3415 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder