6 Estructuras combinatorias

Definición 6.1 (Variacion con repeticion).

Una variacion con repeticion de $\displaystyle m$ elementos $\displaystyle a_{1},a_{2},\ldots,a_{m}$ tomados de $\displaystyle k$ en $\displaystyle k$ es una lista ordenada formada por $\displaystyle k$ elementos (que pueden estar repetidos) elegidos cada uno de ellos entre $\displaystyle a_{1},a_{2},\ldots,a_{m}$ . Denotamos como $\displaystyle VR_{m,k}$ al numero de variaciones con repeticion de $\displaystyle m$ elementos tomados de $\displaystyle k$ en $\displaystyle k$ .

Teorema 6.1.

Sean $\displaystyle m,k\in\mathbb{N}$ . Entonces

\displaystyle VR_{m,k}=m^{k}.

Demostración.

Aplicacion inmediata de la regla del producto. ∎

En las variaciones con repeticion importa el orden de los elementos, puede haber elementos repetidos y es posible $\displaystyle k<m$ o $\displaystyle k=m$ o $\displaystyle k>m$ .

Ejemplo.

En una prueba de maraton participan 84 corredores. Se otorga una medalla de oro al primero, una de plata al segundo y una de bronce al tercero. De cuantas formas diferentes pueden quedar repartidas las medallas entre los 84 participantes? Para el oro, tenemos 84 opciones. Para la plata, hay 83 opciones al no poder repetirse. Para el bronce, hay 82. Por tanto, la solucion sera $\displaystyle 84\cdot 83\cdot 82$ . Difiere con los ejemplos anteriores al no poder haber repeticiones.

Definición 6.2.

Una variacion de $\displaystyle m$ elementos $\displaystyle a_{1},a_{2},\ldots,a_{m}$ tomados de $\displaystyle k$ en $\displaystyle k$ es una lista ordenada formada por $\displaystyle k$ elementos distintos elegidos cada uno de ellos entre $\displaystyle a_{1},a_{2},\ldots,a_{m}$ . Denotamos como $\displaystyle V_{m,k}$ al numero de variaciones de $\displaystyle m$ elementos tomados de $\displaystyle k$ en $\displaystyle k$ .

\displaystyle V_{m,k}=\prod\limits_{j=m-k+1}^{n}j

Definición 6.3.

Sea $\displaystyle n\in\mathbb{N}$ . Se define el factorial de $\displaystyle n$ como

\displaystyle n!\coloneqq\prod\limits_{j=1}^{n}j=n\cdot(n-1)\cdot(n-2)\cdots 3% \cdot 2\cdot 1.

Se define $\displaystyle 0!\coloneqq 1$ .

Teorema 6.2.

Sean $\displaystyle m,k\in\mathbb{N}$ tales que $\displaystyle k\leq m$ . Entonces $\displaystyle V_{m,k}$ se puede expresar utilizando factoriales:

\displaystyle V_{m,k}=\frac{m!}{(m-k)!}

Las variaciones se caracterizan porque importa el orden de los elementos, los elementos son distintos y necesariamente $\displaystyle k\leq m$ .

Ejemplo.

En el problema del maraton quiero decir la clasificacion completa. Es una variacion de 84 elementos tomados de 84 en 84: $\displaystyle V_{84,84}=\frac{84!}{(84-84)!}=\frac{84!}{0!}=\frac{84!}{1}=84!$ .

Definición 6.4.

Una permutacion de $\displaystyle m$ elementos $\displaystyle a_{1},a_{2},\ldots,a_{m}$ es una variacion de esos $\displaystyle m$ elementos tomados de $\displaystyle m$ en $\displaystyle m$ . Denotamos como $\displaystyle P_{m}$ al numero de permutaciones de $\displaystyle m$ elementos.

Teorema 6.3.

Sea $\displaystyle m\in\mathbb{N}$ . Entonces:

\displaystyle P_{m}=m!

Demostración.

Es el resultado que se obtiene viendo una permutacion como una variacion. ∎

Ejemplo.

