En matemáticas, una composición de un número entero n es una forma de escribir n como la suma de una secuencia de números naturales. Dos secuencias que difieren en el orden de sus términos definen composiciones distintas de su suma, aunque se consideran que definen la misma partición de ese número. Cada entero tiene un número finito de composiciones distintas. Los números negativos no tienen composiciones, pero el 0 tiene una: la secuencia vacía. Cada entero positivo n tiene 2n−1 composiciones distintas.
Una composición débil de un entero n es similar a una composición de n, pero permite que los términos de la secuencia sean cero: es una forma de escribir n como la suma de una secuencia de números naturales. En consecuencia, todo entero positivo admite infinitas composiciones débiles (si su longitud no está limitada). Añadir términos cero al final de una composición débil generalmente no define una composición débil diferente; en otras palabras, se asume que las composiciones débiles se extienden implícitamente de forma indefinida con términos cero.
Para generalizar aún más, una composición restringida por A de un entero n, para un subconjunto A de los enteros (positivos o no negativos), es una colección ordenada de uno o más elementos en A cuya suma es n.
Ejemplos
Las dieciséis composiciones de 5 son: 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.
Compárese esto con las siete particiones de 5: 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1.
Es posible imponer restricciones a las partes de las composiciones. Por ejemplo, las cinco composiciones de 5 en términos distintos son: 5 4 + 1 3 + 2 2 + 3 1 + 4.
Número de composiciones
Por convención, la composición vacía se considera la única composición de 0, y no existen composiciones de enteros negativos.
Hay 2n−1 composiciones de n ≥ 1, según la demostración siguiente:
Colocar un signo más o una coma en cada una de las n - 1 casillas de la disposición siguiente:
produce una composición única de n. A la inversa, cada composición de n determina una asignación de signos más y comas. Dado que hay n - 1 opciones binarias, el resultado es el siguiente. El mismo argumento muestra que el número de composiciones de n en exactamente k partes (una k-composición') viene dado por el coeficiente binomial . Nótese que, sumando sobre todos los posibles números de partes, se obtiene 2n−1 como el número total de composiciones de n:
Para composiciones débiles, el número es , ya que cada k-composición de n+k corresponde a una composición débil de n según la regla:
De esta fórmula se deduce que el número de composiciones débiles de n en exactamente k partes es igual al número de composiciones débiles de k − 1 en exactamente n + 1 partes.
Para composiciones restringidas por A, el número de composiciones de n en exactamente k partes viene dado por el coeficiente binomial (o polinomial) extendido , donde los corchetes indican la extracción de los coeficientes de en el polinomio que le sigue.
Polinomios homogéneos La dimensión del espacio vectorial de polinomios homogéneos de grado d en n variables sobre el cuerpo K es el número de composiciones débiles de d en n partes. De hecho, una base para el espacio viene dada por el conjunto de monomios tales que . Dado que los exponentes pueden ser cero, el número de tales monomios es exactamente igual al número de composiciones débiles de d''.
Véase también Barras y estrellas (combinatoria)
Referencias
Bibliografía
Enlaces externos Calculadora de partición y composición
Categoría:Combinatoria