Principios de conteo

Contar es asignar un número de elementos a un conjunto de posibilidades. Hacerlo enumerando funciona para conjuntos pequeños; los principios de conteo permiten contar estructuras grandes combinando conteos parciales.

Principio aditivo

Si una tarea puede resolverse de m formas por un camino o de n formas por otro camino disjunto (sin solape), el total es m más n. La condición esencial es que los casos no se solapen.

Principio multiplicativo

Si una tarea se descompone en pasos sucesivos, con m opciones en el primer paso y n en el segundo, el número de resultados es m por n. Es el principio del menú: tantos platos como combinaciones de primero y segundo.

El producto cartesiano

• Contar pares ordenados de dos conjuntos es multiplicar sus tamaños.
• Se generaliza a n-tuplas eligiendo un elemento de cada factor.
• Es el corazón del principio multiplicativo expresado en lenguaje de conjuntos.

Cuándo usar cada uno

• Aditivo para alternativas excluyentes: esto o aquello.
• Multiplicativo para decisiones en secuencia: esto y luego aquello.
• Un mismo problema suele mezclar ambos: se suman ramas que se multiplican por dentro.

Contar por complemento

A veces es más fácil contar lo que NO cumple una condición y restarlo del total. «Al menos un» se ataca así: total menos ninguno. Este cambio de perspectiva simplifica problemas que de frente son terquemente difíciles.

Inclusión-exclusión

• Al sumar dos conjuntos que se solapan, la intersección cuenta dos veces.
• Se corrige restando la intersección una vez.
• Para tres o más conjuntos, el patrón alterna sumar y restar.

Evitar el doble conteo

El enemigo silencioso del conteo es contar lo mismo dos veces o perder un caso. Ordenar el razonamiento en casos disjuntos y exhaustivos protege contra ambos errores.

Verificar en pequeño

• Comprobar el resultado enumerando cuando el caso sea minúsculo.
• Una fórmula que falla en el caso pequeño falla siempre.
• Las pruebas de cordura detectan el sobreconteo pronto.

Contar en ciencia de datos

• Espacios de hiperparámetros: combinaciones de valores candidatos.
• Tamaño de un dataset de características binarias: dos elevado a n.
• Nº de subconjuntos de validación posibles: crece exponencialmente.

Errores frecuentes

• Sumar en vez de multiplicar cuando las decisiones se encadenan.
• Aplicar el principio aditivo sobre casos que se solapan y sobrecontar.
• Olvidar un caso al dividir el problema en subcasos no exhaustivos.

Ejemplo resuelto: placas de matrícula

Una placa tiene tres letras seguidas de dos cifras, con repetición permitida tanto en letras como en cifras. Cuenta cuántas placas distintas caben.

1. Cada una de las tres letras admite veintiséis opciones.
2. Cada una de las dos cifras admite diez opciones.
3. Como son decisiones en secuencia, se multiplican todos los factores.
4. El producto es veintiséis por veintiséis por veintiséis por diez por diez.
5. Resultado: diecisiete millones quinientos setenta y seis mil placas posibles.

¿Para qué sirve en la realidad?

Contar sin enumerar dimensiona espacios de búsqueda: el número de combinaciones de hiperparámetros a probar, de claves posibles o de subconjuntos de características determina si un algoritmo puede agotar el espacio o hay que muestrearlo.

Regla de la suma
Principio aditivo de conteo para casos disjuntos.

# Principios de conteo
## Aditivo
### alternativas excluyentes
### casos disjuntos
## Multiplicativo
### decisiones en secuencia
### producto cartesiano
## Trucos
### contar por complemento
### inclusión-exclusión

Principio multiplicativo
Contar resultados de decisiones encadenadas multiplicando sus opciones.