PROFILPELAJAR.COM

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.

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.^[1]

Exemple

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

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ă.^[2]

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.

Note

^ Heubach, Silvia; Mansour, Toufik (2004). „Compositions of n with parts in a set”. Congressus Numerantium. 168: 33–51. CiteSeerX 10.1.1.484.5148 .
^ en Eger, Steffen (2013). „Restricted weighted integer compositions and extended binomial coefficients” (PDF). Journal of Integer Sequences. 16.

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.