Calcul combinatorial

Combinatorica este termenul care denotă în mod tradițional ramura matematicii care studiază modalitățile de grupare și / sau ordonare a elementelor unui set finit de obiecte conform regulilor date. Combinația este în principal interesată să numere astfel de moduri, adică configurații și răspunde de obicei la întrebări precum „Câte sunt ...”, „Câte moduri ...”, „Câte combinații posibile ...” și așa mai departe.

Mai formal, având în vedere un set S de n obiecte, vrem să numărăm configurațiile pe care le pot lua k obiecte luate din acest set. Înainte de a aborda o problemă combinatorie, trebuie specificate două puncte importante:

Dacă ordonarea este importantă, adică dacă două configurații sunt aceleași, cu excepția unei reordonări ({ x, y, z } este egal cu { z, x, y }?)
Dacă puteți avea mai multe repetări ale aceluiași obiect sau dacă același obiect al setului poate sau nu poate fi reutilizat de mai multe ori în cadrul aceleiași configurații.

Permutări

Același subiect în detaliu: Permutare și factorial .

Permutări simple (fără repetări)

O permutare a unui set de obiecte este o prezentare ordonată, adică o succesiune, a elementelor sale în care fiecare obiect este prezentat o singură dată. Pentru a număra numărul de permutări ale unui set cu n obiecte, observați că primul element al configurației poate fi ales în n moduri diferite, al doilea în (n-1) , al treilea în (n-2) și așa mai departe până ultimul care poate fi luat doar într-un fel fiind ultimul rămas. Prin urmare, indicând cu P _n numărul de permutări posibile ale unui set de n elemente, obținem că acestea sunt exact n! ( n factorial ):

P_{n}=n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 1=n!

{\ displaystyle P_ {n} = n \ cdot (n-1) \ cdot (n-2) \ cdot \ dots \ cdot 1 = n!}

P_ {n} = n \ cdot (n-1) \ cdot (n-2) \ cdot \ dots \ cdot 1 = n!

De exemplu, permutările elementelor setului { a, b, c } sunt 3! = 3 × 2 × 1 = 6: abc , bac , bca , cab , cba , acb . Un alt exemplu poate fi următorul: În cât mai multe moduri posibil, putem anagrama cuvântul „MONTE”, numărând și cuvintele fără sens: MONTE n = 5; P ₅ = 5! = 5 × 4 × 3 × 2 × 1 = 120 moduri de a anagrama cuvântul MONTE. NB: în cuvântul MONTE nu se repetă nici o literă.

Pentru a completa mai bine definiția factorială, stabilim și următoarele valori:

1! = 1 și 0! = 1.

Permutații cu repetări

În unele cazuri, un set poate conține elemente care se repetă. În acest caz, unele permutări ale acestor elemente vor fi egale între ele. Prin indicarea cu k ₁ , k ₂ până la k _r de câte ori se repetă elementele 1 , 2 până la r , unde r ≤ n , permutațiile unice (nerepetate) devin:

P_{n}^{k_{1},k_{2},\dots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}

{\ displaystyle P_ {n} ^ {k_ {1}, k_ {2}, \ dots, k_ {r}} = {\ frac {n!} {k_ {1}! k_ {2}! \ cdots k_ { r}!}}}

P_ {n} ^ {k_ {1}, k_ {2}, \ dots, k_ {r}} = {\ frac {n!} {K_ {1}! K_ {2}! \ Cdots k_ {r}! }}

De fapt, este vorba de împărțirea numărului de permutări distincte de n obiecte la numărul de permutări de k ₁ ! prezențe ale aceluiași element, toate egale între ele, apoi prin numărul de permutări de k ₂ ! prezența aceluiași element etc.

Formula este valabilă de fapt pentru orice permutare, chiar și fără repetări de elemente. De fapt, dacă presupunem k ₁ , k ₂ până la k _r egal cu 1 (adică elementele se repetă o singură dată), obținem exact formula permutărilor simple, deoarece avem:

P_{n}^{k_{1},k_{2},\dots ,k_{r}}={\frac {n!}{k_{1}!\cdots k_{r}!}}={\frac {n!}{1!\cdots 1!}}=n!

{\ displaystyle P_ {n} ^ {k_ {1}, k_ {2}, \ dots, k_ {r}} = {\ frac {n!} {k_ {1}! \ cdots k_ {r}!}} = {\ frac {n!} {1! \ cdots 1!}} = n!}

P_ {n} ^ {k_ {1}, k_ {2}, \ dots, k_ {r}} = {\ frac {n!} {K_ {1}! \ Cdots k_ {r}!}} = {\ frac {n!} {1! \ cdots 1!}} = n!

De exemplu: permutările lui { a, a, b } sunt 3! / (2! 1!) = 3 și sunt: aab , aba , baa.

Al doilea exemplu: în câte moduri putem anagrama cuvântul FLUTURĂ.

Literele conținute în cuvânt sunt n = 8; elementele care se repetă sunt „F” (k ₁ = 2); "A" (k ₂ = 3); „L” (k ₃ = 2)

Folosind formula, vom avea:

P_{8}^{k_{1},k_{2},k_{3}}={\frac {8!}{2!3!2!}}={\frac {40320}{24}}=1680

{\ displaystyle P_ {8} ^ {k_ {1}, k_ {2}, k_ {3}} = {\ frac {8!} {2! 3! 2!}} = {\ frac {40320} {24 }} = 1680}

P_ {8} ^ {k_ {1}, k_ {2}, k_ {3}} = {\ frac {8!} {2! 3! 2!}} = {\ Frac {40320} {24}} = 1680

Demutări

Permutările fără puncte fixe se numesc dismutații , cu formula:

\sum _{i=0}^{n}\left(-1\right)^{i}{\frac {n!}{i!}}\sim {\frac {n!}{e}}

{\ displaystyle \ sum _ {i = 0} ^ {n} \ left (-1 \ right) ^ {i} {\ frac {n!} {i!}} \ sim {\ frac {n!} {e }}}

\ sum _ {i = 0} ^ {n} \ left (-1 \ right) ^ {i} {\ frac {n!} {i!}} \ sim {\ frac {n!} {e}}

Aranjamente (secvențe ordonate)

Același subiect în detaliu: Aranjament .

Prevederi simple (fără repetări)

O aranjare simplă a lungimii k a elementelor unui set S de n obiecte, cu k ≤ n , este o prezentare ordonată a k elemente ale lui S în care nu putem avea repetări ale aceluiași obiect. Pentru a obține numărul acestor configurații se consideră că prima componentă a unei astfel de secvențe poate fi aleasă în n moduri diferite, a doua în (n -1) și așa mai departe, până la k -th care poate fi ales în ( n - k +1) moduri diferite. Prin urmare, numărul D _{n, k} al aranjamentelor simple ale k obiecte extrase dintr-un set de n obiecte este dat de:

D_{n,k}=n\cdot (n-1)\cdot \dots \cdot (n-k+1)={\frac {n\cdot (n-1)\cdot \dots \cdot 1}{(n-k)\cdot (n-k-1)\cdot \dots \cdot 1}}={\frac {n!}{(n-k)!}}

{\ displaystyle D_ {n, k} = n \ cdot (n-1) \ cdot \ dots \ cdot (n-k + 1) = {\ frac {n \ cdot (n-1) \ cdot \ dots \ cdot 1} {(nk) \ cdot (nk-1) \ cdot \ dots \ cdot 1}} = {\ frac {n!} {(Nk)!}}}

D_ {n, k} = n \ cdot (n-1) \ cdot \ dots \ cdot (n-k + 1) = {\ frac {n \ cdot (n-1) \ cdot \ dots \ cdot 1} {(nk ) \ cdot (nk-1) \ cdot \ dots \ cdot 1}} = {\ frac {n!} {(nk)!}}

De exemplu, aranjamentele simple de lungime 2 ale elementelor setului {1,2,3,4,5} sunt 5! / (5-2)! = 5! / 3! = 120/6 = 20: 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.

Se observă că permutările sunt cazuri particulare de dispoziții simple: permutările unui set de n obiecte sunt dispozițiile simple ale acestor obiecte de lungime n. Într-adevăr, după numărul lor:

P_{n}=D_{n,n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}={\frac {n!}{1}}=n!

{\ displaystyle P_ {n} = D_ {n, n} = {\ frac {n!} {(nn)!}} = {\ frac {n!} {0!}} = {\ frac {n!} {1}} = n!}

P_ {n} = D_ {n, n} = {\ frac {n!} {(Nn)!}} = {\ Frac {n!} {0!}} = {\ Frac {n!} {1} } = n!

Prevederi cu repetări

O prezentare ordonată a elementelor unui set în care pot apărea repetări ale aceluiași element se numește aranjament cu repetări . Căutăm numărul de secvențe posibile de k obiecte extrase din elementele unui set de n obiecte, fiecare dintre ele putând fi luate de mai multe ori. Nu au nicio posibilitate de a alege prima componentă, n pentru a doua, același număr pentru a treia și așa mai departe, până la k -th care finalizează configurația. Prin urmare, numărul căutat este:

D'_{n,k}={\underbrace {n\cdot n\cdot \dots \cdot n}  \atop {k{\mbox{ volte}}}}=n^{k}

