Funciones generatrices en Combinatoria

Nota: Esta entrada es la primera de una serie que dedicaremos a las funciones generatrices y a los productos cartesianos condicionados. Aunque estarán enlazadas dentro de una secuencia lógica, para no convertir este blog en un tratado primaveral sobre Combinatoria, las iremos alternando con varias referentes a otros temas, en los que no abandonaremos nuestros queridos números ni a las hojas de cálculo.


Antes de iniciar cualquier planteamiento teórico sobre las funciones generadoras (o generatrices), muy usadas en Combinatoria y en el estudio de las sucesiones de números, las introduciremos mediante un ejemplo. Después, en sucesivas entradas, estudiaremos el concepto con más profundidad. Al principio no se ve bien la utilidad de estas funciones, pero si lees la serie entera que vamos a ir publicando descubrirás que constituyen un buen instrumento de cálculo. Paciencia, pues.

Problema

Deseamos elegir nueve cuentas de colores. Disponemos de cantidad suficiente de cuentas rojas, amarillas y verdes, pero queremos elegir entre 2 y 5 rojas, menos de 4 amarillas y al menos 3 verdes. ¿De cuántas formas podemos efectuar la elección?

Este problema nos plantea el desarrollo de particiones condicionadas de un número.

Ya hemos tocado este tema en el blog (http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html y en
http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html)

Independientemente de que se trate de particiones, intentaremos resolver el problema con varias técnicas, y entre ellas la del uso de una función generatriz.

Con un producto cartesiano

Como de las rojas hemos de elegir entre 2 y 5, de las amarillas de 0 a 3 y de las verdes un mínimo de 3 y un máximo de 7 (¿por qué 7?), bastará formar el producto cartesiano  {2,3,4,5}{0,1,2,3}{3,4,5,6,7} e ir eligiendo las ternas que sumen 9. Un problema totalmente elemental que se puede resolver en enseñanzas medias.

A poco que nos pongamos obtendremos: 9= 2+0+7 = 2+1+6 = 2+2+5 = 2+3+4 = 3+0+6 = 3+1+5 = 3+2+4 = 3+3+3 =4+0+5 = 4+1+4 = 4+2+3 = 5+0+4 = 5+1+3.

En total 13 particiones. Para este problema no se necesitarían más técnicas, pero lo estamos tomando como modelo sencillo de introducción.

Con la hoja de cálculo “Cartesius”, aún en fase beta y que presentaremos más adelante, se pueden construir productos cartesianos condicionados. En el problema que nos ocupa plantearíamos esto, que se comprende sin más explicación:

Y obtendríamos

Como era de esperar, son los mismos resultados. Veamos ahora el método que deseamos explicar hoy.

Función generatriz

La idea revolucionaria de la función generatriz consiste en sustituir los distintos elementos numéricos por potencias de una indeterminada, y los conjuntos convertirlos en polinomios. Así el producto cartesiano {2,3,4,5}{0,1,2,3}{3,4,5,6,7} se puede escribir en forma de producto de polinomios:

Es fácil  darse cuenta de que si multiplicamos algebraicamente estos polinomios, el término de grado 9 tendrá como coeficiente el número de particiones pedido, en este caso 13.

Hemos sustituido una técnica de conteo por otra de tipo algebraico o analítico (esto último lo veremos más adelante)

En este caso tan sencillo parece que esto es una complicación, pero en casos generales veremos que puede resultar muy útil. Por dos motivos:

•  Las técnicas algebraicas y analíticas permiten simplificar estos productos y  encontrar directamente el coeficiente deseado.
•  Al desarrollar estos polinomios no sólo resolvemos el problema para 9 cuentas, sino para cualquier otro total posible.

Disponemos en este caso de una ayuda, y es que sabemos sumar muy bien las progresiones geométricas. Así, el producto de polinomios dado se puede expresar como

Este a su vez se puede simplificar como

Con tres pasadas del algoritmo de Ruffini encontraremos todos los coeficientes (omitimos los que no influyen en el problema)

Hemos destacado el que nos interesa: con grado 9 aparece el coeficiente 13, que es la solución, pero este procedimiento nos devuelve mucho más. Por ejemplo, con suma 7 sólo son posibles estas elecciones: 7=2+0+5=2+1+4=2+2+3=3+0+4=3+1+3=4+0+3, seis en total, como marca el esquema, y con suma 14 sólo deberán aparecer 3. Son estas: 4+3+7 = 5+3+6 = 5+2+7

Hemos resuelto varios problemas en uno

Si dispones de un CAS puedes ahorrarte bastante trabajo. Aquí tienes el resultado con la calculadora Wiris (hemos recortado la imagen) Compara los coeficientes con los que resultan con Ruffini.

Es normal que pienses que es mucha complicación, pero se trataba de un problema elemental. En sucesivas entradas daremos un enfoque teórico a las funciones generatrices y nos complicaremos un poco, descubriendo así su utilidad.