Compoziție (combinatorică)

Pentru alte sensuri, vedeți Compoziție.

În matematică compoziția unui număr întreg, n, este un mod de a scrie n ca suma unui șir de numere întregi strict pozitive. Două șiruri care diferă în ordinea termenilor definesc compoziții diferite ale sumei lor, dar se consideră că definesc aceeași partiție^⁠(d) a acelui număr. Fiecare număr întreg are un număr finit de compoziții distincte. Numerele negative nu au compoziții, dar 0 are o singură compoziție, șirul vid. Fiecare număr întreg pozitiv n are 2ⁿ⁻¹ compoziții distincte.

Bijecție între numerele binare de 3 cifre și compozițiile de 4

O compoziție slabă a unui număr întreg n este similară cu o compoziție a lui n, dar permițând termenilor șirului să fie zero: este un mod de a scrie n ca suma unui șir de întregi nenegativi. Ca o consecință, dacă lungimea compozițiilor nu este mărginită, fiecare număr întreg pozitiv admite un număr infinit de compoziții slabe. Adăugarea unui număr de termeni 0 la sfârșitul unei compoziții slabe nu este de obicei considerată a defini o compoziție slabă diferită; cu alte cuvinte, se presupune că compozițiile slabe sunt extinse implicit la nesfârșit prin termeni 0.

Pentru a generaliza în continuare, o compoziție restricționată A a unui număr întreg n, pentru o submulțime A a numerelor întregi (nenegative sau pozitive), este o colecție ordonată de unul sau mai multe elemente din A a căror sumă este n.

Exemple

Cele 32 de compoziții ale lui 6

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

Cele 11 partiții ale lui 6

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

Cele 16 compoziții ale lui 5 sunt:

• 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.

A se compara cu cele 7 partiții ale lui 5:

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

Este posibil să se pună constrângeri asupra părților compozițiilor. De exemplu, cele cinci compoziții ale lui 5 în termeni diferiți sunt:

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

A se compara cu cele 3 partiții ale lui 5 în termeni diferiți:

• 5
• 4 + 1
• 3 + 2.

Numărul compozițiilor

Numărul compozițiilor lui n+1 în k+1 partiții ordonate formează triunghiul lui Pascal

Folosind numerele Fibonacci pentru a număra compozițiile restricționate {1, 2} ale lui n, de exemplu numărul de moduri în care se poate urca o scară de lungimea n, urcând odată una sau două trepte

Convențional, compoziția vidă este socotită ca singura compoziție de 0 și nu există compoziții de numere întregi negative. Există 2ⁿ⁻¹ compoziții ale lui n ≥ 1, iată demonstrația:

Plasarea fie a unui semn plus, fie a unei virgule în fiecare dintre cele n−1 casete ale matricei

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

produce o compoziție unică de n. Invers, fiecare compoziție a lui n determină o atribuire de plusuri și virgule. Deoarece există n−1 opțiuni binare, se obține rezultatul. Același argument arată că numărul de compoziții ale lui n în exact k părți (o k-compoziție) este dat de coeficientul binomial ${n-1 \choose k-1}$. De reținut că prin însumarea tuturor numerelor posibile de părți, se regăsește valoare de 2ⁿ⁻¹ ca număr total de compoziții ale lui n:

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

Pentru compozițiile slabe, numărul este ${n+k-1 \choose k-1}={n+k-1 \choose n}$, deoarece la fiecare k-compoziție a lui n+k corespunde una slabă dintre cele n după regula:

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

Din această formulă rezultă că numărul de compoziții slabe ale lui n în exact k părți este egal cu numărul de compoziții slabe ale lui k−1 în exact n+1 părți.

Pentru compozițiile restricționate ale lui A, numărul de compoziții ale lui n în exact k părți este dat de coeficientul binomial (sau polinomial) extins ${\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)^{k}$, unde parantezele pătrate indică extragerea coeficientului lui $x^{n}$ din polinomul care îl urmează.

Polinoame omogene

Dimensiunea spațiului vectorial $K[x_{1},\ldots ,x_{n}]_{d}$ al polinomului omogen de gradul d în n variabile peste corpul K este numărul de compoziții slabe ale lui d în n părți. De fapt, o bază pentru spațiu este dată de mulțimea de monoame $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ astfel încât $d_{1}+\ldots +d_{n}=d$. Deoarece exponenții $d_{i}$ pot fi zero, atunci numărul de astfel de monoame este exact cu numărul de compoziții slabe ale lui d.

Bibliografie

• en Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373. 

Legături externe

• en Partition and composition calculator