Combinatoria II

Variaciones

Este caso es muy sencillo, tenemos un conjunto de $n$ elementos y queremos tomar $k$ de ellos ($k< n$, si $k=n$ tenemos una permutación), con la condición de que el orden sea determinante. Para elegir el primero tenemos $n$ opciones, para el segundo $n-1$, para el tercero $n-2$, de aquí observamos que el número de formas para cada elección  es igual al total de elementos ($n$), menos el número de los que han sido elegidos antes de él. Por lo tanto, para seleccionar el $k$-ésimo tenemos $n-(k-1)= n-k+1$, entonces, si llamamos a estas variaciones $V_{n,k}$, por el principio fundamental del contéo tenemos que:

$$V_{n,k}=n(n-1)(n-2)\cdot \cdot \cdot(n-k+1)$$

Dado que estéticamente esta fórmula deja mucho que desear, vamos a simplificarla. Partimos de los productos que aparecen en ella, el último factor es $(n-k+1)$, su entecesor es $(n-k)$ y el producto de este por los enteros positivos menores a él es $(n-k)!$. Si multiplicamos $n(n-1)(n-2)\cdot \cdot \cdot(n-k+1)$ por esta última expresión obtenemos $n!$. Por lo tanto:

$$V_{n,k}=n(n-1)(n-2)\cdot \cdot \cdot(n-k+1)\frac{(n-k)!}{(n-k)!}=\frac{n!}{(n-k)!}$$

Resumiendo:
$$V_{n,k}=\frac{n!}{(n-k)!}$$

Variaciones con repetición

Partimos  nuevamente de $n$ elementos y queremos seleccionar $k$ , como en el caso anterior, importa el orden, pero estos se pueden repetir las veces que queramos, por lo tanto, para el primer elemento tenemos $n$ opciones, y para cada una de las siguientes $k$ elecciones, también. Por lo tanto por el principio fundamental del contéo tenemos que multiplicar $k$ veces $n$. Si denotamos a esta forma como $VR_{n,k}$, entonces:

$$VR_{n,k}=n^{k}$$

Combinaciones 

Ahora de un conjunto de $n$ elementos queremos elegír $k$ ($k< n$) pero sin tomar en cuenta el orden.  Por ejemplo, del siguiente conjunto con cinco elementos:

Tomamos tres de ellos y dado que el orden no importa, las siguientes configuraciones son la misma.

Si extendemos esto al caso general, vemos que si de $n$ elementos elegimos $k$ sin considerar el orden, cualquier configuración nos da al permutarla,  $k!$ formas que resultan ser la misma.
Por lo tanto el total combinaciones (que denotaremos $C_{n,k}$) será igual a todas las formas en que se puede elegir $k$ elementos de $n$  (y que hemos llamado $V_{n,k}$) entre las veces que cada configuración se repite, es decir:
$$C_{n,k}=\frac{V_{n,k}}{k!}=\frac{n!}{(n-k)!k!}$$

Las combinaciones de $k$ elementos tomados de un conjunto de $n$, tambien se representa por medio de $\binom{n}{k}$, por lo tanto:
$$\binom{n}{k}=\frac{n!}{(n-k)!k!}$$

Combinaciones con repetición

Se trata de tomar $k$ elementos sin importar el orden de un conjunto que tiene $n$ distintos pero cada uno se puede repetir las veces que queramos. Para deducir la fórmula analizaremos un ejemplo, del siguiente conjunto:
 

Queremos tomar 4 de ellos, sin importar el orden y con la posibilidad de repetir elementos. Aquí se muestran cuatro posibles formas de hacerlo

Para poder contar todas las formas existentes, vamos a buscar  representarlas de tal manera que podamos utilizar alguna fórmula ya conocida. Una vez tomado cualquier elemento, este puede repetirse hasta tres veces más (pues sólo queremos cuatro), por lo tanto vamos a introducir tres elementos nuevos:

Que nos van a ayudar a indicar con el subíndice la posición del elemento repetido. A continuación se muestran las configuraciones que presentamos y cómo se representan utilizando estos nuevos elementos.

Los subíndices nos dicen que se repite el primero, el segundo y el tercero.

Unicamente se repite el tercer elemento.

Se repite el primero y el tercero

Únicamente se repite el segundo

 Vemos que añadiendo estos tres nuevos elementos al conjunto original:

Podemos realizar las mismas configuraciones, sin repetir elementos y por lo tanto podemos tratar este caso como una combinación simple de ocho elementos tomados de cuatro en cuatro. Si a las combinaciones con repetición de $n$ elementos tomados de $k$ en $k$ la denotamos como $CR_{n,k}$, en este caso:
$$CR_{5,4}=C_{8,4}=\frac{8!}{(8-4)!4!}=70$$

En general, si queremos tomar $k$ objetos de un conjunto de $n$, sin importar el orden y repitiendo cualquiera de ellos, podemos anexar al conjunto original $k-1$ elementos (ya que es la cantidad máxima de repeticiones).  Y las combinaciones con repetición de $n$ elementos tomados de $k$ en $k$, se transforma en una combinación simple de $n+k-1$ objetos tomados de $k$ en $k$:
$$CR_{n,k}=C_{n+k-1,k}=\frac{n+k-1!}{(n+k-1-k)!k!}=\frac{n+k-1!}{(n-1)!k!}$$

Otra forma de deducir esta fórmula es utilizando las permutaciones con repetición, partimos nuevamente de nuestro conjunto de cinco elementos:

Y los separamos mediante barras (el número de barras será, uno menos que el total de elementos), como se muestra en la siguiente figura:

Por convención los elementos  siempre ocuparán el lugar indicado  y para representar las veces que se repiten utilizaremos tantos puntos como elementos queramos tomar, en este caso, cuatro. A continuación se muestran algunos ejemplos de configuraciones posibles en el formato original y en el nuevo de puntos y barras.

Los dos puntos a la izquierda indican dos amarillos y los que se encuentran entre las dos barras primeras  de la izquierda, rojos

Como no hay amarillos ni rojos, sólo tenemos puntos en los espacios correspondientes al azul (uno), al verde (dos) y al magenta (uno).

Los cuatro puntos están en el espacio del color amarillo.

Cualquier configuración posible podemos obtenerla permutando objetos que se pueden repetir (puntos y barras), por lo tanto:
$$CR_{5,4}=P_{8}^{4,4 }=\frac{8!}{4! 4!}=70$$

En general si tenemos $n$ objetos distintos  podemos separarlos con $n-1$ barras, si queremos tomar $k$ de ellos, con la posibilidad de repetición necesitaremos $k$ puntos y el problema se reduce a trabajar con 2 objetos (barras y puntos): queremos buscar de cuántas formas se pueden permutar (con repetición) $n-1$ barras y $k$ puntos (en total $n+k-1$ objetos), por lo tanto:
$$CR_{n,k}=P_{n+k-1}^{n-1,k }=\frac{(n+k-1)!}{(n-1)! k!}$$

Tenemos la misma fórmula que habíamos encontrado antes.

En la siguiente imagen podemos resumir la mayoría de los resultados obtenidos en esta entrada y en Combinatoria I.