Lección 36 — Principio fundamental del conteo

PFC y árboles

Enunciado

Si un experimento consiste en $k$ etapas sucesivas e independientes, con $n_1$ resultados en la primera, $n_2$ en la segunda, ..., $n_k$ en la $k$-ésima, entonces el número total de resultados posibles es: $N = n_1 \cdot n_2 \cdots n_k$

Principio aditivo (alternativa)

Si una tarea puede hacerse por método A con $m$ formas O por método B con $n$ formas (excluyentes), el total es $m + n$.

Ejemplo arquetípico

Contraseña de 4 caracteres: cada uno puede ser A-Z (26 opciones). Total: $26^4 = 456\,976$.

Árbol de posibilidades

Cada etapa "ramifica": el árbol tiene $n_1$ raíces, cada una con $n_2$ hijos, etc. Hojas = total de resultados.

Restricciones — "sin repetición"

Si los zapatos no pueden repetirse, el primero tiene 5 opciones, el segundo 4, el tercero 3: combinaciones sin repetición. Generaliza a arreglo (Lección 37).

Funciones entre conjuntos

• Total de funciones $f: A \to B$ con $|A| = m, |B| = n$: $n^m$.
• Funciones inyectivas ($f: A \to B$ con $m \leq n$): $n!/(n-m)!$ (arreglo).
• Funciones biyectivas ($m = n$): $n!$ (permutación).