Saltar al contenido ForoHackers

Combinatoria: por dónde empezar

Combinatoria
#3416 · · Citar · Denunciar

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

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