Análisis combinatorio I

1.1 La idea intuitiva

Cuando una persona puede elegir una cosa u otra, y ambas opciones no pueden ocurrir al mismo tiempo, las posibilidades totales se obtienen sumando.

Piensa en un estudiante que desea viajar de Lima a Ica. Tiene a su disposición 3 empresas de bus y 2 líneas de tren. Como solo puede viajar por bus o por tren, no puede elegir ambos medios a la vez. Entonces:

$$\text{Total de maneras} = 3 + 2 = 5$$

Este es el principio de adición.

1.2 Definición formal

Si un evento $A$ ocurre de $m$ maneras diferentes y un evento $B$ ocurre de $n$ maneras diferentes, y no pueden ocurrir ambos de manera simultánea, entonces el evento $A$ o $B$ ocurre de

$$m+n$$

maneras diferentes.

1.3 ¿Cuándo se suma?

Se suma cuando las opciones son excluyentes, es decir, cuando al elegir una opción renunciamos a las demás. Las palabras clave suelen ser: o, alternativas, puede optar por, uno u otro.

Ejemplo breve

Un alumno puede presentar su trabajo final de dos formas: exponer oralmente (puede elegir entre 5 temas) o entregar una monografía (puede elegir entre 3 formatos). No puede hacer ambas cosas a la vez. El número total de maneras de elegir es:

$$5 + 3 = 8$$

Es importante verificar que no haya superposición. Si un mismo elemento pudiera contarse en ambas opciones, no se debe sumar directamente.

2.1 La idea intuitiva

Cuando un proceso se realiza en etapas, y para cada elección de la primera etapa se puede elegir libremente en la segunda, las posibilidades totales se obtienen multiplicando.

Imagina que para ir de la ciudad $A$ a la ciudad $C$ debes pasar por $B$. De $A$ a $B$ hay 4 caminos, y de $B$ a $C$ hay 6 caminos. Para viajar de $A$ a $C$ pasando por $B$, debes elegir:

1. un camino de $A$ a $B$: 4 opciones;
2. un camino de $B$ a $C$: 6 opciones.

Por cada uno de los 4 primeros caminos, hay 6 caminos siguientes. Entonces:

$$4 \times 6 = 24$$

rutas distintas.

2.2 Definición formal

Si un evento $A$ ocurre de $m$ maneras diferentes y, para cada una de ellas, un evento $B$ ocurre de $n$ maneras diferentes, entonces el evento $A$ y $B$, de manera simultánea o consecutiva, ocurre de

$$m \times n$$

maneras diferentes.

2.3 Aplicación directa a un código de cuatro dígitos

Un código de 4 dígitos se forma eligiendo una cifra para la primera posición, otra para la segunda, otra para la tercera y otra para la cuarta. Si cualquiera de las cifras puede repetirse, entonces para cada posición hay 10 opciones: $0,1,2,\ldots,9$.

Por el principio de multiplicación:

$$10 \times 10 \times 10 \times 10 = 10^4 = 10\,000$$

Es un error común pensar que el primer dígito no puede ser cero. Eso es cierto cuando se pide formar números de cuatro cifras, pero no cuando se pide un código: un código puede empezar en cero, como $0573$.

2.4 Diferencia clave entre “o” y “y”

• Si el problema dice “o”, se trata de alternativas excluyentes: se suma.
• Si el problema dice “y”, se trata de etapas sucesivas o elecciones simultáneas: se multiplica.

Por ejemplo:

• “Elegir un helado de vainilla o un helado de chocolate”: se suma.
• “Elegir un helado de vainilla y un queque”: se multiplica.

3.1 Definición

Para contar ordenamientos con rapidez, usamos el factorial de un número natural $n$, denotado $n!$, que se define como el producto de todos los números naturales desde 1 hasta $n$:

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

Ejemplos:

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

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

$$1! = 1$$

Por convención, se define:

$$0! = 1$$

Esta convención no es arbitraria; permite que varias fórmulas funcionen incluso cuando no hay elementos que ordenar.

3.2 Propiedad útil para simplificar

El factorial tiene una propiedad muy usada en simplificaciones:

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

Así, por ejemplo:

$$7! = 7 \times 6!$$

También es frecuente simplificar cocientes como:

$$\frac{8!}{5!} = \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336$$

4.1 Permutación lineal simple

Una permutación lineal es un ordenamiento de todos los elementos de un conjunto en línea recta. La palabra “lineal” indica que hay un primer lugar, un segundo lugar, un tercero, etc.

¿De cuántas maneras se pueden ordenar $n$ objetos distintos en $n$ lugares?

Imagina que tienes $n$ casillas vacías.