{\ displaystyle D '_ {n, k} = {\ underbrace {n \ cdot n \ cdot \ dots \ cdot n} \ atop {k {\ mbox {times}}}} = n ^ {k}}

D '_ {n, k} = {\ underbrace {n \ cdot n \ cdot \ dots \ cdot n} \ atop {k {\ mbox {times}}}} = n ^ {k}

De exemplu, aranjamentele cu repetarea lungimii 2 a elementelor din {1,2,3,4,5} sunt 5 ² = 25 și sunt: 11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 41 42 43 44 45 51 52 53 54 55. Trebuie remarcat faptul că poate fi și k > n.

Al doilea exemplu: octeții utilizați în informatică sunt dispuneri de 8 obiecte pe elementele {0,1} care pot presupune, prin urmare, 2 ⁸ = 256 de valori distincte: 00000000, 00000001, 00000010, ..., 11111111.

În teoria limbajului formal , aranjamentele reprezintă șiruri pe un alfabet dat.

Combinații (secvențe neordonate)

Același subiect în detaliu: Combinație .

Combinații simple (fără repetări)

O combinație simplă este o prezentare a elementelor unui set în care ordinea componentelor nu contează și același element nu poate fi repetat de mai multe ori. Colecția de combinații de k elemente extrase dintr-un set S de n obiecte distincte poate fi considerată obținută din colecția de aranjamente simple de lungime k a elementelor lui S prin împărțirea acestor secvențe în clasele de secvențe care au același subset de S și alegerea unei singure secvențe din fiecare dintre aceste clase. Fiecare dintre clasele de secvență de mai sus de lungime k conține k ! secvențe, deoarece lângă o secvență σ există toate și numai cele care se pot obține permutând componentele lui σ. Prin urmare, numărul de combinații simple de n elemente de lungime k se obține împărțind la k ! numărul de aranjamente simple de n elemente de lungime k :

C_{n,k}={\frac {D_{n,k}}{P_{k}}}={\frac {n!}{k!(n-k)!}}={n \choose k}

{\ displaystyle C_ {n, k} = {\ frac {D_ {n, k}} {P_ {k}}} = {\ frac {n!} {k! (nk)!}} = {n \ alege k}}

C_ {n, k} = {\ frac {D_ {n, k}} {P_ {k}}} = {\ frac {n!} {K! (N-k)!}} = {N \ alege k}

De obicei, printre diferitele dispoziții simple ale unei clase, secvența în care componentele apar în ordine crescătoare este aleasă ca combinație reprezentativă (toate mulțimile finite pot avea elementele total ordonate, adică asociate biunivoc cu primii numere întregi pozitive).

De exemplu, combinațiile simple de lungime 4 ale elementelor din {1,2,3,4,5,6} sunt 6! / (4! (6-4)!), Adică 6! / (4! 2! ) = 15: 1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 2456, 3456.

Combinații cu repetiții

Când ordinea nu este importantă, dar este posibil să avem componente repetate vorbim de combinații cu repetare . Numărul de combinații cu repetarea a n obiecte din clasa k este egal cu cel al combinațiilor fără repetarea n + k -1 obiecte din clasa k și, prin urmare, este egal cu:

C'_{n,k}={\binom {n+k-1}{k}}

{\ displaystyle C '_ {n, k} = {\ binom {n + k-1} {k}}}

{\ displaystyle C '_ {n, k} = {\ binom {n + k-1} {k}}}

De exemplu, există ${\binom {2+4-1}{4}}={\binom {5}{4}}=5$ ${\ displaystyle {\ binom {2 + 4-1} {4}} = {\ binom {5} {4}} = 5}$ ${\ binom {2 + 4-1} {4}} = {\ binom {5} {4}} = 5$ modalități de distribuire a 4 bomboane nedistinguibile către 2 copii care se disting, numărând și cazurile în care unul dintre copii nu primește bomboane: 0-4, 1-3, 2-2, 3-1, 4-0. Echivalent, combinațiile cu repetiții informează despre numărul de posibile ples n- ai addends nonnegative a căror sumă este k (luând în considerare diferite ples n- în care apar aceleași addends în ordine diferită); în exemplul de mai sus sunt prezentate cele cinci perechi diferite de sumă 4. Mai mult, combinațiile cu repetiții pentru n obiecte din clasa k reprezintă numărul de derivate parțiale de ordin k care cel mult diferă între ele pentru o funcție n variabile cu continuu derivate până la ordinea k (care, prin urmare, respectă ipotezele teoremei lui Schwarz ).

Bibliografie

Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elemente de matematică discretă , Bologna, Zanichelli, 1988.
Sheldon M. Ross, Calculul probabilităților , Milano, Apogee, 2004.