FUNCIONES GENERATRICES Y COMBINATORIA

P. S. Laplace (1749-1827), en su obra Teoría Analítica de las Probabilidades (1812), expuso los principios y las aplicaciones de lo que él llamó geometría del azar. En este libro, el matemático francés recopiló y unificó una serie de Memorias sobre el tema que había publicado desde 1771. En esta obra Laplace hizo una presentación de numerosos recursos del Análisis Matemático aplicados al estudio de los fenómenos aleatorios.

Entre la multitud de métodos del Cálculo Algebraico e Infinitesimal aparecen conceptos como el de Función Generatriz, que presentaremos en este trabajo; el Método de los Mínimos Cuadrados que había sido utilizado en casos concretos por A. M. Legendre (1752-1833) y K.F. Gauss (1777-1855) y, pero en la Teoría Analítica Laplace dio una demostración formal del mismo; aparece el problema de la aguja de Buffon, propuesto en 1777  por G.L. Leclerc, (conde de  Buffon)  (1707-1788) para obtener una aproximación del número p; y el conocido posteriormente como Teorema de Bayes.

En suma, a lo largo del texto quedan reflejados los extensos y profundos conocimientos de Análisis Matemático de su autor. Por ejemplo, se obtienen los valores numéricos de las integrales definidas más comunes. Utilizó transformadas integrales para resolver ecuaciones diferenciales (Trasformada de Laplace) o la demostración general del teorema, enunciado por J.L. Lagrange (1736-1813), para el desarrollo de cualquier función implícita en una serie.

Utilizaremos un concepto que relaciona la Aritmética con el Álgebra. Una sucesión numérica con una función expresada en forma de serie potencial Se llama Función Generatriz de la sucesión a0, a1, a2, a3, …. a la función

f(x) = a0 + a1 x + a2 x2 + a3 x3, ….

cuando la función es convergente, aunque en estos ejercicios destacaremos más los coeficientes que las cuestiones de convergencia.

Podemos calcular las funciones generatrices con programas informáticos de manipulación algebraica como Máxima, Derive o Maple. En este artículo se han calculado con Derive en los siguientes problemas.

PROBLEMA 1: Queremos construir un collar de 10 cuentas con bolas rojas, verdes y blancas (tiene que tener los tres colores) con las siguientes condiciones: a) Entre 2 y 5 bolas rojas, b) Menos de cuatro verdes y c) Por lo menos tres blancas.

Respuesta: Rojas = {2,3,4,5}, Verdes {0,1,2,3} y Blancas {3,4,5,6,7}

De las ochenta ternas [4x4x5] del producto cartesiano de los conjuntos {2,3,4,5} x {0,1,2,3} x {3,4,5,6,7} calcularemos cuántas suman 10. Como pueden, por ejemplo las ternas:

(3,2,5) … (3 rojas, 2 verdes y 4 blancas)

(2,3,5) … (2 rojas, 2 verdes y 5 blancas) o

(2,2,6) … (2 rojas, 1 verde y 6 blancas)

Sean PR(x) = x2 + x3 + x4 + x5 el polinomio que tiene por exponentes las 4 opciones de elegir bolas rojas,

Pv(x) = 1 + x1 + x2 + x3 el polinomio que tiene por exponentes las 4 opciones de elegir bolas verdes  y

PB(x) = x3 + x4 + x5 + x6 + x7 el polinomio que tiene por exponentes las 5 opciones elegir de bolas blancas.

El producto de los tres polinomios da la función generatriz de grado 15:

PR(x)·Pv(x)·PB(x) = x15 + 3·x14 + 6·x13 + 10·x12 + 13·x11+ 14·x10 + 13·x9 + 10·x8 + 6·x7 + 3·x6 + x5

El coeficiente de x15 [=1] da el número de formas que se puede formar un collar de quince cuentas [que es (4,5,6)] con las condiciones impuestas.

Por ejemplo, el coeficiente de x14 [=3] da el número de formas en que se puede formar un collar de catorce cuentas que, con las condiciones impuestas, son (4,3,7), (5,2,7) y (5,3,6). El

