Combinatoria

La idea

Qué vas a aprender

• Principio multiplicativo: contar por etapasmétodo

  Si una elección se arma en etapas sucesivas y cada camino tiene una cantidad conocida de opciones, se aplica el principio multiplicativo. Si la etapa 1 tiene $m$ opciones y, para cada una, la etapa 2 tiene $n$, hay $m\cdot n$ resultados. Una hamburguesería con 3 hamburguesas, 4 bebidas y 2 postres ofrece $3\cdot4\cdot2=24$ combos.

  Un listado sistemático escribe los casos siguiendo siempre el mismo orden. Con remeras R y A y pantalones N y G, el listado $(R,N),(R,G),(A,N),(A,G)$ confirma los $2\cdot2=4$ conjuntos. Un diagrama de árbol representa cada elección con una rama y cada resultado completo con una hoja. Si todas las ramas continúan con las mismas cantidades, el producto cuenta las hojas. Si una restricción cambia las continuaciones, se podan las ramas prohibidas y se suman los productos de casos disjuntos.

  El conector ayuda: si el resultado toma una opción de cada etapa —A Y B— se multiplican las opciones; si se elige entre alternativas que no pueden ocurrir juntas —A O B— se suman. Antes de operar hay que comprobar que los casos no se superpongan y que el árbol o el listado no omita ninguna posibilidad.

• Factorial y permutaciones: ordenar todos los elementosconcepto

  El factorial de un número natural $n$ es $n!=n\cdot(n-1)\cdots2\cdot1$. Por ejemplo, $5!=120$, y por convención $0!=1$. Una permutación ordena TODOS los elementos. Si los $n$ elementos son distintos, hay $P_n=n!$ órdenes: para el primer lugar hay $n$ candidatos, para el segundo $n-1$ y así sucesivamente.

  Por ejemplo, 5 personas distintas pueden ordenarse en una fila de $5!=120$ maneras. Si algunos objetos son indistinguibles, intercambiarlos no crea un orden nuevo y hay que quitar duplicaciones. Con $n$ objetos donde se repiten $n_1,n_2,\ldots,n_r$ de cada tipo y $n_1+n_2+\cdots+n_r=n$, la cantidad es $\dfrac{n!}{n_1!n_2!\cdots n_r!}$.

  La palabra CASA tiene 4 letras, pero las dos A son iguales. Sus ordenamientos distintos son $4!/2!=12$, no 24. Este tipo de repetición no es $n^k$: se están ordenando todos los objetos de un multiconjunto y se divide por los intercambios indistinguibles.

• Variaciones: elegir y ordenar (cuando el orden importa)método

  Si elegís $k$ elementos de un total de $n$, importa el orden y no se repiten, usás variaciones: $V_{n,k}=\dfrac{n!}{(n-k)!}=n\cdot(n-1)\cdots(n-k+1)$. En una carrera con 8 participantes, un podio tiene $V_{8,3}=8\cdot7\cdot6=336$ resultados.

  Si hay $k$ posiciones ordenadas, en cada una se pueden usar cualquiera de los mismos $n$ símbolos y la repetición está permitida, entonces sí hay $n^k$ secuencias. Un PIN de 4 dígitos tiene $10^4=10000$, incluyendo ceros iniciales. Esta potencia exige que cada posición conserve las mismas $n$ opciones.

  Las restricciones cambian ese producto. Un código de 3 cifras distintas no puede empezar con 0: la primera posición tiene 9 opciones, la segunda 9 —incluido el 0 si no se usó— y la tercera 8, para un total de $9\cdot9\cdot8=648$. Según la condición conviene separar casos, fijar primero una posición, contar el complemento o podar un árbol; no se aplica una fórmula ignorando los casos prohibidos.

• Combinaciones: elegir sin importar el ordenmétodo

  Si elegís $k$ elementos de $n$, el orden NO importa y no se repiten, usás combinaciones: $C_{n,k}=\binom{n}{k}=\dfrac{n!}{k!(n-k)!}$. Cada grupo fue contado $k!$ veces por las variaciones, de modo que $C_{n,k}=V_{n,k}/k!$. Elegir una comisión de 3 personas entre 8 da $C_{8,3}=56$.

  Si el orden no importa pero se puede elegir varias veces un mismo tipo, aparece una combinación con repetición. Elegir $k$ objetos entre $n$ tipos con disponibilidad suficiente se cuenta con $CR_{n,k}=\binom{n+k-1}{k}$. Por ejemplo, un pote de 3 bochas elegido entre 4 gustos, admitiendo gustos repetidos y sin importar el orden de pedido, tiene $\binom{4+3-1}{3}=\binom{6}{3}=20$ combinaciones.

  La interpretación decide la fórmula. Un pote con dos bochas de chocolate y una de vainilla es el mismo sin importar en qué orden se sirvan; en cambio, una clave C-V-C es distinta de V-C-C porque sus posiciones sí importan. Decir solamente «se puede repetir» no alcanza.

