Análisis combinatorio y permutaciones

Principio de multiplicación

Es la regla más importante de todo el análisis combinatorio. Dice lo siguiente:

Si un primer suceso puede ocurrir de $m$ maneras diferentes y, por cada una de esas maneras, un segundo suceso puede ocurrir de $n$ maneras diferentes, entonces ambos sucesos, en ese orden, pueden ocurrir de $m \times n$ maneras.

La idea clave es que existe una secuencia de decisiones y que cada decisión se toma después de haber tomado la anterior. Por eso se habla de contar por "ramas": cada opción inicial genera un nuevo conjunto de opciones para la siguiente etapa.

Ejemplo breve.
Un joven tiene 3 polos deportivos y 2 pantalones. ¿De cuántas maneras diferentes puede vestirse usando un polo y un pantalón?

Lo que debe elegir es, primero, el polo (3 opciones) y, por cada polo, un pantalón (2 opciones). El total es:

$$3 \times 2 = 6$$

Esto se entiende mejor con un diagrama de árbol:

El principio se generaliza sin dificultad a más de dos sucesos. Si una primera decisión tiene $m$ opciones, la segunda $n$, la tercera $p$ y así sucesivamente, el número total de formas de realizar toda la secuencia es el producto:

$$m \times n \times p \times \dots$$

Este principio se usa cuando las decisiones están encadenadas por la palabra «y».

Principio de adición

Complementa al anterior. Dice:

Si un suceso puede ocurrir de $m$ maneras y otro suceso distinto, que no comparte casos con el primero, puede ocurrir de $n$ maneras, entonces el suceso “uno u otro” puede ocurrir de $m + n$ maneras.

La palabra clave aquí es «o».

Ejemplo breve.
Un estudiante desea viajar de Lima a Huancayo. Puede ir en bus (hay 4 empresas) o en auto particular (puede viajar en 2 horarios distintos). ¿De cuántas maneras puede realizar el viaje?

Como no puede viajar simultáneamente en bus y auto, se suman las posibilidades:

$$4 + 2 = 6$$

El principio de adición es muy útil cuando un conteo se divide en casos excluyentes: se resuelve cada caso por separado y luego se suman los resultados.

El factorial de un número entero positivo $n$ se denota $n!$ y se define como el producto de todos los enteros consecutivos desde 1 hasta $n$:

$$n! = n(n-1)(n-2)\cdots 3\cdot 2\cdot 1$$

Por ejemplo:

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

Por convención matemática, se define:

$$0! = 1$$

Aunque no se justifica intuitivamente de inmediato, es necesario para que las fórmulas de combinaciones y variaciones funcionen en casos límite.

Simplificación de factoriales

En los problemas no interesa calcular todo el producto, sino simplificar. La propiedad fundamental es que un factorial puede "desdoblarse" hasta el factorial que convenga:

$$n! = n \cdot (n-1)!$$

O también:

$$n! = n(n-1)(n-2)!$$

Por ejemplo:

$$\frac{7!}{5!} = \frac{7 \times 6 \times 5!}{5!} = 7 \times 6 = 42$$

Este tipo de simplificación aparece constantemente en las fórmulas de variaciones y combinaciones.

Permutaciones lineales simples

Una permutación de un conjunto es un ordenamiento de todos sus elementos. Si tenemos $n$ elementos distintos, el número de formas de ordenarlos en fila es:

$$P_n = n!$$

Ejemplo breve.
¿De cuántas maneras se pueden ordenar 4 libros distintos en un estante?

Como hay que colocar todos los libros y el orden importa, el número de ordenamientos es:

$$P_4 = 4! = 4 \times 3 \times 2 \times 1 = 24$$

La justificación es directa por el principio de multiplicación: para la primera posición hay 4 opciones, para la segunda quedan 3, para la tercera 2 y para la última 1.

Variaciones o permutaciones parciales

Muchas veces no se toman todos los elementos, sino solo una parte, y el orden importa. A estos ordenamientos se les llama variaciones o arreglos parciales. Si de $n$ elementos distintos se toman grupos ordenados de $r$ elementos, con $r \le n$, el número de variaciones es:

$$V_{r}^{n} = \frac{n!}{(n-r)!}$$

También se escribe $V(n,r)$ o $nPr$. La fórmula se obtiene directamente:

$$V_{r}^{n} = n(n-1)(n-2)\cdots (n-r+1)$$

Es decir, se multiplican $r$ factores decrecientes a partir de $n$.

Ejemplo breve.
Con los dígitos 5, 6, 7, 8, ¿cuántos números de dos cifras diferentes se pueden formar?

La primera cifra tiene 4 opciones; la segunda, como debe ser diferente, tiene 3. Por tanto:

$$4 \times 3 = 12$$

Eso es $V_{2}^{4} = 4 \times 3 = 12$.

Permutaciones circulares

