Polinomios que cuentan

Imagina que queremos contar de cuantas formas se puede contar de cuantas formas se puede obtener 8 al tirar un par de dados. Uno puede realizar el clásico diagrama de coordenadas

Y concluir que hay 5 formas de obtener el 8.  Con el mismo diagrama, podemos encontrar el resultado f(k) para cualquier suma k:

f(2)=1, f(3)=2, f(4)=3, f(5)=4, f(6)=5, f(7)=6, f(8)=5, f(9)=4, f(10)=3, f(11)=2, f(12)=1.

Pero ¿qué pasa si queremos tirar tres dados? ¿cinco dados? ¿20 dados? ¿m dados? Ya no es práctico usar la representación de coordenadas, necesitamos un nuevo modelo.

Consideremos sólo un dado. ¿De cuantas formas podemos obtener el valor k? Pues de 1 forma si k=1,2,3,4,5,6  y 0 de cualquier otra forma.  Vamos a codificar todos los resultados posibles en una única expresión:

a+a^2+a^3+a^4+a^5+a^6

Donde los exponentes representan los valores de los dados y los coeficientes (todos 1) representan el número de formas de obtener esos valores.  Así, por ejemplo,  a^3 = 1a^3 indica que sólo hay 1 forma de obtener a^3.

Ahora, si tenemos dos dados, pues son dos polinomios a considerar:

(a+a^2+a^3+a^4+a^5+a^6)(a+a^2+a^3+a^4+a^5+a^6)

Hacemos la multiplicación y el resultado es…

a^2+2a^3+3a^4+4a^5+5a^6+6a^7+5a^8+4a^9+3a^{10}+2a^{11}+a^{12}.

Los coeficientes son precisamente el número de formas de obtener el exponente al tirar dos dados.  De hecho, el coeficiente de  a^k en el desarrollo de (a+a^2+a^3+a^4+a^5+a^6)^m es el número de formas de obtener el valor k al tirar m dados y con esta información podemos encontrar el valor exacto.

Observamos que a+a^2+a^3+a^4+a^5+a^6 es una serie geométrica, por lo que

a+a^2+a^3 +a^4+a^5 +a^6 = a \left( \frac{1-a^6}{1-a} \right)

y por tanto

(a+a^2+a^3+a^4+a^5+a^6)^m=a^m(1-a^6)^m(1-a)^{-m}

Ejemplo.

¿De cuántas formas se puede obtener 15 al tirar 8 dados?

El resultado es el coeficiente de a^{15} en  a^8 (1-a^6)^8 (1-a)^{-8}. Es decir, es el coeficiente de a^7 en (1-a^6)^8 (1-a)^{-8}.  Usando el teorema del Binomio (primero para exponentes enteros y luego para exponentes negativos) tenemos

(1-a^6)^8 (1-a)^{-8} = \left(\sum_{j=0}^8 {8 \choose j}(-a^6)^j\right)\left(\sum_{j\ge 0}{j+7 \choose 7}(-a)^j\right),

y al desarrollar, los términos que contienen a^7 son:

\binom{8}{0}\cdot \binom{14}{7}(-a)^7 + \binom{8}{1}(-a^6)\cdot \binom{8}{1}(-a),

con lo que concluimos que el número de formas de obtener 15 al tirar 8 dados es

{14\choose 7} - 64 = 3368.

Reflexiones.

Entre las cuentas, puede perder uno de punto de vista la idea central: estamos representando una sucesión de varios valores (formas de tirar un dado) mediante un solo objeto algebraico (un poliomio), y manipulaciones con este objeto nos dan información acerca de la combinatoria del problema.

El método puede modificarse para resolver problemas similares (por ejemplo, si quisiéramos saber de cuántas formas se puede obtener 30 al tirar 3 dados normales y dos dados en forma de icosaedro, intentaríamos encontrar el coeficiente de a^{30} en el desarrollo de

(a+a^2+a^3+a^4+a^5+a^6) ^3 (a+a^2+a^3+\cdots+a^{20})^2

Este es un caso particular del método de funciones generadoras, en el que una serie de potencias representa una cantidad (posiblemente infinita) de valores de una sucesión.

Bibliografía.

  • Aigner, Martin. A Course in Enumeration. Graduate Texts in Mathematics, 238. (2007)
  • Bona, Miklós. Introduction to Enumerative Combinatorics.  McGraw Hill Higher Education. (2007)
  • Camina and Lewis. An Introduction to Enumeration.  Springer Undergraduate Mathematics Series. (2010)

Tarea sobre funciones generadoras

Del curso de matemáticas discretas.

Recuerden que esta tarea no es para entregar, es de práctica para el examen.

  1. Resuelve las recurrencias:
    1. a_n=5a_{n-1} + 2 para n\ge 1, con a_0=0.
    2. a_n = c a_{n-1} +b para n\ge 1, con a_0=0 y c,b constantes.
    3. a_{n+2} = 2 a_{n+1}- a_n para n\ge 0 y a_0=0, a_1=1.
  2. Para cada una de las siguientes sucesiones, encuentra de forma explícita la función generadora ordinaria y la función generadora exponencial.
    1. a_n=n.
    2. a_n=n^2.
    3. a_n=3^n.
    4. a_n = 5\cdot 4^n - 7\cdot 2^n.
  3. Si A(x) es la función generadora de la sucesión a_0, a_1,a_2, a_3, \ldots, ¿cual es la función generadora ordinaria de las sucesiones b_n?
    1. b_n = a_n + c.
    2. b_n= n a_n.
    3. 0,0,0,a_0,a_1,a_2,a_3,a_4,\ldots.
    4. a_0, 0,a_1,0,a_2,0,a_3,0,a_4,\ldots.
    5. a_5,a_6,a_7,a_8,a_9, \ldots.
    6. a_0, a_2, a_4, a_6, a_8,\ldots.
  4. Si F(x) es la función generadora exponencial de la sucesión a_0, a_1, a_2, a_3,\ldots, ¿cuales son las funciones generadoras exponenciales de las sucesiones en el inciso anterior?
  5. Si A(x) es la función generadora ordinaria \sum_{n\ge 0} a_n x^n. ¿Cual es la función generadora ordinaria de la sucesión
    a_0, a_0+a_1, a_0+a_1+a_2, a_0+a_1+a_2+a_3,\ldots?
  6. Demuestra que si p_{par}(n) es el número de formas de particiones de n donde todas las partes son pares entonces
    \sum_{n\ge 0} p_{par} (n) = \prod_{k\ge 0} \frac{1}{1-x}
    Por ejemplo, para n=10 las particiones con partes pares son  [10], [8,2], [6,4],[6,2,2], [4,4,2],[4,2,2,2],[2,2,2,2,2,] y por tanto p_{par}(10)=7.
  7. ¿Cual es el coeficiente de x^n en el desarrollo de \frac{1}{(1-x^2)^2} ?
  8. Usa el método de funciones generadoras para hallar una fórmula para:
    1. la suma de  los primeros n números consecutivos.
    2. la suma de los cuadrados de los primeros n números consecutivos.
      Sugerencia: Considera el problema 5.
  9. ¿Cual es la función generadora de la sucesión  1,  1/2, 1/3, 1/4, … ?
  10. ¿Cual es la función generadora de la sucesión h_n donde
    h_n = 1 + \frac{1}{2} + \frac{1}{3} +\frac{1}{4} + \cdots + \frac{1}{n}
    para n\ge 1 ?