6 Estructuras combinatorias

Definition 6.1 (Variacion con repeticion).

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

Denotamos como $VR_{m,k}$ al numero de variaciones con repeticion de $m$ elementos tomados de $k$ en $k$ .

Theorem 6.2.

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

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

Proof 6.3.

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 $k<m$ o $k=m$ o $k>m$ .

Example 6.4.

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 $84\cdot 83\cdot 82$ . Difiere con los ejemplos anteriores al no poder haber repeticiones.

Definition 6.5.

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

Denotamos como $V_{m,k}$ al numero de variaciones de $m$ elementos tomados de $k$ en $k$ .

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

Definition 6.6.

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

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

Se define $0!\coloneqq 1$ .

Theorem 6.7.

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

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

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

Example 6.8.

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

Definition 6.9.

Una permutacion de $m$ elementos $a_{1},a_{2},\ldots,a_{m}$ es una variacion de esos $m$ elementos tomados de $m$ en $m$ .

Denotamos como $P_{m}$ al numero de permutaciones de $m$ elementos.

Theorem 6.10.

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

P_{m}=m!

Proof 6.11.

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

Example 6.12.

Cuantas palabras pueden formarse reordenando las letras de la palabra “murcielago”?

Es una permutacion de 10 elementos: $V_{10,10}=P_{10}=10!$

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

Example 6.13.

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 $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:

\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}.

Definition 6.14.

Una combinacion de $m$ elementos $a_{1},a_{2},\ldots,a_{m}$ tomados de $k$ en $k$ es una coleccion no ordenada formada por $k$ elementos distintos elegidos cada uno de ellos entre $a_{1},a_{2},\ldots,a_{m}$ .

Denotamos como $C_{m,k}$ al numero de combinaciones de $m$ elementos tomados de $k$ en $k$ . Una notacion alternativa para $C_{m,k}$ es $\binom{m}{k}$ (numero combinatorio, se lee $m$ sobre $k$ ).

Theorem 6.15.

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

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

Proof 6.16.

Hay $V_{m,k}=\frac{m!}{(m-k)!}$ variaciones de $m$ elementos tomados de $k$ en $k$

Hay varias variaciones que dan la misma combinacion. ¿Cuantos? $P_{k}=k!$ que son las distintas formas de permutar los $k$ elementos.

Por tanto, el numero de combinaciones

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 $k\leq m$ .

Example 6.17.

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 $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 ( $3!\cdot 2!=12$ ). $3!$ son las formas de permutar las O y $2!$ las formas de permutar las R.

Luego el numero total de palabras que puedo obtener son $\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).

$a_{1}=O(n_{1}=3),a_{2}=R(n_{2}=2),a_{3}=S(n_{3}=1),a_{4}=C(n_{4}=1)$ .

Definition 6.18.

Una permutacion con repeticion de $n$ elementos $a_{1},a_{2},\ldots,a_{m}$ donde cada $a_{i}$ se repite $n_{i}$ veces es una lista ordenada de $n$ elementos elegidos entre $a_{1},a_{2},\ldots,a_{m}$ donde el elemento $a_{i}$ aparece repetido $n_{i}$ veces.

Supongamos que $n_{i}>1$ siempre que $i\leq k$ y que $n_{i}=1$ siempre que $i>k$ . Denotamos como $P^{n_{1},n_{2},\ldots,n_{k}}_{n}$ al numero de permutaciones con repeticion de $n$ elementos donde hay $k$ elementos que se repiten $n_{1},n_{2},\ldots,n_{k}$ veces respectivamente.

Theorem 6.19.

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

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}!}

Proof 6.20.

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

Example 6.21.

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:

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

Como seria el caso general?

Hay $m$ elementos $a_{1},\ldots,a_{m}$ ( $n=3$ ). Hay que elegir $k$ veces pudiendo repetir ( $k=10$ ).

Para el mismo argumento, necesitamos $m-1$ separadores. Habra $k+m-1$ huecos.

De cuantas formas se pueden elegir los huecos de los separadores? $\binom{k+m-1}{m-1}=\binom{k+m-1}{k}$ .

Definition 6.22.

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

Denotamos como $CR_{m,k}$ al numero de combinaciones de elementos tomados de $k$ en $k$ .

Theorem 6.23.

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

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