Cuantas palabras pueden formarse reordenando las letras de la palabra “murcielago”? Es una permutacion de 10 elementos: $\displaystyle V_{10,10}=P_{10}=10!$

En las permutaciones importa el orden de los elementos, los elementos son distintos, son ordenaciones de $\displaystyle m$ elementos y es un caso particular de variacion con $\displaystyle m=k$ : intervienen todos los elementos.

Ejemplo.

La loteria primitiva es un sorteo en el que se usan todos los numeros consecutivos del 1 al 49. Una apuesta consiste en marcar 6 de esos 49 numeros en un boleto. Cuantas apuestas diferentes existen en la loteria primitiva? Si lo hago como una variacion, varias opciones iguales con diferente orden se consideran distintas. Cada saco de $\displaystyle 6!$ da una sola apuesta. El numero total de apuestas es el numero total de variaciones dividido entre el numero de variaciones que dan lugar a la misma apuesta:

\displaystyle\frac{49\cdot 48\cdot 47\cdot 46\cdot 45\cdot 44}{6!}=\frac{V_{49% ,6}}{P_{6}}=\frac{\frac{49!}{43!}}{6!}=\frac{49!}{43!6!}=\binom{49}{6}.

Definición 6.5.

Una combinacion de $\displaystyle m$ elementos $\displaystyle a_{1},a_{2},\ldots,a_{m}$ tomados de $\displaystyle k$ en $\displaystyle k$ es una coleccion no ordenada formada por $\displaystyle k$ elementos distintos elegidos cada uno de ellos entre $\displaystyle a_{1},a_{2},\ldots,a_{m}$ . Denotamos como $\displaystyle C_{m,k}$ al numero de combinaciones de $\displaystyle m$ elementos tomados de $\displaystyle k$ en $\displaystyle k$ . Una notacion alternativa para $\displaystyle C_{m,k}$ es $\displaystyle\binom{m}{k}$ (numero combinatorio, se lee $\displaystyle m$ sobre $\displaystyle k$ ).

Teorema 6.4.

Sean $\displaystyle m,k\in\mathbb{N}$ tales que $\displaystyle k\leq m$ . Entonces

\displaystyle C_{m,k}=\frac{m!}{k!\cdot(m-k)!}

Demostración.

Hay $\displaystyle V_{m,k}=\frac{m!}{(m-k)!}$ variaciones de $\displaystyle m$ elementos tomados de $\displaystyle k$ en $\displaystyle k$ Hay varias variaciones que dan la misma combinacion. ¿Cuantos? $\displaystyle P_{k}=k!$ que son las distintas formas de permutar los $\displaystyle k$ elementos. Por tanto, el numero de combinaciones

\displaystyle C_{k,m}=\frac{V_{m,k}}{P_{k}}=\frac{m!}{(m-k)!\cdot k!}

∎

En las combinaciones, no importa el orden de los elementos, los elementos son distintos y necesariamente $\displaystyle k\leq m$ .

Ejemplo.

Cuantas palabras pueden formarse reordenando las letras de la palabra “SOCORRO”? No se puede contar como una variacion porque se puede reordenar de forma distinta y de lugar a la misma palabra. Para contar contar, vamos a pensar temporalmente que las letras son las 7 distintas. Ahora puedo considerar las permutaciones de estos 7 simbolos distintos: son $\displaystyle 7!$ . Por ejemplo, cuantas veces va a salir SOOCORR contando como permutaciones de 7 elementos distintos? En este caso, son 12 posibilidades porque hay 3 O y 2 R ( $\displaystyle 3!\cdot 2!=12$ ). $\displaystyle 3!$ son las formas de permutar las O y $\displaystyle 2!$ las formas de permutar las R. Luego el numero total de palabras que puedo obtener son $\displaystyle\frac{7!}{3!2!}=P^{3,2}_{7}$ (visto en la siguiente definicion). Los parametros son el numero total de simbolos y el numero de repeticiones de cada uno (3,2,1,1). $\displaystyle a_{1}=O(n_{1}=3),a_{2}=R(n_{2}=2),a_{3}=S(n_{3}=1),a_{4}=C(n_{4}% =1)$ .

