Combinatoria: el arte de contar · Lección 8 de 10
Subconjuntos
Contar todas las selecciones posibles de un conjunto.
Antes de empezar, una de repaso
Recordar algo cuesta más que releerlo, y por eso funciona mejor. Esta pregunta es de una lección anterior.
Dos opciones por elemento
Cada elemento entra o no entra en el subconjunto: dos decisiones independientes. Por el principio multiplicativo, un conjunto de n elementos tiene 2 elevado a n subconjuntos.
Eso incluye el conjunto vacío y el conjunto entero, que son subconjuntos perfectamente válidos.
La identidad de Pascal
Si se suman las combinaciones de n sobre 0, sobre 1, sobre 2… hasta n, sale el mismo 2 elevado a n. No es casualidad: se está contando lo mismo agrupado por tamaño.
Es una de las identidades combinatorias más elegantes, y se demuestra sin álgebra: basta con notar que las dos formas cuentan los mismos objetos.
Por qué esto importa
Muchos problemas de informática consisten en revisar todos los subconjuntos de un conjunto, y 2 elevado a n crece tan rápido que con 40 elementos ya es inviable.
Es la razón de que existan los algoritmos aproximados: contar rápido que algo es imposible es en sí mismo un resultado útil.
Practica
Cada ejercicio se genera con números nuevos y lo corrige el mismo motor que mueve las calculadoras del sitio. La lección se da por dominada al acertar 4 de los últimos 5.
¿Quieres comprobar tus propios números? Esta calculadora resuelve lo mismo paso a paso: Calculadora de combinaciones.