Combinări cu repetiție

Combinările cu repetiție seamănă cu combinările obișnuite, doar că permitem elementelor din mulțimea de bază M să se repete.

Definiție și formulă

Începem cu un exemplu frumos: intri într-un magazin și vrei să cumperi pentru o drumeție douăsprezece sticle de bere. Pe raft sunt în total patru sortimente diferite. Acum ai mai multe posibilități de a cumpăra sticlele – poți cumpăra, de exemplu, 5 Ciuc, 2 Timișoreana, 1 Ursus și 4 Bergenbier sau poți cumpăra de la fiecare producător exact câte trei sticle. În câte moduri diferite poți cumpăra sticlele, astfel încât să ai exact douăsprezece?

Avem deci mulțimea de bază M = {Ciuc, Timișoreana, Ursus, Bergenbier} și ne întrebăm câte k-upluri, unde k = 12, care conțin elemente din mulțimea M și la care nu contează ordinea, există.

Deducerea formulei este destul de complicată în comparație cu celelalte probleme de combinatorică. Mai întâi ne imaginăm cumpărătura ca un șir de zerouri și unități, astfel încât numărul de unități să corespundă numărului de sticle cumpărate de la un anumit producător, iar zeroul să separe producătorii. Așadar 111011101111101 ne spune că am cumpărat trei Ciuc (primele trei 1), apoi trei Timișoreana (0 este separator, următoarele trei 1), apoi cinci Ursus (0 separator și apoi cinci 1) și în sfârșit un Bergenbier. Întregul principiu este redat în figura următoare:

$$\underset{Ciu}{\underbrace{111}}0\underset{Tim}{\underbrace{111}}0\underset{Urs}{\underbrace{11111}}0\underset{Ber}{\underbrace{1}}$$

Dacă am vrea să cumpărăm 6 Ciuc, 4 Timișoreana, 2 Bergenbier și niciun Ursus, șirul ar arăta așa:

$$\underset{Ciu}{\underbrace{111111}}0\underset{Tim}{\underbrace{1111}}00\underset{Ber}{\underbrace{11}}$$

Observăm că lungimea acestui șir este întotdeauna egală cu 15 – trebuie să fie 12 unități, ca să cumpărăm în total 12 beri. Și trebuie să fie trei separatoare, ca să putem separa cei patru producători diferiți. Rămâne deci să calculăm câte astfel de șiruri de lungime 15 există care conțin exact trei zerouri.

Este suficient să calculăm amplasarea zerourilor – în momentul în care așezăm 3 zerouri printre cele 12 unități, avem o combinație validă de beri. Cu alte cuvinte: avem în total 15 căsuțe și trebuie să ocupăm 3 dintre ele cu zero. Căsuțele rămase le ocupăm automat cu unități.

Aceasta este deja o problemă simplă de combinări fără repetiție. Numerotăm cele 15 căsuțe cu numerele {1, …, 15} și alegem acum din această mulțime de fiecare dată câte trei numere, obținând astfel trei indici unde punem zero. De exemplu, pentru combinarea {2, 4, 7} am obține șirul: 101011011111111. Pe locurile 2, 4 și 7 este zero, restul sunt unități. Există deci în total

$$C_{15}^3=455$$

moduri diferite de a așeza zerourile în 15 căsuțe și, prin urmare, 455 de posibilități diferite de a cumpăra 12 beri, dacă avem patru sortimente diferite de bere.

Raționamentul anterior se poate generaliza. Dacă avem o mulțime de elemente M cu n elemente și alegem din ea k-upluri, elementele putându-se repeta, atunci construim un șir de zerouri și unități de lungime n + k − 1 (k unități și n − 1 zerouri) și aflăm în câte moduri putem așeza cele n − 1 zerouri, deci numărul combinărilor cu repetiție, notat ${\bar{C}}_n^k$, este egal cu

$${\bar{C}}_n^k=C_{n+k-1}^{n-1}=C_{n+k-1}^k.$$

Ultima transformare am putut-o face datorită relațiilor de bază dintre combinări.

Exemple rezolvate

1. În câte moduri se pot împărți 20 de bilete gratuite la premiera unui film între 10 pensionare? Este un exemplu de combinări cu repetiție, pentru că o pensionară poate primi mai multe bilete gratuite, potențial chiar pe toate. Trebuie doar să ne dăm seama corect ce este n și ce este k. De fapt alegem combinări de 20 de elemente din 10 pensionare, cu alte cuvinte construim un șir de zerouri și unități astfel încât șirul să aibă lungimea 29, să conțină 20 de unități și 9 zerouri. Deci n = 10, k = 20. Obținem rezultatul:

$${\bar{C}}_{10}^{20}=C_{10+20-1}^{20}=10.015.005.$$

Surse și lecturi suplimentare

• Bělohlávek, Vychodil: Diskrétní matematika (în limba cehă)