Skip to the content ForoHackers
Log inJoin

Combinatoria: por dónde empezar

Combinatorics
#3416 · · Quote · Report

La combinatoria es el arte de contar: cuántas disposiciones, selecciones o estructuras cumplen una condición, y si existe alguna. En informática dice cuán grande es un espacio de búsqueda, cuántos casos necesita una prueba y cómo crece el trabajo de un algoritmo. También da las herramientas detrás del hashing, la codificación y la probabilidad.

Conceptos clave

  • Principios de conteo: las reglas de la suma y del producto, las permutaciones y combinaciones y los coeficientes binomiales.
  • Inclusión-exclusión: contar una unión sumando y restando las intersecciones.
  • Principio del palomar: con más objetos que cajas, alguna caja tiene dos; demuestra la existencia sin construir nada.
  • Recurrencias y funciones generadoras: problemas de conteo convertidos en ecuaciones sobre sucesiones.
  • Doble conteo y biyecciones: contar un conjunto de dos maneras, o emparejarlo con otro más fácil de contar.

Vocabulario

  • Permutación y combinación: una selección de elementos con orden o sin él.
  • Coeficiente binomial: el número de maneras de elegir k elementos de n.
  • Números de Catalan: una sucesión que cuenta paréntesis balanceados, árboles binarios y muchas otras estructuras.
  • Partición: una manera de dividir un conjunto, o de escribir un número como suma.

Qué estudiar, en orden

  1. Permutaciones, combinaciones y el teorema del binomio, con ejemplos pequeños comprobados por fuerza bruta.
  2. Escribe un programa que enumere todos los subconjuntos o permutaciones y compara su cuenta con la fórmula.
  3. Usa la inclusión-exclusión y el principio del palomar en acertijos.
  4. Resuelve problemas de conteo con recurrencias y programación dinámica.
  5. Conoce las funciones generadoras y úsalas para resolver una recurrencia en forma cerrada.

Etiquetas relacionadas

#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