Por ejemplo, el coeficiente de x6 [=3] da el número de formas en que se puede formar un collar de seis cuentas, con las condiciones impuestas, son (2,1,3), (2,0,4) y (3,0,3).

Finalmente, el collar de 10 cuentas se podrá formar de 14 formas diferentes con bola rojas, verdes y blancas ya que 14 es el coeficiente de x10.

 

PROBLEMA 2. Lanzamos un dado 5 veces ¿Cuál es la probabilidad de que la suma de sus cinco resultados sea 20?

Respuesta: Tenemos seis resultados posibles A = {1,2,3,4,5,6}. Con cinco lanzamientos los resultados posibles serán los elementos del producto cartesiano

Quíntuplas posibles: Serán los elementos del producto cartesiano A5 = AxAxAxAxA, que tiene 65 elementos (Quíntuplas). Expresado en términos de combinatoria:  RV6, 5 = 65 = 7776.

Quíntuplas favorables: Serán cada una de las quíntuplas que sumen 20, por ejemplo:

(2,3,2,4,5,4) o (1 3,5,4,5,2).

Con la función generadora (x1 + x2 + x3 + x4 + x5 + x6)5 aparecen todos los productos posibles y, al asociar (reducir) términos semejantes aparecen monomios con exponentes de 5 a 30.

El coeficiente de x20 de  (x1 + x2 + x3 + x4 + x5 + x6)5 nos dará el número de monomios (antes de reducir términos).

Calculando la Función Genetatriz con Derive:

f(x) = (x1 + x2 + x3 + x4 + x5 + x6)5 = x30 + 5·x29 + 15·x28 + 35·x27 + 70·x26 + 126·x25 + 205·x24 + 305·x23 + 420·x22 + 540·x21 + 651·x 20 + 735·x19 + 780·x18 + 780·x17+ 735·x16 + 651·x15 + 540·x14 + 420·x13 + 305·x12 + 205·x11 + 126·x10 + 70·x9 + 35·x8 + 15·x7 + 5·x6 + x5

El coeficiente de x 20 de la función generatriz es 651, los casos favorables (quíntuplas que suman 20) será 615. Luego la probabilidad de que la suma sea 20 será  651/7776 = 0,085.

 

PROBLEMA 3. Determina el número de soluciones enteras para x1 + x2 + x3 + x4 = 40 donde 0 ≤ xi ≤15 para todo i, 1 ≤ i ≤ 4

Solución: Evidentemente, xi  puede tomar los valores:

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

La Función Característica f(x) = (1+ x+ x2 + …+ x15 )4

Es el coeficiente de x40 de Función Característica será la solución, es decir será el número de soluciones de la ecuación:

x60  + 4·x59  + 10·x58  + 20·x57   + 35·x56  + 56·x55 + 84·x54 + 120·x53  + 165·x52  + 220·x51  + 286·x50   + 364·x49  + 455·x48 + 556·x47 + 668·x46 + 800·x45 + 949·x44 + 1112·x43 + 1286·x42 + 1468·x41   + 1655·x40 + 1844·x39  + 2032·x38   + 2216·x37  + 2393·x36 + 2560·x35 +33 2720·x34 + 2864·x33   + 2965·x32 + 3056·x31 + 3158·x30  + 3220·x29 + 3245·x28 + 3236·x27 + 3196·x26  + 3128·x25  + 3035·x24  + 2920·x23 + 2786·x22   + 2632·x21   + 2469·x20   + 2320·x19 + 2128·x18 + 1884·x17 + 1735·x16 + 1608·x15  +  1394·x14  + 1200·x13 + 1025·x12 + 868·x11 + 728·x10 + 604·x9  + 496·x8 +  400·x7 + 310·x6  + 252·x5  + 217·x4  + 120·x3  + 54·x2  + 108·x + 81

Por lo tanto, la ecuación tiene 1655 soluciones.

Add a Comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *