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

thumb|center|600px|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 thumb|Cele 32 de compoziții ale lui 61 + 1 + 1 + 1 + 1 + 12 + 1 + 1 + 1 + 11 + 2 + 1 + 1 + 1. . .1 + 56 thumb|Cele 11 partiții ale lui 61 + 1 + 1 + 1 + 1 + 12 + 1 + 1 + 1 + 13 + 1 + 1 + 1. . .3 + 36 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 thumb|Numărul compozițiilor lui n+1 în k+1 partiții ordonate formează triunghiul lui Pascal

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

Polinoame omogene 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

Bibliografie

Legături externe

Partition and composition calculator

Categorie:Teoria numerelor Categorie:Combinatorică