Función generatriz de combinaciones y variaciones

Combinaciones sin repetición
Ya vimos en la entrada de presentación de la teoría de las funciones generatrices

(http://hojaynumeros.blogspot.com.es/2013/03/funciones-generatrices-en-combinatoria_14.html)

esta relación

Es el clásico Binomio de Newton y nos da de forma inmediata la función generatriz (F.G.) de las combinaciones de n elementos sin repetición.

Esta forma de expresar los números combinatorios da lugar a demostraciones muy sencillas de algunas de sus propiedades. Observa esta identidad:

Si la desarrollas da lugar a la identidad de Vandermonde

Basta imaginarse cómo sería el producto de las dos potencias

De igual forma, de esta otra identidad

Nos resultaría

Basta con igualar términos con el exponente k

Así se podría demostrar otras similares.

Combinaciones con repetición 

La fórmula del binomio de Newton es válida también para exponente negativo, pero en ese caso los números combinatorios tendrían la forma

Pero la última expresión coincide con las combinaciones con repetición, luego

Sería, teniendo en cuenta los signos, la F.G. de las combinaciones con repetición.

Caso de elementos con repetición prefijada

Este es el caso con el que comenzamos a estudiar las F.G. en una entrada anterior. Si deseamos combinaciones con repetición, pero en las que algunos elementos tienen un máximo en su repetición (no se suele estudiar este caso en los niveles elementales), debemos usar otra técnica. Por ejemplo:

Disponemos de varias fichas en cada una de las cuales se ha dibujado una forma distinta. Por ejemplo esta distribución:

¿De cuántas formas distintas se puede tomar un conjunto de cinco símbolos? Al hablar de conjunto, no tendremos en cuenta el orden.

Basta usar, como ya vimos, un producto de polinomios en los que los exponentes representan las repeticiones posibles de cada símbolo:

F(x)=(1+x+x²)(1+x+x²+x³)(1+x+x²+x³+x⁴)

Buscamos con PARI su coeficiente de grado 5, que representa los elementos seleccionados:

print(polcoeff((x^2+x+1)*(x^3+x^2+x+1)*(x^4+x^3+x^2+x+1),5))

con un resultado de 11 posibilidades

Son estas (con la hoja Cartesius):

Podemos interpretarlas así:

Este método es general: para crear la F.G, en un caso de combinaciones con repeticiones prefijadas basta con formar polinomios de potencias para cada uno de los elementos y después multiplicarlos todos.

Funciones generatrices exponenciales


Hasta ahora hemos manejado combinaciones, no hemos tenido en cuenta el orden. Cuando éste interviene, para abordar las variaciones y permutaciones, necesitamos otro tipo de funciones generatrices, las exponenciales:

Dada una sucesión de números (en general complejos) {a0, a1, a2, a3,…an,….} llamaremos función generatriz exponencial de esa sucesión a la formada por

Es idéntica a la definición general, pero en cada término de la suma dividimos entre el factorial del exponente. La raíz de esta técnica está en el desarrollo del binomio de Newton, en el que podemos sustituir Cm,n por Vm,n/n!

De esta forma, si (1+x)^m era la F.G. de las combinaciones, también será ahora la F.G exponencial de las variaciones. Esta idea no es de mucha utilidad así en general, pero nos será muy útil en lo que sigue.

Variaciones con elementos repetidos

Un caso que no se suele estudiar en las enseñanzas medias es el las variaciones en las que se permite un máximo de repeticiones para cada elemento. Por ejemplo, tomar variaciones de 4 elementos en este conjunto de elementos con repetición: AAABBCDD.

Efectuamos previamente un acercamiento sin F.G.

En la imagen hemos obtenido con Cartesius todas las posibles combinaciones, escribiendo en cada columna el número de veces que se toman A,B,C y D, contando después las distintas ordenaciones de cada una. La suma obtenida fue de 162 variaciones.

Probamos ahora con una F.G. exponencial para cada elemento, hasta 3 para A, 2 para B y D y una para C. Observa que los términos de los polinomios están divididos entre factoriales.

FG=(1+x+x^2/2+x^3/6)(1+x+x^2/2)(1+x)(1+ x+x^2/2)

Desarrollamos esta función con wMaxima

Nos resulta para el exponente 4 un coeficiente de 27/4, pero recordemos que es una F.G. exponencial, luego hay que multiplicar por 4! para encontrar el verdadero coeficiente, el número de variaciones:

27/4*4!=27*6=162, que confirma el resultado previo.

Lo que hemos aprovechado en realidad es que al escribir estos paréntesis cada elemento está representado por los órdenes que puede presentar. Si usamos este factor (1+x+x^2/2+x^3/6) lo que estamos comunicando es que x^2 presenta dos posibles órdenes (que al repetir el símbolo se han perdido) y que x^3 proviene de 6 órdenes (permutaciones con tres elementos)

Quiere decir lo anterior que las contribuciones al coeficiente final de x^4, 27/4, ya vienen descontados los órdenes que se han perdido al repetir. Al final, al multiplicar por el factorial de 4, nos quedamos con los órdenes verdaderos. Es un poco complicado de entender, pero estúdialo, que funciona.

Lo comprobamos para el variaciones de 3 elementos: el coeficiente es 26/3 y si multiplicamos por 3! nos queda 26*2=52

Lo comprobamos con Cartesius

Lo generalizamos sin demostración:

Para encontrar el número de variaciones con repetición en el que conocemos el número máximo de repeticiones de un elemento, sean por ejemplo k, aportaremos a la F.G. un factor del tipo 1+x+x2/2!+x3/3!+…+xk/k! por cada elemento.

Permutaciones con repetición

La función generatriz que hemos empleado para variaciones coincide con la de permutaciones si el coeficiente que buscamos coincide con el total de las repeticiones de símbolos. En el ejemplo que estamos usando, AAABBCDD, el total de elementos es 8. Busca en el desarrollo mediante wMaxima de arriba el exponente 8 de la F.G. y verás que es 1/24. Como estamos usando funciones exponenciales, el verdadero valor será (1/24)*8! = 1680.

En este caso no es necesaria la F.G., pues ya sabemos que el número de permutaciones de AAABBCDD se calcula mediante 8!/(3!2!1!2!) =8!/24 = 1680, pero es conveniente comprobar que en este caso también funciona la técnica de las F.G.