Combinazioni con ripetizione
Le combinazioni con ripetizione somigliano alle combinazioni semplici, solo che permettiamo che gli elementi dell’insieme di partenza M si ripetano.
Definizione e formula
Cominciamo da un bell’esempio: entri in un negozio e vuoi comprare dodici lattine di bibita per una gita. Sullo scaffale ci sono in tutto quattro gusti diversi. Ora hai diverse possibilità di acquisto: puoi ad esempio comprare 5 aranciate, 2 limonate, 1 cola e 4 al gusto di mela, oppure puoi comprare esattamente tre lattine per ogni gusto. Quante possibilità diverse ci sono in tutto di comprare le lattine in modo che ne abbia esattamente dodici?
Abbiamo quindi l’insieme di partenza M = {arancia, limone, cola, mela} e ci chiediamo quante k-uple esistono, con k = 12, che contengono elementi dell’insieme M e in cui l’ordine non conta.
La deduzione della formula è già più complicata che negli altri problemi di calcolo combinatorio. Come prima cosa immaginiamo il nostro acquisto come una successione di zeri e uni, in modo che il numero di uni corrisponda al numero di lattine comprate di un dato gusto e lo zero separi i singoli gusti. Quindi 111011101111101 ci dice che abbiamo comprato tre aranciate (i primi tre 1), poi tre limonate (0 è il separatore, altri tre 1), poi cinque cola (0 separatore e poi cinque 1) e infine una al gusto di mela. L’intero principio è mostrato nella figura seguente:
Se volessimo comprare 6 aranciate, 4 limonate, 2 al gusto di mela e nessuna cola, la successione avrebbe questo aspetto:
Osserviamo che la lunghezza di questa successione è sempre uguale a 15: ci devono essere 12 uni per comprare in tutto 12 lattine. E ci devono essere tre separatori per poter separare i quattro gusti diversi. Resta da calcolare quante successioni di questo tipo, di lunghezza 15, contengono esattamente tre zeri.
Ci basta calcolare la collocazione degli zeri: nel momento in cui distribuiamo 3 zeri tra i 12 uni, abbiamo una combinazione valida di bibite. In altre parole: abbiamo in tutto 15 caselle e 3 di esse dobbiamo occuparle con uno zero. Le caselle rimanenti le occupiamo automaticamente con degli uni.
Questo è ormai un semplice esercizio sulle combinazioni senza ripetizione. Numeriamo le 15 caselle con i numeri {1, …, 15} e da questo insieme scegliamo ogni volta terne di numeri, ottenendo così tre indici in cui collocare lo zero. Ad esempio per la combinazione {2, 4, 7} otterremmo la successione: 101011011111111. Al 2º, 4º e 7º posto c’è uno zero, il resto sono uni. Esistono quindi in tutto
modi diversi di distribuire gli zeri nelle 15 caselle e quindi anche 455 possibilità diverse di comprare 12 lattine, se abbiamo quattro gusti diversi.
Il ragionamento precedente si può generalizzare. Se abbiamo un insieme M di n elementi e ne scegliamo k-uple in cui i singoli elementi possono ripetersi, componiamo una successione di zeri e uni di lunghezza n + k − 1 (k uni e n − 1 zeri) e cerchiamo in quanti modi possiamo collocare gli n − 1 zeri, per cui il numero di combinazioni con ripetizione, che indichiamo con C'n,k, è uguale a
L’ultimo passaggio lo abbiamo potuto fare grazie alle relazioni fondamentali tra i coefficienti binomiali.
Esercizi svolti
- In quanti modi si possono distribuire 20 biglietti omaggio per la prima di uno spettacolo teatrale tra 10 pensionate? È un esercizio sulle combinazioni con ripetizione, perché una pensionata può ricevere più biglietti, potenzialmente anche tutti. Dobbiamo solo capire bene che cosa sono n e k. In realtà scegliamo combinazioni di classe 20 tra 10 pensionate; in altre parole costruiamo una successione di zeri e uni di lunghezza 29, che contiene 20 uni e 9 zeri. Quindi n = 10, k = 20. Otteniamo il risultato:
Capitoli: Calcolo combinatorio, Disposizioni, Permutazioni, Combinazioni, Disposizioni con ripetizione, Combinazioni con ripetizione, Quanti PIN diversi esistono?
