Composiciones y particiones · Definición

Función generadora de particiones

combinatoria enumerativacomposiciones y particiones

Antes de empezar necesitas conocer

Euler observó que contar particiones equivale a multiplicar series geométricas, una para cada tamaño de parte. Esa idea convierte un problema de conteo en un producto de series.

Definición

La función generadora de particiones es la serie formal \(\sum_{n\ge 0} p(n)\,x^n\), donde \(p(n)\) cuenta las particiones del entero \(n\).

\[\sum_{n\ge 0} p(n)x^n=\prod_{k\ge 1}\frac{1}{1-x^k}\]

Cada parte de tamaño \(k\) puede aparecer \(0,1,2,\dots\) veces, y su contribución es \(1+x^k+x^{2k}+\cdots=\frac{1}{1-x^k}\). Como las partes se eligen de forma independiente, la función generadora es el producto \(\prod_{k\ge 1}\frac{1}{1-x^k}\). Además, al expandir el producto, el coeficiente de \(x^n\) cuenta exactamente las particiones de \(n\).

Por ejemplo, para \(n=4\) las particiones son \(4,\ 3+1,\ 2+2,\ 2+1+1,\ 1+1+1+1\), así que \(p(4)=5\). Al expandir \(\prod_{k\ge1}\frac{1}{1-x^k}\) hasta \(x^4\) se obtiene \(1+x+2x^2+3x^3+5x^4+\cdots\), donde el coeficiente de \(x^4\) coincide con este conteo.

Un error típico es confundir particiones con composiciones. En una composición el orden de los sumandos importa, así que \(1+2\) y \(2+1\) cuentan por separado y la función generadora cambia a \(\frac{1}{1-x-x^2-\cdots}\). Para particiones el orden no cuenta y el producto de arriba es el modelo correcto.

Para pensar

¿Por qué el producto de series geométricas no cuenta el orden de los sumandos, a diferencia de \(1/(1-x-x^2-\cdots)\)?

El producto elige cuántas veces aparece cada tamaño k sin distinguir el orden, mientras que las composiciones registran el orden de los sumandos.

Ejercicios 10

  1. ¿Cuál es el coeficiente de \(x^1\) en \(\prod_{k\ge1}\frac{1}{1-x^k}\)?
  2. ¿Cuántas particiones tiene el entero 2?
  3. ¿Qué coeficiente de la expansión de \(\prod_{k\ge1}\frac{1}{1-x^k}\) corresponde a \(p(3)\)?
  4. ¿Qué factor aporta la parte de tamaño \(k\) a la función generadora?
  5. ¿Cuál es el coeficiente de \(x^2\) en \(\prod_{k\ge1}\frac{1}{1-x^k}\)?
  6. Si \(p(n)\) es el número de particiones de \(n\), ¿cuánto vale \(p(3)\)?
  7. Usando \(1+x+2x^2+3x^3+5x^4+\cdots\), ¿cuál es \(p(4)\)?
  8. ¿Cuál es el coeficiente de \(x^5\) en \(\frac{1}{(1-x)(1-x^2)}\)?
  9. ¿Cuántas particiones de 4 tienen todas sus partes iguales a 1 o 2?
  10. Sea \(F(x)=\prod_{k\ge1}\frac{1}{1-x^k}\). ¿Cuál es el coeficiente de \(x^5\) en \(F(x)\)? Pista: \(p(5)\) se obtiene contando todas las particiones de 5.

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.