• En la primera casilla puedes colocar cualquiera de los $n$ objetos.
• En la segunda casilla, como ya usaste uno, quedan $n-1$ objetos.
• En la tercera, quedan $n-2$.
• Así sucesivamente hasta la última casilla, donde queda 1 objeto.

Por el principio de multiplicación:

$$n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!$$

Por lo tanto:

$$P_n = n!$$

Ejemplo breve

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

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

Hay 24 maneras.

4.2 Permutación con elementos repetidos

Cuando entre los $n$ elementos hay algunos que son iguales entre sí, se deben eliminar los ordenamientos repetidos.

Supongamos que se ordenan $n$ objetos de los cuales $n_1$ son iguales entre sí, $n_2$ son iguales entre sí, y así sucesivamente. El número de permutaciones distinguibles es:

$$P_{n}^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$$

¿De dónde sale la fórmula?

Si los objetos repetidos fueran distinguibles, tendríamos $n!$ ordenamientos. Pero como los $n_1$ objetos iguales pueden permutarse entre sí de $n_1!$ maneras sin que el ordenamiento visible cambie, al resultado $n!$ hay que dividirlo entre $n_1!$. Lo mismo se hace con cada grupo de repetidos.

Ejemplo breve

¿Cuántas permutaciones distintas se pueden formar con las letras de la palabra $CASA$?

La palabra tiene 4 letras: $C, A, S, A$. La letra $A$ se repite 2 veces. Entonces:

$$P_{4}^{2} = \frac{4!}{2!} = \frac{24}{2} = 12$$

Hay 12 ordenamientos distintos.

4.3 Permutación circular

Una permutación circular se da cuando los elementos se ubican alrededor de una figura cerrada, generalmente una circunferencia. En estos casos no existe un “primer elemento” ni un “último elemento”; lo que importa es la posición relativa de los elementos entre sí.

Imagina 4 personas alrededor de una mesa circular. Si todas se ponen de pie y se desplazan un asiento en el mismo sentido, la distribución relativa sigue siendo la misma; no se considera un ordenamiento nuevo. Para evitar contar de más, se fija un elemento como referencia y se ordenan los demás en torno a él.

Así, el número de permutaciones circulares de $n$ objetos distintos es:

$$P_n^{\text{circular}} = (n-1)!$$

Ejemplo breve

¿De cuántas maneras se pueden sentar 5 personas alrededor de una mesa circular?

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

Hay 24 maneras.

En los problemas clásicos de asientos alrededor de una mesa, no se divide adicionalmente entre 2 por “efecto espejo”, salvo que el problema indique que la orientación izquierda-derecha no importa. En general, se usa $(n-1)!$.

4.4 Técnica de bloques: elementos que deben ir juntos

Muchos problemas de permutaciones exigen que ciertos elementos permanezcan juntos. La técnica más eficaz consiste en agruparlos en un solo bloque y tratar a ese bloque como una unidad.

Pasos del método de bloques

1. Identifica los elementos que deben ir juntos.
2. Agrúpalos en un bloque; cuenta cuántas unidades hay en total (el bloque cuenta como una sola).
3. Permuta las unidades (lineal o circularmente, según corresponda).
4. Multiplica por las permutaciones internas de cada bloque.

a) Bloques en permutación lineal

Ejemplo breve

Cinco personas $A, B, C, D, E$ se sientan en una fila de 5 asientos, y $A$ con $B$ deben sentarse juntas. ¿De cuántas maneras pueden sentarse?

Formamos el bloque $AB$. Entonces las unidades son:

$$[AB], \ C, \ D, \ E$$

En total, 4 unidades en línea recta:

$$4! = 24$$

Dentro del bloque, $A$ y $B$ pueden permutarse:

$$2! = 2$$

El total es:

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

b) Bloques en permutación circular

Ejemplo breve

Seis personas, entre ellas $A$ y $B$, se sientan alrededor de una mesa circular. ¿De cuántas maneras pueden sentarse si $A$ y $B$ deben estar juntas?

Formamos el bloque $AB$. Las unidades circulares son:

$$[AB], \ C, \ D, \ E, \ F$$

Hay 5 unidades alrededor de la mesa circular:

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

Dentro del bloque:

$$2! = 2$$

Total:

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

c) Bloques múltiples en forma circular

Cuando hay más de un bloque, el procedimiento es el mismo: cada bloque cuenta como una unidad.

En las permutaciones se ordenan todos los elementos. En muchas situaciones, sin embargo, se dispone de un conjunto grande y se desea ordenar solo una parte de sus elementos. En estos casos hablamos de variaciones.

5.1 Variación sin repetición

Si se tienen $n$ elementos distintos y se desea ordenar $r$ de ellos ($r \le n$), sin repetir ninguno, el número de variaciones simples es:

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

