Composició (combinatòria)

En matemàtiques, una composició d'un número entero n és una forma d'escriure n com la suma d'una seqüència de número natural. Dos seqüències que diferixen en l'orde dels seus térmens definixen composicions distintes de la seua suma, encara que es consideren que definixen la mateixa partició d'eixe número. Cada sancer té un número finito de composicions distintes. Els números negatius no tenen composicions, pero el 0 té una: la seqüència buida. Cada sancer positiu n té 2ⁿ⁻¹ composicions distintes.

Relació biyectiva entre els número binario de 3 bits (esquerra) i les composicions del número 4 (dreta). En el centre, una representació geomètrica

Una composició dèbil d'un sancer n és similar a una composició de n, pero permet que els térmens de la seqüència siguen zero: és una forma d'escriure n com la suma d'una seqüència de número natural. En conseqüència, tot sancer positiu admet infinites composicions dèbils (si la seua llongitut no està llimitada). Afegir térmens zero al final d'una composició dèbil generalment no definix una composició dèbil diferent; en atres paraules, s'assumix que les composicions dèbils s'estenen implícitament de forma indefinida en térmens zero.

Per a generalisar encara més, una composició restringida per A d'un sancer n, per a un subconjunt A dels sancers (positius o no negatius), és una colecció ordenada d'un o més elements en A que la seua suma és n.

Eixemples

Les 32 composicions de 6

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

Les 11 particions de 6

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

Les setze composicions de 5 són:

• 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's açò en les sèt particions de 5:

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1.

És possible impondre restriccions a les parts de les composicions. Per eixemple, les cinc composicions de 5 en térmens distints són:

• 5
• 4 + 1
• 3 + 2
• 2 + 3
• 1 + 4.

Número de composicions

Archiu:Pascal triangle compositions.svg

Els números de composicions de n+1 en k+1 particions ordenades formen un triàngul de Pascal

Archiu:Fibonacci climbing stairs.svg

Us de la successió de Fibonacci per a contar les composicions {1, 2}-restringides de n, per eixemple, el número de maneres en que es pot pujar una escala de n escalones, pujant indistintament un o dos escalons en cada pas

Per convenció, la composició buida es considera l'única composició de 0, i no existixen composicions de sancers negatius.

Hi ha 2ⁿ⁻¹ composicions de n ≥ 1, segons la demostració següent:

Colocar un signe més o una menge en cada una de les n - 1 caselles de la disposició següent:

$\left(\stackrel{n}{\overbrace{1◻1◻\dots ◻1◻1}}\right)$

produïx una composició única de n. A l'inversa, cada composició de n determina una assignació de signes més i menges. Ya que hi ha n - 1 opcions binarias, el resultat és el següent. El mateix argument mostra que el número de composicions de n en exactament k partixes (una k-composició) ve dau pel coeficient binomial $(\genfrac{}{}{0ex}{}{n-1}{k-1})$. Note's que, sumant sobre tots els possibles números de parts, s'obté 2ⁿ⁻¹ com el número total de composicions de n:

$\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n-1}{k-1})=2^{n-1}.$

Per a composicions dèbils, el número és $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})=(\genfrac{}{}{0ex}{}{n+k-1}{n})$, ya que cada k-composició de n+k correspon a una composició dèbil de n segons la regla:

$a_1+a_2+\dots +a_k{=}^{″}{n}^{″}+k\mapsto (a_1-1)+(a_2-1)+\dots +(a_k-1)=n$

D'esta fòrmula es deduïx que el número de composicions dèbils de n en exactament k partixes és igual al número de composicions dèbils de k − 1 en exactament n + 1 parts.

Per a composicions restringides per A, el número de composicions de n en exactament k partixes ve dau pel coeficient binomial (o polinomial) estés ${(\genfrac{}{}{0ex}{}{k}{n})}_{(1{)}_{a\in A}}=[x^n]{\left(\sum _{a\in A}{x}^a\right)}^k$, a on els corchetes indiquen l'extracció dels coeficients de $x^n$ en el polinomi que li seguix.

Polinomis homogéneus

La dimensió de l'espai vectorial $K[x_1,\dots ,x_n{]}_d$ de polinomis homogéneus de grau d en n variables sobre el cos K és el número de composicions dèbils de d en n partixes. De fet, una base per a l'espai ve donada pel conjunt de monomis $x_1^{d_1}\cdots x_n^{d_n}$ tals que $d_1+\dots +d_n=d$. Ya que els exponents $d_i$ poden ser zero, el número de tals monomis és exactament igual al número de composicions dèbils de d.

Vore també

• Barres i estreles (combinatòria)

Bibliografia

• (2009) Combinatorics of Compositions and Words, Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9.