Cuando los elementos se ordenan alrededor de un círculo (personas alrededor de una mesa, collares, fogatas), el orden ya no se mide de izquierda a derecha, sino de una posición relativa. En un círculo no hay primera posición fija, por lo que girar todos los elementos no produce un ordenamiento distinto.

Para $n$ elementos distintos, el número de permutaciones circulares es:

$$PC_n = (n-1)!$$

¿Por qué? Porque fijamos mentalmente un elemento como punto de referencia. Fijado ese elemento, los otros $n-1$ se pueden ordenar libremente a su alrededor, y eso da $(n-1)!$ posibilidades.

Ejemplo breve.
¿De cuántas maneras pueden sentarse 5 personas alrededor de una mesa redonda?

Fijamos una persona como referencia; las otras 4 se ordenan de $4! = 24$ maneras.

$$PC_5 = (5-1)! = 4! = 24$$

Permutaciones con elementos repetidos

Si en un conjunto hay elementos que se repiten, no todos los intercambios generan ordenamientos distintos. Por ejemplo, al ordenar las letras A, A, B, si intercambiamos las dos A entre sí, visualmente obtenemos la misma palabra.

En general, si tenemos $n$ objetos, donde un primer tipo se repite $r_1$ veces, otro $r_2$ veces, y así sucesivamente, el número de permutaciones distinguibles es:

$$P_{n}^{r_1,r_2,\dots,r_k} = \frac{n!}{r_1! \cdot r_2! \cdots r_k!}$$

donde $r_1+r_2+\cdots+r_k = n$.

Ejemplo breve.
¿Cuántas palabras de 4 letras, con o sin sentido, se pueden formar con las letras de la palabra “CACA”?

Hay 4 letras: C se repite 2 veces, A se repite 2 veces. El total es:

$$\frac{4!}{2!\cdot 2!} = \frac{24}{2\cdot 2} = 6$$

Las palabras serían: CACA, CAAC, CCAA, ACAC, AACC, AC CA.

Este tipo de conteo es muy frecuente en problemas con palabras como “COCOTERO” o números con dígitos repetidos.

Una combinación es una selección de elementos en la que no interesa el orden. Es decir, dos combinaciones son diferentes solo si difieren en al menos un elemento.

El número de combinaciones de $n$ elementos tomados de $r$ en $r$ se denota $C_{r}^{n}$, $\binom{n}{r}$ o $C(n,r)$, y se calcula:

$$C_{r}^{n} = \frac{n!}{r!(n-r)!}$$

¿De dónde sale esta fórmula? Primero, si importara el orden, tendríamos $V_{r}^{n} = \frac{n!}{(n-r)!}$. Pero cada grupo de $r$ elementos puede ordenarse de $r!$ maneras distintas; como para combinaciones todas esas maneras cuentan como una sola, dividimos entre $r!$:

$$C_{r}^{n} = \frac{V_{r}^{n}}{r!} = \frac{n!}{(n-r)! \cdot r!}$$

Ejemplo breve.
En un aula hay 6 estudiantes. ¿Cuántos grupos de estudio de 4 personas se pueden formar?

El orden dentro del grupo no importa; elegir a Ana, Bruno, Carla y David es lo mismo que elegir a David, Carla, Bruno y Ana.

$$C_{4}^{6} = \frac{6!}{4!\cdot 2!} = \frac{6 \times 5}{2 \times 1} = 15$$

Propiedades importantes de las combinaciones

• $C_{0}^{n} = 1$: solo hay una forma de no elegir nada.
• $C_{1}^{n} = n$: hay $n$ formas de elegir 1 elemento.
• $C_{n}^{n} = 1$: solo hay una forma de elegir todos.
• Propiedad complementaria: $C_{r}^{n} = C_{n-r}^{n}$. Por ejemplo, $C_{4}^{6} = C_{2}^{6} = 15$, porque elegir 4 de 6 es equivalente a excluir 2 de 6.
• La suma de todas las combinaciones para $r=0$ hasta $r=n$ es:

$$C_{0}^{n} + C_{1}^{n} + C_{2}^{n} + \cdots + C_{n}^{n} = 2^{n}$$

Esta propiedad es útil para problemas de número total de subconjuntos o selecciones posibles.

Diferencia entre variación y combinación

Una tabla puede aclarar la distinción:

Una buena estrategia es preguntarse: si intercambio dos elementos dentro del grupo, ¿obtengo un caso nuevo?

• Si la respuesta es sí, se trata de variación (o permutación).
• Si la respuesta es no, se trata de combinación.

En los exámenes de admisión, los problemas rara vez piden aplicar una fórmula directamente. Lo típico es que impongan restricciones: ciertos elementos deben estar juntos, otros separados, algunos no pueden ocupar ciertas posiciones, hay condiciones de género o de cantidad mínima. Para estos casos necesitamos herramientas de combinación y estrategias.