• La pregunta clave: ¿importa el orden? ¿se repite?método

  Antes de elegir una fórmula, describí qué constituye un resultado. Si importa el orden, distinguí entre ordenar todo —permutación— y llenar $k$ posiciones —variación sin repetición o $n^k$ con repetición uniforme—. Si el orden no importa, distinguí combinación sin repetición de combinación con repetición. Si se ordenan objetos entre los que hay copias indistinguibles, corresponde una permutación de multiconjunto.

  Después revisá restricciones: posiciones prohibidas, elementos que deben ir juntos o separados, cantidades exactas por categoría y ramas con diferente número de opciones. Para pocos casos, un listado o árbol permite comprobar el modelo; para muchos, se separa en casos disjuntos, se usa el complemento o se fijan primero los elementos restringidos. Los conteos parciales se suman solo si no se superponen.

  Cuando todos los resultados elementales son igualmente probables, la regla de Laplace usa estos conteos: $P(\text{evento})=\frac{\text{casos favorables}}{\text{casos totales}}$. Numerador y denominador deben emplear el mismo criterio de orden, repetición y restricciones.

Ejemplos resueltos

• Árbol y restricción. Una pizzería combina 1 de 5 pizzas, 1 de 3 bebidas y 1 de 4 postres o ninguno: sin restricciones hay $5\cdot3\cdot5=75$ promos. Si una de las bebidas solo puede venderse sin postre, el árbol ya no tiene cinco continuaciones en todas sus ramas. Para cada pizza, las otras dos bebidas conservan 5 opciones de postre y la bebida restringida solo 1: $2\cdot5+1=11$. En total hay $5\cdot11=55$ promos. Podar las ramas prohibidas evita usar el producto uniforme de 75.
• Variación vs combinación: el mismo problema, dos respuestas. En una final de atletismo corren 10 personas. (a) ¿Cuántos podios distintos (1°, 2° y 3°) puede haber? Acá el orden importa: no es lo mismo salir primero que tercero. Es una variación: $V_{10,3} = 10 \cdot 9 \cdot 8 = 720$ podios. (b) De esas mismas 10 personas se sortean 3 para el control antidoping. ¿Cuántos grupos posibles? Acá el orden NO importa: el grupo formado por Ana, Beto y Caro es el mismo sin importar en qué orden salieron sorteados. Es una combinación: $C_{10,3} = \frac{10 \cdot 9 \cdot 8}{3!} = \frac{720}{6} = 120$ grupos. Fijate en la relación: hay 720 podios y 120 grupos, y $720 = 120 \cdot 3!$. Es porque cada grupo de 3 personas se puede ordenar de $3! = 6$ maneras distintas como podio. Dividir por $3!$ es exactamente lo que "borra" el orden.
• Tres significados de repetición. (1) Ordenar las letras de CASA: hay $4!/2!=12$ órdenes porque las dos A son indistinguibles. (2) Elegir 3 bochas entre 4 gustos, admitiendo repetir y sin importar el orden: hay $\binom{6}{3}=20$ combinaciones con repetición. (3) Formar un PIN de 4 posiciones con 10 dígitos reutilizables: hay $10^4=10000$ secuencias porque el orden sí importa. La palabra «repetición» no determina por sí sola una única cuenta.

Errores comunes

• Cuando el orden no importa, usa la fórmula de variaciones (o al revés): no divide por $k!$.

  Las variaciones cuentan como distintos dos arreglos con los mismos elementos en distinto orden. Si el orden no importa (un grupo, una comisión, los números del Quini), estás contando cada grupo $k!$ veces de más y el resultado sale inflado. Al revés, si el orden sí importa y usás combinaciones, el resultado sale corto.

  Cómo corregirlo: Antes de elegir la fórmula preguntate: si intercambio dos de los elementos elegidos, ¿es un caso diferente? Si sí, es variación. Si es exactamente el mismo caso, es combinación, y ahí dividís por $k!$: $C_{n,k} = \frac{V_{n,k}}{k!}$.

• Para contar por etapas, suma las opciones de cada etapa en vez de multiplicarlas.

  Sumar contaría "una opción de la etapa 1 O una de la etapa 2". Pero cuando el resultado combina las etapas ("una remera Y un pantalón"), cada opción de una etapa se combina con TODAS las de la otra: eso es multiplicar. Con 3 remeras y 4 pantalones no hay $3 + 4 = 7$ conjuntos, hay $3 \cdot 4 = 12$.

  Cómo corregirlo: Mirá el conector: si armás el resultado tomando algo de cada etapa ("Y"), multiplicás; si elegís entre alternativas excluyentes ("O"), sumás.

• Trata toda repetición como $n^k$, o usa fórmulas sin aclarar si se repiten posiciones, tipos elegidos u objetos indistinguibles.

  $n^k$ solo cuenta $k$ posiciones ordenadas que conservan las mismas $n$ opciones. Un grupo sin orden con tipos repetibles y un ordenamiento con copias indistinguibles identifican como iguales casos diferentes de los de una contraseña.

  Cómo corregirlo: Definí qué cambia un resultado: posiciones ordenadas con repetición uniforme, $n^k$; selección sin orden con repetición, $\binom{n+k-1}{k}$; ordenamiento de $n$ objetos con multiplicidades $n_i$, $n!/(n_1!\cdots n_r!)$. Después aplicá las restricciones del problema.

• Cree que $0! = 0$.

  Por convención matemática $0! = 1$, no $0$. Si tomás $0! = 0$, fórmulas como $C_{n,n} = \frac{n!}{n!\,0!}$ te darían una división por cero o un resultado absurdo, cuando en realidad elegir los $n$ elementos entre $n$ da exactamente 1 forma.

  Cómo corregirlo: Grabate $0! = 1$. Tiene sentido: hay una sola manera de elegir todo el conjunto. Verificalo con la fórmula: $C_{5,5} = \frac{5!}{5!\,0!} = \frac{120}{120 \cdot 1} = 1$.

En resumen