Compoziție (combinatorică)
Î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 2n−1 compoziții distincte.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Binary_and_compositions_4.svg/600px-Binary_and_compositions_4.svg.png)
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
[modificare | modificare sursă]![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Compositions_of_6.svg/220px-Compositions_of_6.svg.png)
1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/ca/Partitions_of_6.svg/220px-Partitions_of_6.svg.png)
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
[modificare | modificare sursă]![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Pascal_triangle_compositions.svg/220px-Pascal_triangle_compositions.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/10/Fibonacci_climbing_stairs.svg/220px-Fibonacci_climbing_stairs.svg.png)
Convențional, compoziția vidă este socotită ca singura compoziție de 0 și nu există compoziții de numere întregi negative. Există 2n−1 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
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 . De reținut că prin însumarea tuturor numerelor posibile de părți, se regăsește valoare de 2n−1 ca număr total de compoziții ale lui n:
Pentru compozițiile slabe, numărul este , deoarece la fiecare k-compoziție a lui n+k corespunde una slabă dintre cele n după regula:
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 , unde parantezele pătrate indică extragerea coeficientului lui din polinomul care îl urmează.[2]
Polinoame omogene
[modificare | modificare sursă]Dimensiunea spațiului vectorial 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 astfel încât . Deoarece exponenții pot fi zero, atunci numărul de astfel de monoame este exact cu numărul de compoziții slabe ale lui d.
Note
[modificare | modificare sursă]- ^ Heubach, Silvia; Mansour, Toufik (). „Compositions of n with parts in a set”. Congressus Numerantium. 168: 33–51. CiteSeerX 10.1.1.484.5148
.
- ^ en Eger, Steffen (). „Restricted weighted integer compositions and extended binomial coefficients” (PDF). Journal of Integer Sequences. 16.
Bibliografie
[modificare | modificare sursă]- en Heubach, Silvia; Mansour, Toufik (). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.