1. Método de las cajas o casilleros

Es una representación visual del principio de multiplicación. Se dibujan tantas cajas como posiciones o decisiones haya y se escribe en cada caja el número de opciones disponibles luego de aplicar las restricciones.

Ejemplo general.
¿Cuántos números de 3 cifras distintas se pueden formar con los dígitos 1, 2, 3, 4, 5 si el número debe ser par?

Un número es par si termina en 2 o 4. Empecemos por la última cifra, que tiene restricción:

• Última cifra: 2 opciones (2 o 4).
• Luego, la primera cifra: de 5 dígitos quitando el ya usado, quedan 4 opciones.
• Segunda cifra: quedan 3 opciones.

Total: $2 \times 4 \times 3 = 24$.

2. Elementos que deben ir juntos

Cuando un grupo de elementos debe permanecer unido, el truco es tratar a ese grupo como un solo bloque. Luego se cuenta el ordenamiento de los bloques y, al final, se multiplica por los ordenamientos internos del bloque.

Ejemplo.
¿De cuántas maneras se pueden sentar 4 personas en una fila si dos de ellas, Ana y Beto, deben estar juntos?

Consideramos a Ana y Beto como un bloque $AB$. Entonces tenemos 3 elementos: el bloque $AB$ y las otras dos personas $C$ y $D$. Estos 3 elementos se ordenan de $3! = 6$ maneras.
Dentro del bloque, Ana y Beto pueden ubicarse de $2! = 2$ maneras ($AB$ o $BA$).

Total:

$$3! \times 2! = 6 \times 2 = 12$$

3. Elementos que no deben ir juntos

Aquí conviene usar el complemento: contar todos los arreglos posibles y restar aquellos en los que los elementos prohibidos sí están juntos.

Ejemplo.
¿De cuántas maneras se pueden sentar 5 personas en una fila si dos personas, Ana y Beto, no deben ir juntas?

Total sin restricciones: $5! = 120$.
Casos con Ana y Beto juntos (bloque $AB$): $4! \times 2! = 24 \times 2 = 48$.
Casos donde no están juntos:

$$120 - 48 = 72$$

4. Restricciones en mesas circulares

Las restricciones se aplican igual, pero recordando que la base circular es $(n-1)!$. Si dos personas deben ir juntas, se forma un bloque, y como ahora hay un "marco circular" con menos elementos, se usa $(k-1)!$ para los bloques y se multiplica por $2!$ si el bloque tiene dos personas intercambiables.

Ejemplo.
¿De cuántas maneras pueden sentarse 6 personas alrededor de una mesa redonda si dos de ellas deben estar juntas?

Formamos un bloque con las dos personas. Quedan 5 elementos: el bloque y las otras 4 personas. Las 5 se ubican circularmente de $(5-1)! = 4! = 24$ maneras. El bloque interior tiene $2! = 2$ ordenamientos. Total:

$$4! \times 2! = 24 \times 2 = 48$$

5. Selecciones con condiciones de género o de cantidad

En problemas de equipos o comités, se usa la combinación como base y luego el principio de multiplicación o adición según los casos.

Ejemplo guía.
De un grupo de 7 hombres y 5 mujeres se quiere formar un comité de 4 personas con exactamente 2 mujeres.

• Elegir 2 mujeres de 5: $C_{2}^{5} = 10$.
• Elegir 2 hombres de 7: $C_{2}^{7} = 21$.
• Multiplicar: $10 \times 21 = 210$.

Si la condición es “al menos una mujer”, conviene dividir en casos o usar el complemento:

• Caso 1: exactamente 1 mujer y 3 hombres.
• Caso 2: exactamente 2 mujeres y 2 hombres.
• Caso 3: exactamente 3 mujeres y 1 hombre.
• Caso 4: exactamente 4 mujeres y 0 hombres.

Se suman todos los casos.

Alternativa más rápida: contar el total de comités $C_{4}^{12}$ y restar el caso sin ninguna mujer $C_{4}^{7}$. El resultado es el mismo.

6. Separación en casos excluyentes

En muchos problemas con restricciones, la salida más ordenada es separar en casos según la restricción. Por ejemplo, si un dígito no puede ir en cierta posición, se analiza primero esa posición y se desdobla si es necesario.

Ejemplo.
¿Cuántos números de 4 cifras se pueden formar con los dígitos 0, 1, 2, 3, 4, 5 sin repetir si el número debe ser mayor que 3000?

La primera cifra debe ser 3, 4 o 5.

• Si la primera cifra es 3, quedan 5 dígitos para las otras 3 posiciones: $5 \times 4 \times 3 = 60$.
• Si es 4: otros 60.
• Si es 5: otros 60.

Total: $60 + 60 + 60 = 180$.

Si hubiera más restricciones, por ejemplo que el número sea par, se combinarían el último dígito y el primero, separando por casos para no contradecir.