Definición 6.6.

Una permutacion con repeticion de $\displaystyle n$ elementos $\displaystyle a_{1},a_{2},\ldots,a_{m}$ donde cada $\displaystyle a_{i}$ se repite $\displaystyle n_{i}$ veces es una lista ordenada de $\displaystyle n$ elementos elegidos entre $\displaystyle a_{1},a_{2},\ldots,a_{m}$ donde el elemento $\displaystyle a_{i}$ aparece repetido $\displaystyle n_{i}$ veces. Supongamos que $\displaystyle n_{i}>1$ siempre que $\displaystyle i\leq k$ y que $\displaystyle n_{i}=1$ siempre que $\displaystyle i>k$ . Denotamos como $\displaystyle P^{n_{1},n_{2},\ldots,n_{k}}_{n}$ al numero de permutaciones con repeticion de $\displaystyle n$ elementos donde hay $\displaystyle k$ elementos que se repiten $\displaystyle n_{1},n_{2},\ldots,n_{k}$ veces respectivamente.

Teorema 6.5.

Sea $\displaystyle n,n_{1},n_{2},\ldots,n_{k}\in\mathbb{N}$ tales que $\displaystyle\sum_{i=1}^{k}n_{i}\leq n$ . Entonces

\displaystyle P^{n_{1},n_{2},\ldots,n_{k}}_{n}=\frac{n!}{\prod_{i=1}^{k}n_{i}!% }=\frac{n!}{n_{1}!\cdot n_{2}!\cdots n_{k}!}

Demostración.

Extrapolar las ideas del ejemplo que hemos visto. No lo escribimos. ∎

Ejemplo.

De combinaciones con repeticion. Sabemos que la seleccion olimpica española ha obtenido un resultado final de 10 medallas en los ultimos juegos. De cuantas formas pueden estar distribuidas esas medallas entre oro, plata y bronce? Genero 12 huecos (10 para medallas y 2 para separadores que van a separar las medallas de oro de las de plata y las de plata de las de bronce). Dos hechos:

1.

Hay el mismo numero de medallas posibles que de estructuras con separadores.
2.

La estructura queda totalmente determinada si se conoce la posicion de los dos separadores.

De cuantas formas diferentes puedo poner los separadores? Como tengo que elegir los dos huecos para los dos separadores de entre 12 posibles y no importa el orden en el que lo haga:

\displaystyle C_{12,2}=\binom{12}{2}=\frac{12!}{2!10!}=\frac{12\cdot 11}{2}

Como seria el caso general? Hay $\displaystyle m$ elementos $\displaystyle a_{1},\ldots,a_{m}$ ( $\displaystyle n=3$ ). Hay que elegir $\displaystyle k$ veces pudiendo repetir ( $\displaystyle k=10$ ). Para el mismo argumento, necesitamos $\displaystyle m-1$ separadores. Habra $\displaystyle k+m-1$ huecos. De cuantas formas se pueden elegir los huecos de los separadores? $\displaystyle\binom{k+m-1}{m-1}=\binom{k+m-1}{k}$ .

Definición 6.7.

Una combinacion con repeticion de $\displaystyle m$ elementos $\displaystyle a_{1},\ldots,a_{m}$ tomados de $\displaystyle k$ en $\displaystyle k$ es una coleccion no ordenada formada por $\displaystyle k$ elementos (que pueden estar repetidos) elegidos cada uno de ellos entre $\displaystyle a_{1},\ldots,a_{m}$ . Denotamos como $\displaystyle CR_{m,k}$ al numero de combinaciones de elementos tomados de $\displaystyle k$ en $\displaystyle k$ .

Teorema 6.6.

Sean $\displaystyle m,k\in\mathbb{N}$ . Entonces

\displaystyle CR_{m,k}=\binom{m+k-1}{m-1}=\frac{(m+k-1)!}{(m-1)!\cdot k!}.