Composición (combinatoria)

En matemáticas , una composición de un entero n es una forma de escribir n como la suma de una secuencia de números enteros (estrictamente) positivos . Dos secuencias que difieren en el orden de sus términos definen diferentes composiciones de su suma, mientras que se considera que definen la misma partición entera de ese número. Cada número entero tiene un número finito de composiciones distintas. Los números negativos no tienen composiciones, pero el 0 tiene una composición, la secuencia vacía. Cada número entero positivo n tiene 2 ^{n −1} composiciones distintas.

Biyección entre números binarios de 3 bits y composiciones de 4

Una composición débil de un entero n es similar a una composición de n , pero permitiendo que los términos de la secuencia sean cero: es una forma de escribir n como la suma de una secuencia de enteros no negativos . Como consecuencia, todo entero positivo admite infinitas composiciones débiles (si su longitud no está acotada). Generalmente no se considera que añadir un número de términos 0 al final de una composición débil defina una composición débil diferente; en otras palabras, se supone que las composiciones débiles se extienden implícitamente de forma indefinida por los términos 0.

Para generalizar aún más, una composición A -restringida de un entero n , para un subconjunto A de los enteros (no negativos o positivos), es una colección ordenada de uno o más elementos en A cuya suma es n . ^[1]

Ejemplos

Las 32 composiciones de 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6

Las 11 particiones de 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
. . .
3 + 3
6

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.

Compare 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 poner 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.

Compare esto con las tres particiones de 5 en términos distintos:

• 5
• 4 + 1
• 3 + 2.

Número de composiciones

Los números de composiciones de n  +1 en k  +1 particiones ordenadas forman el triángulo de Pascal

Usando la secuencia de Fibonacci para contar las composiciones restringidas {1, 2} de n , por ejemplo, la cantidad de formas en que uno puede ascender una escalera de longitud n , tomando uno o dos escalones a la vez.

Convencionalmente, la composición vacía se considera la única composición de 0 y no existen composiciones de números enteros negativos. Existen 2 ^{n −1} composiciones de n  ≥ 1; aquí hay una prueba:

Colocar un signo más o una coma en cada uno de los n  − 1 cuadros de la matriz

${\displaystyle {\big (}\,\overbrace {1\,\square \,1\,\square \,\ldots \,\square \,1\,\square \,1} ^{n}\,{\big )}}$

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. Como 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 ) está dado por el coeficiente binomial . Nótese que al sumar todos los números posibles de partes recuperamos 2 ^{n −1} como el número total de composiciones de n : ${\displaystyle {n-1 \choose k-1}}$

${\displaystyle \sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.}$

Para composiciones débiles, el número es , ya que cada k -composición de n  +  k corresponde a una débil de  n por la regla ${\displaystyle {n+k-1 \choose k-1}={n+k-1 \choose n}}$

${\displaystyle a_{1}+a_{2}+\ldots +a_{k}=n+k\quad \mapsto \quad (a_{1}-1)+(a_{2}-1)+\ldots +(a_{k}-1)=n}$

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 A -restringidas, el número de composiciones de n en exactamente k partes está dado por el coeficiente binomial (o polinomial) extendido , donde los corchetes indican la extracción del coeficiente de en el polinomio que lo sigue. ^[2] ${\displaystyle {\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)^{k}}$ ${\displaystyle x^{n}}$

Polinomios homogéneos

La dimensión del espacio vectorial de un polinomio homogéneo 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 está dada por el conjunto de monomios tales que . Como se permite que los exponentes sean cero, entonces el número de tales monomios es exactamente el número de composiciones débiles de d . ${\displaystyle K[x_{1},\ldots ,x_{n}]_{d}}$ ${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$ ${\displaystyle d_{1}+\ldots +d_{n}=d}$ ${\displaystyle d_{i}}$

Véase también

• Estrellas y barras (combinatoria)

Referencias

1. Heubach, Silvia ; Mansour, Toufik (2004). "Composiciones de n con partes en un conjunto". Congressus Numerantium . 168 : 33–51. CiteSeerX 10.1.1.484.5148 . 
2. Eger, Steffen (2013). "Composiciones enteras ponderadas restringidas y coeficientes binomiales extendidos" (PDF) . Journal of Integer Sequences . 16 .

• Heubach, Silvia; Mansour, Toufik (2009). Combinatoria de composiciones y palabras . Matemáticas discretas y sus aplicaciones. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9.Zbl1184.68373  .​

Enlaces externos

• Calculadora de particiones y composición