Composiciones y particiones · Definición

Partición de un entero

combinatoria enumerativacomposiciones y particiones

Antes de empezar necesitas conocer

Las particiones aparecen al contar formas de repartir una cantidad en partes sin importar su orden. Su estudio conecta la combinatoria enumerativa con las funciones generadoras.

Definición

Una partición de un entero n es una forma de escribir n como suma de enteros positivos, sin tener en cuenta el orden de los sumandos. Se denota p(n) el número de particiones de n.

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

Una partición se suele escribir con sus partes en orden no creciente, por ejemplo \(5=3+1+1\). Dos particiones son iguales si tienen las mismas partes con las mismas multiplicidades, y la función \(p(n)\) cuenta estas clases. Por la función generadora de Euler, \(p(n)\) es el coeficiente de \(x^n\) en el producto \(\prod_{k\ge 1}(1-x^k)^{-1}\), donde cada factor representa cuántas copias de la parte \(k\) se usan.

Para \(n=4\) las particiones son \(4\), \(3+1\), \(2+2\), \(2+1+1\) y \(1+1+1+1\), así que \(p(4)=5\). Este conteo directo se puede verificar con la serie generadora, cuyo coeficiente de \(x^4\) también vale \(5\). Este método es útil cuando la lista explícita se vuelve demasiado larga.

Un error típico es contar \(3+1\) y \(1+3\) como particiones distintas. Como el orden no importa, ambas representan la misma partición y deben contarse una sola vez. Conviene escribir siempre las partes en orden decreciente para evitar duplicados.

Para pensar

¿Qué pasaría con el conteo si el orden de los sumandos sí importara?

Cada partición se convertiría en varias composiciones distintas, así que el número crecería y ya no sería \(p(n)\).

Ejercicios 10

  1. ¿Cuántas particiones tiene el entero \(3\)?
  2. ¿Cuál de las siguientes es una partición de \(5\)?
  3. ¿Cuántas particiones de \(4\) tienen exactamente dos partes?
  4. ¿Cuál es el número de particiones \(p(2)\)?
  5. ¿Cuál es la partición de \(6\) escrita en orden no creciente que tiene todas sus partes iguales a \(2\)?
  6. ¿Cuántas particiones tiene \(5\)?
  7. ¿Cuántas particiones de \(6\) tienen todas sus partes distintas?
  8. ¿Cuál es el coeficiente de \(x^3\) en \(\prod_{k\ge 1}\frac{1}{1-x^k}\)?
  9. ¿Cuántas particiones de \(4\) tienen todas sus partes impares?
  10. Sea \(q(n)\) el número de particiones de \(n\) en partes distintas. ¿Cuál es \(q(6)\) y cuál es el valor que cumple la igualdad \(q(6)=p(6)-\)número de particiones de \(6\) con alguna parte repetida?

Referencias

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