Números binomiales
Definición: Llamaremos número binomial, o coeficiente binomial, a la expresión \(\binom{n}{k}\), dada por la fórmula: \[{\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}\]
Teorema (Fórmula de Stiefel): Sea \({n\choose 0}={n\choose n}=1,\ \forall n\in\mathbb{Z}^+,\) entonces para todos los números enteros \(n\geq k\geq 0\) es \[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]
Ejercicio: Probar que \({n\choose 1}=n\).
Proposición: \[{n\choose m}=\frac{n!}{m!(n-m)!}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}\]
Ejercicio: Probar que \({n\choose m}={n\choose n-m}\).
Como veremos, los números binomiales serán una herramienta que nos ayudarán en muchos resultados. Por ejemplo, la fórmula de las Permutaciones con Repetición expresada exclusivamente mediante números binomiales es el resultado de descomponer el proceso de ordenación en elecciones sucesivas. Para un conjunto de $n$ elementos donde las frecuencias de los elementos repetidos son $n_1, n_2, \dots, n_r$ (tal que $\sum n_i = n$), la fórmula es:$$PR_{n}^{n_1, n_2, \dots, n_r} = \binom{n}{n_1} \cdot \binom{n – n_1}{n_2} \cdot \binom{n – n_1 – n_2}{n_3} \cdots \binom{n_r}{n_r}$$
Teorema del binomio
Si utilizamos la Fórmula de Stiefel, podemos ver en el El teorema de Pascal.
«TrianguloPascalC» por Drini – Trabajo propio. Disponible bajo la licencia CC BY-SA 3.0 vía Wikimedia Commons.
Con esto hemos sentado las bases para enunciar el Teorema del Binomio:
\[(x+y)^n=\sum_{k=0}^n {n \choose k}x^{n-k} y^k\]
Ejercicio: ¿Cuál es el coeficiente de \(x^6\) en el desarrollo de \((x-2)^{11}\)
Ejercicio: Calcular \[{n\choose 0}+{n\choose 1}+{n\choose 2}+\ldots+{n\choose n}\]
Ejercicio: Calcular \[{n\choose 0}-{n\choose 1}+{n\choose 2}-{n\choose 3}+\ldots+(-1)^n{n\choose n}\]
Ejercicio: ¿Cuánto suman las cifras del resultado de \[\sum_{i=1}^{\frac{17-1}{2}}{17\choose i}\]
Un resultado interesante es el siguiente. Utilizando el teorema del binomio, podemos ver que
\[(1+x)^n=\sum_{k=0}^n {n \choose k}x^{k}\]
Ejercicio: Calcular \[{n\choose 1}+2{n\choose 2}+3{n\choose 3}+\ldots+n{n\choose n}\]
Ejercicio: Determinar, usando el teorema del binomio, la matriz \[\begin{bmatrix}1&2&0\\ 0&1&2\\ 0&0&1\end{bmatrix}^n\]
Coeficientes multinomiales
Podemos extender el teorema del binomio al conocido resultado de la fórmula de Leibniz: Dados \(m\) enteros y un natural \(n\), se tiene
\[(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} \prod_{1\le t\le m}x_{t}^{k_{t}}\]
Aquí definimos los coeficientes multinomiales como \[{n \choose k_1, k_2, \ldots, k_m} =\frac{n!}{k_1!· k_2! \cdots k_m!}\]
donde \(k_1+ k_2+ \ldots+ k_m=n\).
Ejercicio: ¿Cuál es el coeficiente de \(x^3y^4z^2\) en el desarrollo de \((x+y+3z)^9\).
Combinaciones
Si anteriormente tratábamos de contar las aplicaciones entre dos conjuntos, ahora veamos cómo contar los posibles subconjuntos formados con los elementos de un conjunto.
Sabemos que dado un conjunto finito \(A\) con cardinal \(|A|=n\) entonces
\(|\wp(A)|=2^n\)
Pero, ¿cuántos subconjuntos de un determinado número de elementos, \(m\leq n\), podemos tener? Veámoslo.
Sea \(A=\{a,b\}\), entonces los subconjuntos pueden ser de 1 elemento: \(\{a\},\{b\}\); o de dos elementos, \(\{a,b\}\). Observar que, como conjunto, \(\{a,b\}=\{b,a\}\), pues \(\{a,b\}\subseteq\{b,a\}\) y \(\{b,a\}\subseteq\{a,b\}\). Ved que \[\wp(A)=\{\varnothing, \{a\},\{b\},\{a,b\}\}\] que verifica el resultado anterior.
Sea \(A=\{a,b,c\}\), entonces los subconjuntos pueden ser de 1 elemento: \(\{a\},\{b\},\{c\}\); o de dos elementos, \(\{a,b\},\{a,c\},\{b,c\}\); o de tres elementos \(\{a,b,c\}\). De nuevo se cumple que \(|\wp(A)|=8\) que verifica el resultado anterior.
Ejercicio: ¿Cuántos subconjuntos de 2 elementos podemos hacer con los elementos del conjunto \(A=\{a,b,c,d\}\)
Definición: Definimos las combinaciones de \(n\) elementos tomados de \(m\) en \(m\), como los subconjuntos de \(m\) elementos de un conjunto de \(n\) elementos, \[C_{n,m}=\frac{V_{n,m}}{P_m}\]
Es decir, las variaciones donde no importa el orden que elijamos los elementos. De este modo, ese número será \[C_{n,m}=\frac{V_{n,m}}{P_m}=\frac{n!}{m!\,(n-m)!}\]
Ahora podemos identificar los números binomiales con las combinaciones:
\[C_{n,m}={n \choose m}\]
Ejercicio: De un grupo de veinticinco libros distintos queremos escoger tres para leer durante las vacaciones. ¿De cuántas maneras podemos hacer esto?
Ejercicio: En una clase de 10 alumnos van a distribuirse 4 premios iguales, de manera que un alumno no pueda recibir dos premios. ¿De cuántos modos pueden distribuirse?
Combinaciones con repetición
Definición: Llamamos combinaciones con repetición de un conjunto a las distintas formas en que se puede hacer una selección de elementos del conjunto dado, permitiendo que las selecciones puedan repetirse.
Veamos un ejemplo. Vamos a elegir un número determinado de objetos entre varios conjuntos de objetos. Por ejemplo, tenemos limones, naranjas y peras suficientes para repartir una pieza a cada uno de nuestros once alumnos. ¿De cuántas formas podríamos hacerlo? De nuevo, esta manera de repartir, en la que, como se aprecia, podemos repetir alguno de los objetos, es equivalente a lo que denominamos combinaciones con repetición.
Teorema: \[CR_{n,m}=C_{n+m-1,m}\]
Ejercicio: Un banco ofrece un regalo a elegir entre 5 posibles regalos por cada cartilla. Un señor que tiene tres cuentas corrientes en dicho banco, ¿de cuántas formas puede elegir el lote de tres obsequios si no le importan repetir regalos?
Ejercicio: En una clase de 10 alumnos van a distribuirse 3 premios iguales, de manera que un alumno puede recibir más de uno. ¿De cuántos modos pueden distribuirse?
En las combinaciones con repetición es independiente que \(n<m\) o \(m<n\).
El resultado \(CR_{n,m}=C_{n+m-1,m}\) nos permite introducir los coeficientes \(\left(\!{n \choose m}\!\right)\), que hacen referencia a las combinaciones con repetición:\[\left(\!\!\!{n \choose m}\!\!\!\right)={n+m-1 \choose m}\]
Esto nos da pie a deducir que el número de coeficientes multinomiales de la fórmula de Leibniz es
\[{n+m-1 \choose m-1}\] que es coincidente con \[{n+m-1 \choose m-1}=\left(\!\!\!{m \choose n}\!\!\!\right)={m+n-1 \choose n},\] ya que se corresponde con todos los posibles monomios \(x_1^{k_1} \cdot x_2^{k_2} \cdots x_m^{k_m}\) del desarrollo de \((x_1 +x_2+\ldots +x_m)^n\).
Soluciones enteras de una ecuación.
Teorema: Sean \(k,n\in\mathbb{N}\). El número de soluciones enteras no negativas(es decir, \(x_i\geq 0 \)) de la ecuación \[x_1+x_2+\ldots+x_m=n\] es \[CR_{m,n}=C_{m+n-1,n}\]
Observar que esto es equivalente a expresar \(n\) en, como mucho, \(m\) sumandos. Por ejemplo, 4 expresado en 3 sumandos será:
\[\begin{align}
4&=4+0+0\\
4&=0+4+0\\
4&=0+0+4\\
4&=3+1+0\\
4&=1+3+0\\
4&=0+3+1\\
4&=0+1+3\\
4&=3+0+1\\
4&=1+0+3\\
4&=2+2+0\\
4&=2+0+2\\
4&=0+2+2\\
4&=1+1+2\\
4&=1+2+1\\
4&=2+1+1
\end{align}\]
Que, como vemos, resultan \(CR_{3,4}=15\) expresiones.
Si consideramos que \(x_i>0\), entonces el número de soluciones enteras de la ecuación \[x_1+ x_2+ \ldots+ x_m=n,\] siendo \(n>m\) es \[{n-1 \choose m-1}\]
Además, si consideramos \(x_1 = x_2 = \cdots = x_m=1\), en tal caso, la suma de los coeficientes multinomiales de la fórmula de Leibniz es\[\sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m}=m^n\]
| Ejercicio: Hay que colocar a 5 hombres y 4 mujeres en una fila de modo que las mujeres ocupen los lugares pares. ¿De cuántas maneras puede hacerse? |