Combinaciones
En los anteriores posts hemos estado viendo cómo contar determinados conjuntos y varias técnicas para hacerlo. Ahora lo que vamos a hacer es plantearnos el problema de cómo podemos contar los elementos de un subconjunto cualquiera de un conjunto finito. Es decir, si tenemos un conjunto finito de $n$ elementos, ¿cuántos subconjuntos suyos hay que tengan $k\leq n$ elementos?
Un posible símil que podemos establecer es el siguiente: si tenemos $n$ personas, ¿de cuántas formas distintas podemos agrupar $k$ de ellas? En efecto, el conjunto de $n$ elementos es el conjunto de personas, y habrá tantos subconjuntos de $k$ elementos como formas de elegir $k$ personas distintas del grupo. Además este ejemplo nos viene muy bien para hacer algunas observaciones fácilmente. Por ejemplo: por cada grupo de $k$ personas que podemos formar, el resto de personas que no quedan en el grupo $(n-k)$ forman otro grupo (distinto), y de hecho esta es una correspondencia biunívoca, es decir, cada grupo de $k$ personas tiene asociado otro de $n-k$ formado por las personas no elegidas, y por tanto habrá tantos grupos de $k$ como grupos de $n-k.$ Es decir, hay tantos subconjuntos de $k$ elementos como subconjuntos de $n-k$ elementos.
Otra observación fácil de hacer es si $k=1$ entonces estamos agrupando subconjuntos de $1$ elemento y por tanto habrá $n$ de ellos (pues hay $n$ elementos distintos). Además según la observación anterior, también habrá $n$ subconjuntos de $n-1$ elementos, pues hay los mismos de $k$ que de $k-1.$
Vamos a intentar deducir cómo hallar los números que estamos buscando en general. Veamos que tenemos $n$ elementos y supongamos que queremos elegir $k$ distintos. Vamos a denotar:$$ \text{Card}\left\lbrace S \subset \left\lbrace 1,2,3, \ ..., n \right\rbrace : \ \text{Card}(S) = k \right\rbrace = \binom{n}{k}.$$Es decir, $\binom{n}{k}$ es el número de subconjuntos de un conjunto de $n$ elementos que tienen $k$ elementos. Para formar un subconjunto de $k$ elementos vamos a ir tomándolos de uno en uno. Para el primero hay $n$ formas de tomarlo. Para el segundo hay $n-1.$ Para el tercero hay $n-2,$ etc. En general para el $i$-ésimo hay $n+1-i$ formas de elegirlo, de manera que para formar un subconjunto de $k$ elementos hay $n\cdot (n-1) \cdot \ ... \ \cdot (n-k+1) = \frac{n!}{(n-k)!}.$ Sin embargo esto nos debería sonar, puesto que este es precisamente el número de funciones inyectivas de $I_k$ en $I_n$ que calculamos hace un tiempo, y de hecho es el número de $k$-listas sin repetición con $n$ elementos. Además si nos fijamos un poco más, es fácil darse cuenta de que hay más $k$-listas de $n$ elementos que subconjuntos de $k$ elementos de un conjunto de $n,$ pues en estos últimos el orden no determina una diferencia entre dos elementos mientras que en las $k$-listas sí. Por tanto algo hemos hecho mal. Si revisamos el razonamiento que hemos hecho podemos fijarnos en que esta última observación es lo único que debemos añadir al proceso. Por cada subconjunto de $k$ elementos podemos hacer varias $k$-listas distintas: tantas como permutaciones de los elementos del subconjunto. El razonamiento se hace mejor visualmente si se ordenan los elementos del subconjunto y se consideran las permutaciones: $$\left\lbrace a_1,a_2,a_3, \ ..., a_k \right\rbrace = \left\lbrace a_{i_1},a_{i_2},a_{i_3}, \ ..., a_{i_k} \right\rbrace, \ \ a_{i_j}<a_{i_{j+1}} \ \ \forall j : \ 1<j<k.$$Es decir, por ejemplo:$$ \left\lbrace 4,2,7,1 \right\rbrace = \left\lbrace 1,2,4,7 \right\rbrace $$y ahora consideramos todas las posibles permutaciones de los números $1,2,4$ y $7,$ que son $4!.$ En general habrá $k!$ permutaciones, que serán las distintas maneras de ordenar los elementos del subconjunto para conseguir las listas.
Por tanto la única modificación que es necesaria hacer a nuestra fórmula es eliminar las $k!$ $k$-listas por cada subconjunto de $k$ elementos. Por tanto llegamos a que:$$\binom{n}{k} = \frac{n!}{k! (n-k)!}.$$Estos números tienen un nombre: números combinatorios. Son ampliamente conocidos y de hecho muy curiosos, ya que aparecen en gran cantidad de razonamientos y cumplen propiedades muy aparentemente extrañas. De entre ellas vamos a señalar algunas de las más importantes.
La primera es que pueden ordenarse de manera piramidal (una pirámide infinita) en lo que se conoce como "Triángulo de Pascal" o "Triángulo de Tartaglia". Empezamos considerando el número combinatorio $\binom{0}{0}.$ Bajo él situamos los números $\binom{1}{0}$ y $\binom{1}{1}.$ La manera de continuar construyendo la pirámide es de manera similar a éste último paso. Debajo del $\binom{m}{0}$ ya la izquierda situamos el $\binom{m+1}{0},$ y vamos rellenando la fila con los $\binom{m+1}{l}$ donde $l$ recorre $0,1,2, \ ..., m,m+1.$ El resultado es algo así:
Además los números combinatorios satisfacen la recurrencia: $$ \binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}$$y visualmente esto equivale a que la suma de dos números combinatorios consecutivos (en cada fila) del triángulo resulta en el número situado debajo y entre ambos. Por tanto podemos calcular rápidamente muchos números combinatorios utilizando el triángulo:
Otra propiedad interesante que se deduce de la primera observación que realizamos es que $\binom{n}{k} = \binom{n}{n-k}.$ Por último, vamos a ver por qué los números combinatorios también se llaman "coeficientes binomiales". Si intentamos desarrollar la potencia $(x+y)^n:$ $$\begin{align*} (x+y)^n &= (x+y)\cdot (x+y) \cdot \ ... \ \cdot (x+y) = \\ &= a_{n,0} \cdot x^n + a_{n-1,1} \cdot x^{n-1}y + ... + a_{1,n-1} \cdot xy^{n-1}+a_{0,n} \cdot y^n. \end{align*}$$Ahora, para calcular los coeficientes: $a_{n,0}$ se obtendrá de multiplicar $x$ consigo mismo $n$ veces, que lo podemos hacer únicamente si de cada factor tomamos $x,$ es decir, de una manera, luego $a_{n,0}=1.$ Para obtener $a_{n-1,1}$ tendremos que tomar $n-1$ $x$'s y una $y$ de dentro de los factores, de manera que habrá tantas formas de hacerlo como subconjuntos de $n-1$ elementos en un conjunto de $n$ (porque en realidad con determinar cuántas $x$'s tomamos nos vale, ya que el resto de elementos los tomaremos $y$'s). En general, para el coeficiente $a_{i,n-i}$ tendremos que elegir $i$ factores de los que tomamos las $x$'s, luego habrá tantas formas de hacerlo como subconjuntos de $i$ elementos en un conjunto de $n$ ($i$ factores de los $n$ totales). De esta manera: $$(x+y)^n = \sum_{i=0}^n \binom{n}{i} x^{n-i} y^{i}=\sum_{i=0}^n \binom{n}{i} x^{i} y^{n-i}.$$
Vamos a intentar deducir cómo hallar los números que estamos buscando en general. Veamos que tenemos $n$ elementos y supongamos que queremos elegir $k$ distintos. Vamos a denotar:$$ \text{Card}\left\lbrace S \subset \left\lbrace 1,2,3, \ ..., n \right\rbrace : \ \text{Card}(S) = k \right\rbrace = \binom{n}{k}.$$Es decir, $\binom{n}{k}$ es el número de subconjuntos de un conjunto de $n$ elementos que tienen $k$ elementos. Para formar un subconjunto de $k$ elementos vamos a ir tomándolos de uno en uno. Para el primero hay $n$ formas de tomarlo. Para el segundo hay $n-1.$ Para el tercero hay $n-2,$ etc. En general para el $i$-ésimo hay $n+1-i$ formas de elegirlo, de manera que para formar un subconjunto de $k$ elementos hay $n\cdot (n-1) \cdot \ ... \ \cdot (n-k+1) = \frac{n!}{(n-k)!}.$ Sin embargo esto nos debería sonar, puesto que este es precisamente el número de funciones inyectivas de $I_k$ en $I_n$ que calculamos hace un tiempo, y de hecho es el número de $k$-listas sin repetición con $n$ elementos. Además si nos fijamos un poco más, es fácil darse cuenta de que hay más $k$-listas de $n$ elementos que subconjuntos de $k$ elementos de un conjunto de $n,$ pues en estos últimos el orden no determina una diferencia entre dos elementos mientras que en las $k$-listas sí. Por tanto algo hemos hecho mal. Si revisamos el razonamiento que hemos hecho podemos fijarnos en que esta última observación es lo único que debemos añadir al proceso. Por cada subconjunto de $k$ elementos podemos hacer varias $k$-listas distintas: tantas como permutaciones de los elementos del subconjunto. El razonamiento se hace mejor visualmente si se ordenan los elementos del subconjunto y se consideran las permutaciones: $$\left\lbrace a_1,a_2,a_3, \ ..., a_k \right\rbrace = \left\lbrace a_{i_1},a_{i_2},a_{i_3}, \ ..., a_{i_k} \right\rbrace, \ \ a_{i_j}<a_{i_{j+1}} \ \ \forall j : \ 1<j<k.$$Es decir, por ejemplo:$$ \left\lbrace 4,2,7,1 \right\rbrace = \left\lbrace 1,2,4,7 \right\rbrace $$y ahora consideramos todas las posibles permutaciones de los números $1,2,4$ y $7,$ que son $4!.$ En general habrá $k!$ permutaciones, que serán las distintas maneras de ordenar los elementos del subconjunto para conseguir las listas.
Por tanto la única modificación que es necesaria hacer a nuestra fórmula es eliminar las $k!$ $k$-listas por cada subconjunto de $k$ elementos. Por tanto llegamos a que:$$\binom{n}{k} = \frac{n!}{k! (n-k)!}.$$Estos números tienen un nombre: números combinatorios. Son ampliamente conocidos y de hecho muy curiosos, ya que aparecen en gran cantidad de razonamientos y cumplen propiedades muy aparentemente extrañas. De entre ellas vamos a señalar algunas de las más importantes.
La primera es que pueden ordenarse de manera piramidal (una pirámide infinita) en lo que se conoce como "Triángulo de Pascal" o "Triángulo de Tartaglia". Empezamos considerando el número combinatorio $\binom{0}{0}.$ Bajo él situamos los números $\binom{1}{0}$ y $\binom{1}{1}.$ La manera de continuar construyendo la pirámide es de manera similar a éste último paso. Debajo del $\binom{m}{0}$ ya la izquierda situamos el $\binom{m+1}{0},$ y vamos rellenando la fila con los $\binom{m+1}{l}$ donde $l$ recorre $0,1,2, \ ..., m,m+1.$ El resultado es algo así:
Además los números combinatorios satisfacen la recurrencia: $$ \binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}$$y visualmente esto equivale a que la suma de dos números combinatorios consecutivos (en cada fila) del triángulo resulta en el número situado debajo y entre ambos. Por tanto podemos calcular rápidamente muchos números combinatorios utilizando el triángulo:
Otra propiedad interesante que se deduce de la primera observación que realizamos es que $\binom{n}{k} = \binom{n}{n-k}.$ Por último, vamos a ver por qué los números combinatorios también se llaman "coeficientes binomiales". Si intentamos desarrollar la potencia $(x+y)^n:$ $$\begin{align*} (x+y)^n &= (x+y)\cdot (x+y) \cdot \ ... \ \cdot (x+y) = \\ &= a_{n,0} \cdot x^n + a_{n-1,1} \cdot x^{n-1}y + ... + a_{1,n-1} \cdot xy^{n-1}+a_{0,n} \cdot y^n. \end{align*}$$Ahora, para calcular los coeficientes: $a_{n,0}$ se obtendrá de multiplicar $x$ consigo mismo $n$ veces, que lo podemos hacer únicamente si de cada factor tomamos $x,$ es decir, de una manera, luego $a_{n,0}=1.$ Para obtener $a_{n-1,1}$ tendremos que tomar $n-1$ $x$'s y una $y$ de dentro de los factores, de manera que habrá tantas formas de hacerlo como subconjuntos de $n-1$ elementos en un conjunto de $n$ (porque en realidad con determinar cuántas $x$'s tomamos nos vale, ya que el resto de elementos los tomaremos $y$'s). En general, para el coeficiente $a_{i,n-i}$ tendremos que elegir $i$ factores de los que tomamos las $x$'s, luego habrá tantas formas de hacerlo como subconjuntos de $i$ elementos en un conjunto de $n$ ($i$ factores de los $n$ totales). De esta manera: $$(x+y)^n = \sum_{i=0}^n \binom{n}{i} x^{n-i} y^{i}=\sum_{i=0}^n \binom{n}{i} x^{i} y^{n-i}.$$
Comentarios
Publicar un comentario