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, cada entero positivo admite infinitas composiciones débiles (si su longitud no está acotada). Sumar un número de términos 0 al final de una composición débil no suele considerarse que 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.

Tenga en cuenta que los antiguos sabios sánscritos descubrieron muchos años antes que Fibonacci que el número de composiciones de cualquier número natural n como la suma de 1 y 2 es el n-ésimo número de Fibonacci. Tenga en cuenta que estas no son composiciones generales como se definieron anteriormente porque los números están restringidos solo a 1 y 2.

• 1=1 (1)
• 2=1+1=2 (2)
• 3=1+1+1=1+2=2+1 (3)
• 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 (5)
• 5=1+1+1+1+1=1+1+1+2=1+1+2+1=1+2+1+1=2+1+1+1=1+2+2= 2+1+2=2+2+1 (8)
• 6 tendrá 13 combinaciones, etc.

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 de un conjunto". Congreso 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