Composición de números

En la teoría de números, una composición o descomposición de un número natural es una representación del mismo como una suma de números naturales que tiene en cuenta el orden de los términos. Los términos incluidos en la composición se denominan partes , y su número es la longitud de la composición.

Dividir un número, a diferencia de la composición, no tiene en cuenta el orden de las partes. Por lo tanto, el número de particiones de un número nunca excede el número de composiciones.

Con una longitud fija de composiciones, a veces se permiten términos iguales a 0 en ellas.

Ejemplos

Hay 16 composiciones para el número 5:

${\begin{alignedat}{2}5&=5=\\&=4+1=\\&=3+2=\\&=3+1+1=\\&=2+3= \\&=2+2+1=\\&=2+1+2=\\&=2+1+1+1=\\&=1+4=\\&=1+3+1= \\&=1+2+2=\\&=1+2+1+1=\\&=1+1+3=\\&=1+1+2+1=\\&=1+ 1+1+2=\\&=1+1+1+1+1.\end{alineado en}}$

Número de composiciones

En el caso general, hay composiciones del número n , de las cuales exactamente tienen longitud k , donde es el coeficiente binomial , o el número de combinaciones . $2^{{n-1}}$ ${\tbinom {n-1}{k-1))$ ${\tbinom {n-1}{k-1))$

Prueba

Para probar esta afirmación, basta construir una biyección entre composiciones n de longitud k y subconjuntos de elementos de un conjunto de elementos. Asociemos la composición a un subconjunto del conjunto formado por sumas parciales: . Evidentemente, esta correspondencia tiene todo lo contrario: por subconjunto , cuyos elementos están ordenados de forma ascendente, se puede restaurar la composición original: $(k-1)$ $(n-1)$ $n=n_{1}+\ldots +n_{k}$ $\{1,\;\ldots,\;n-1\}$ $\{n_{1},\;n_{1}+n_{2},\;\ldots,\;n_{1}+\ldots +n_{{k-1}}\}$ $\{m_{1},\;\ldots,\;m_{{k-1}}\}$

n_{1}=m_{1}

, en y, finalmente, .

n_{i}=m_{i}-m_{{i-1}}

i=2,\;\ldots,\;k-1

n_{k}=n-m_{{k-1}}

Así, la aplicación construida es biyectiva y, por lo tanto, el número de composiciones del número n de longitud k es igual al número de subconjuntos de elementos del conjunto de elementos, es decir, el coeficiente binomial . $(k-1)$ $(n-1)$ ${\tbinom {n-1}{k-1))$

Para calcular el número total de composiciones del número n , es suficiente sumar estos coeficientes binomiales o usar el mismo mapeo para construir una biyección entre todas las composiciones del número n y todos los subconjuntos del conjunto de elementos. ■ $(n-1)$

Si se permiten cero partes en las composiciones del número n de longitud k , entonces el número de dichas composiciones será igual a , ya que sumando 1 a cada parte se obtiene una composición del número n + k ya sin cero partes. Si consideramos composiciones del número n con partes cero posibles de cualquier longitud, entonces el número de composiciones, en términos generales, será infinito. ${\tbinom {n+k-1}{k-1))$

Véase también

Dividir un número

Literatura

Sachkov VN Métodos combinatorios de matemáticas discretas. - M. : Nauka, 1977. - S. 241. - 319 p.