COMBINATORIA

En esta nueva entrada de nuestro blog, queremos exponer un breve repaso de conceptos básicos de combinatoria, que nos ayudarán a entender algunos de los problemas correspondientes al Tema 1 del libro Kurose & Ross.

• PERMUTACIONES DE n ELEMENTOS:

Las permutaciones nos permiten ordenar números, pudiendo responder a preguntas como: ¿Cuántos números de n cifras podemos obtener reordenando la posición de n dígitos distintos?

Como podemos ver en esta imagen, el número de combinaciones posibles viene dado por la operación n factorial, siendo n el número de cifras disponibles:

  

• PERMUTACIONES CON CIFRAS QUE SE PUEDEN REPETIR:

 En este caso queremos contar el número de combinaciones posibles, teniendo en cuentan que tenemos cifras que se pueden repetir (por ejemplo, disponemos de las cifras 1,1,1,1,1,2,2,2). Para ello, debemos contar como uno todas las posibles combinaciones de los números que se repiten:

- Permutaciones de los 1: 5! (ya que tenemos 5 unos posibles).
- Permutaciones de los 2: 3! (ya que tenemos 3 doses posibles).

Con estos datos, el resultado seria: 8!/(5!3!).

Podemos generalizar esta formula como: n!/(k1!k2!....kp!); teniendo en cuenta que ki es el número de veces que tenemos disponibles cada cifra.

• VARIACIONES CON REPETICIÓN: 

En este apartado, resolveremos preguntas del tipo: ¿Cuántos números de n cifras podemos obtener con k dígitos distintos suponiendo que podemos reutilizarlos?

Por ejemplo: si tenemos las cifras 0 ,1 y tenemos n posiciones, el número total de combinaciones será: 2^n.
Si generalizamos esta expresión para k digitos, obtenemos la expresión: k^n.

• VARIACIONES SIN REPETICIÓN DE ELEMENTOS:

En este apartado suponemos, al contrario que en el anterior, que no podemos reutilizar los dígitos disponibles; respondiendo a preguntas del tipo: ¿Cuántos números de n cifras podemos obtener a partir de k (k>=n) cifras sin poder reutilizarlas?

• COMBINACIONES DE k ELEMENTOS SIN REPETICIONES:

En este caso el orden en el que aparece cada cifra no es importante. Un ejemplo muy ilustrativo es el siguiente problema:
De una baraja de 10 cartas se extraen 3, ¿cuántos tríos distintos se pueden extraer?

- Suponemos que m es el número de elementos totales (en el ejemplo serían las 10 cartas) y n, el número de elementos seleccionados (en el ejemplo, los grupos de 3 cartas):

 - Esta fórmula se conoce como el número combinatorio de m sobre n, de manera que su solución daría respuesta a la pregunta del problema.