Sabemos que \[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]
Ejercicio: Crear una función recursiva que nos permita calcular \[\binom{n}{k}\]
Ejercicio: Utlizando $$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}$$ crear una función que nos calcule $PR_{n}^{n_1, n_2, \dots, n_r}$
Ejercicio: Utilizando la función recursiva creada para los números binomiales, calcula la suma de los coeficientes impares del desarrollo de \((x+y)^{21}\). Es decir, \[\sum_{i=0}^{\left\lfloor \frac{21}{2}\right\rfloor}\binom{21}{2i+1}\]
Las combinaciones con repetición admiten una fórmula recursiva: para todos enteros positivos \(0<n\) y \(0\leq m\), es \[CR_{n,m}=CR_{n-1,m}+CR_{n,m-1}, \] siendo \(CR_{1,m}=1\) y \(CR_{n,1}=n\). Así \[\left(\!\!\!{n \choose m}\!\!\!\right)=\left(\!\!\!{n-1 \choose m}\!\!\!\right)+\left(\!\!\!{n \choose m-1}\!\!\!\right)\]
Ejercicio: Utilizando el procedimiento recursivo anterior, crea una función que nos permita calcular cuánto es \(\left(\!\!{5 \choose 3}\!\!\right)\)
Construcción de las combinaciones
Hasta ahora hemos construido funciones que nos determinan el valor de las variaciones, permutaciones y combinaciones.
Supongamos que deseamos construir todos los posibles subconjuntos de dos elementos de un conjunto finito; es decir, las combinaciones de \(n\) elementos tomados de dos en dos. La forma más sencilla sería mediante
\[\begin{array}{l} \mathrm{Sea }\,A=\{x_1,x_2,\ldots,x_n\};\\ \mathbf{for}\, i=1\, \mathbf{thru}\, n-1 \,\mathbf{do}(\\ \qquad \mathbf{for }\, j=i+1\, \mathbf{thru}\, n \,\mathbf{do}( \\ \qquad\qquad\{x_i,x_j\}\\ \qquad )\\ )\end{array} \]
¿Cómo podríamos construir las variaciones? ¿Y las permutaciones?
| Ejercicio: En una reunión de 10 personas debe nombrarse una comisión formada por tres de ellas. ¿Cuántas comisiones distintas podrían nombrarse? |