Composiciones y particiones · Definición

Composición de un entero

combinatoria enumerativacomposiciones y particiones

Antes de empezar necesitas conocer

Las composiciones son el primer ejemplo de contar particiones con orden y aparecen en muchos problemas de conteo. Para contarlas basta con decidir dónde colocar separadores entre las unidades.

Definición

Una composición de un entero positivo n es una forma de escribirlo como suma ordenada de enteros positivos, donde el orden de los sumandos importa.

\[\binom{n-1}{k-1}\]

El número total de composiciones de \(n\) es \(2^{n-1}\), porque cada uno de los \(n-1\) huecos entre las \(n\) unidades puede tener o no un separador. Si se fija que la composición tiene exactamente \(k\) partes, el número de composiciones es \(\binom{n-1}{k-1}\), pues se eligen \(k-1\) separadores entre \(n-1\) huecos posibles. Estos resultados se deducen del principio de correspondencia biyectiva entre composiciones y conjuntos de separadores.

Consideremos \(n=4\). Las composiciones con exactamente 2 partes son \(1+3\), \(2+2\) y \(3+1\), es decir, \(\binom{3}{1}=3\) casos. Cada una corresponde a elegir un único separador entre los tres huecos de la cadena de cuatro unidades.

Un error típico es confundir composiciones con particiones, contando \(1+3\) y \(3+1\) como la misma. En una composición el orden cuenta, así que son dos objetos distintos, y por eso el total es \(2^{n-1}\) y no el número de particiones de \(n\).

Para pensar

¿Qué pasaría con el número de composiciones de \(n\) si se permitieran partes iguales a \(0\)?

Sería infinito, porque se podrían insertar ceros cuantas veces se quisiera; la fórmula \(2^{n-1}\) exige partes positivas.

Ejercicios 10

  1. ¿Cuántas composiciones de n=3 existen en total?
  2. ¿Cuántas composiciones de n=4 tienen exactamente 1 parte?
  3. Si n=5, ¿cuántos huecos entre unidades hay?
  4. ¿Cuál es el coeficiente binomial \(\binom{4}{2}\)?
  5. ¿Cuántas composiciones de n=2 existen?
  6. ¿Cuántas composiciones de n=5 tienen exactamente 2 partes?
  7. ¿Cuántas composiciones de n=6 tienen exactamente 3 partes?
  8. ¿Cuántas composiciones de n=4 tienen al menos 3 partes?
  9. ¿Cuántas composiciones de n=6 tienen todas sus partes impares?
  10. Demuestra con un contraejemplo que el número de composiciones de n con k partes no siempre coincide con el de particiones de n en k partes. ¿Cuál es un valor de n y k donde difieren?

Después de esto

Referencias

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