Deducción breve

Para la primera posición hay $n$ opciones; para la segunda, $n-1$; para la tercera, $n-2$; así hasta la $r$-ésima posición, para la cual hay $n-r+1$ opciones. Multiplicando:

$$V_n^r = n(n-1)(n-2)\cdots(n-r+1)$$

Esta expresión es equivalente a:

$$\frac{n!}{(n-r)!}$$

Ejemplo breve

¿Cuántos números de 3 cifras distintas se pueden formar con las cifras $1,2,3,4,5$?

Aquí $n=5$, $r=3$:

$$V_5^3 = 5 \times 4 \times 3 = 60$$

Hay 60 números.

Cuando $r=n$, la variación simple se convierte en una permutación:

$$V_n^n = \frac{n!}{0!} = n!$$

5.2 Variación con repetición

Si al ordenar $r$ elementos tomados de $n$ distintos se permite repetir elementos, el número de variaciones con repetición es:

$$VR_n^r = n^r$$

Esto se debe a que para cada una de las $r$ posiciones hay $n$ opciones posibles, sin restricción.

Ejemplo breve

Con las cifras $5,7,9$, ¿cuántos números de 4 cifras se pueden formar si se permite repetir cifras?

$$VR_3^4 = 3^4 = 81$$

Esta idea también resuelve el problema del código de cuatro dígitos que vimos antes: hay 10 opciones por posición y 4 posiciones, luego $10^4$.

En las permutaciones y variaciones, el orden de los elementos importa. Pero hay muchos problemas en los que no importa el orden: formar un grupo, elegir un comité, escoger preguntas de un examen, trazar segmentos, seleccionar helados, etc. En estos casos se usan las combinaciones.

6.1 Combinación simple

Una combinación simple es una selección de $r$ elementos tomados de un total de $n$ elementos distintos, sin importar el orden y sin repetición.

El número de combinaciones se denota:

$$C_n^r \quad \text{o} \quad \binom{n}{r}$$

y se calcula como:

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

¿De dónde sale?

Si primero contamos las variaciones simples $V_n^r$, estamos contando cada selección de $r$ elementos muchas veces: una por cada orden posible de esos $r$ elementos. Como cada grupo de $r$ elementos puede ordenarse de $r!$ maneras, dividimos:

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

Ejemplo breve

¿De cuántas maneras se puede elegir una comisión de 2 personas entre 5 personas?

$$C_5^2 = \frac{5!}{2! \cdot 3!} = \frac{5 \times 4}{2} = 10$$

Hay 10 comisiones posibles.

Si en cambio se pidiera elegir delegado y subdelegado, el orden importaría y se usaría $V_5^2 = 5 \times 4 = 20$. La diferencia entre 20 y 10 es justamente el factor $2!$.

Propiedades básicas muy útiles

• $C_n^0 = 1$
• $C_n^n = 1$
• $C_n^r = C_n^{n-r}$

Por ejemplo, $C_{10}^8 = C_{10}^2 = 45$. Esta propiedad ahorra cálculos cuando $r$ es cercano a $n$.

6.2 Aplicación: segmentos entre puntos

Si en un plano hay $n$ puntos, y no hay más de dos puntos colineales, cada par de puntos determina un segmento. El número de segmentos es:

$$C_n^2 = \frac{n(n-1)}{2}$$

Esto se debe a que un segmento no depende del orden de los dos puntos: el segmento $AB$ es el mismo que $BA$.

6.3 Combinación con repetición

En algunos problemas se eligen $k$ objetos de $n$ tipos distintos, pero se permite repetir el mismo tipo varias veces. Un ejemplo típico es comprar helados: se puede elegir 8 helados de 3 sabores y repetir sabores libremente.

El número de combinaciones con repetición se denota:

$$CR_n^k$$

y se calcula con la fórmula:

$$CR_n^k = C_{n+k-1}^{k} = \frac{(n+k-1)!}{k!(n-1)!}$$

¿De dónde sale la fórmula?

Si hay $n$ tipos de objetos y queremos elegir $k$ objetos en total, representamos la elección con $k$ bolitas idénticas y $n-1$ separadores.

Cada distribución de las bolitas entre los separadores representa una compra. El número total de símbolos es $n+k-1$; elegimos $k$ posiciones para las bolitas (o, equivalentemente, $n-1$ posiciones para los separadores). Por eso:

$$CR_n^k = C_{n+k-1}^{k}$$

Ejemplo breve

¿Cuántas opciones diferentes hay de comprar 8 helados de 3 sabores?

Aquí $n=3$, $k=8$:

$$CR_3^8 = C_{3+8-1}^{8} = C_{10}^8 = C_{10}^2 = 45$$

Hay 45 opciones.