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)