Combinazioni con ripetizione
Si dice combinazione con ripetizione un raggruppamento di k elementi estratti da n elementi distinti, nel quale uno stesso elemento può ripetersi fino a k volte, e in cui l'ordine di estrazione non è rilevante. In altri termini si definisce combinazione con ripetizione di classe k ogni gruppo di k oggetti, eventualmente ripetuti, scelti tra n elementi distinti e senza tenere conto dell'ordine.
Nella lezione introduttiva sulle combinazioni abbiamo visto che ne esistono due tipi: semplici e con ripetizione. Ci siamo già occupati delle combinazioni semplici e sappiamo come si definiscono, quando si usano e come si calcola il numero di combinazioni semplici.
Ora procediamo sulla stessa falsariga e vediamo cosa sono le combinazioni con ripetizione, qual è la formula per calcolare il numero di combinazioni con ripetizione e come si dimostra. Ci soffermeremo anche sulla differenza tra disposizioni con ripetizione e combinazioni con ripetizione, e metteremo in evidenza analogie e differenze tra combinazioni semplici e con ripetizione.
Definizione di combinazione con ripetizione
Consideriamo 
elementi distinti e sia 
un numero naturale. Si dicono combinazioni con ripetizione di classe k tutti i raggruppamenti che si possono formare dagli elementi, in modo che:
- ogni raggruppamento contenga esattamente elementi;
- ogni elemento possa essere ripetuto fino a volte nello stesso raggruppamento;
- due raggruppamenti differiscano tra loro per almeno un elemento, e non per l'ordine.
Le combinazioni con ripetizione di classe k sono anche chiamate combinazioni con ripetizione a k a k.
Per comprendere la definizione di combinazione con ripetizione, e per capire come si costruiscono le combinazioni con ripetizione di classe di elementi distinti, conviene richiamare il concetto di disposizione con ripetizione, che a questo punto del corso sul Calcolo Combinatorio dovrebbe essere assodato.
Si definiscono disposizioni con ripetizione di classe di elementi distinti tutti i raggruppamenti ordinati di elementi, formati a partire dagli elementi assegnati, e nei quali uno stesso elemento può essere ripetuto fino a volte.
Combinazioni con ripetizione e disposizioni con ripetizione sono quindi raggruppamenti di elementi in cui uno stesso elemento può essere ripetuto fino a un massimo di volte, ma vi è una differenza cruciale: le disposizioni con ripetizione sono raggruppamenti ordinati, mentre nelle combinazioni con ripetizione l'ordine con cui gli elementi si susseguono è irrilevante.
Più esplicitamente:
• nel caso delle disposizioni con ripetizione, due o più raggruppamenti che hanno gli stessi elementi con un ordine diverso sono disposizioni diverse;
• nel caso delle combinazioni con ripetizione, due o più raggruppamenti formati dagli stessi elementi sono la medesima combinazione, indipendentemente dall'ordine.
È allora evidente che le combinazioni con ripetizione di classe di elementi si possono ottenere dalle disposizioni con ripetizione della stessa classe: è sufficiente elencare tutte le disposizioni con ripetizione e individuare quelle che cambiano solo per l'ordine.
Esempio sulle combinazioni con ripetizione degli elementi di un insieme
Applichiamo la definizione in un esempio e troviamo tutte le combinazioni con ripetizione di classe 2 degli elementi dell'insieme 
.
Partiamo dalle disposizioni con ripetizione di classe 2 degli elementi di 
, che sono:
Individuiamo quelle che cambiano solo per l'ordine, e che quindi individuano la medesima combinazione:
Ci siamo! Tutte e sole le combinazioni con ripetizione di classe 2 degli elementi di sono:
Calcolo del numero di combinazioni con ripetizione
Il numero di combinazioni con ripetizione di classe di elementi distinti si indica con 
, ed è dato dal coefficiente binomiale 
su
Poiché è il numero di elementi distinti di partenza, possiamo supporre che sia 
. In questo modo la quantità è maggiore o uguale a per ogni 
.
Dalla formula del coefficiente binomiale risulta
pertanto vale la seguente formula per il calcolo del numero di combinazioni con ripetizione:
Nota bene: nelle combinazioni con ripetizione non vi è alcuna limitazione su , che può essere un qualsiasi numero naturale (maggiore, minore o uguale a ).
Dimostrazione della formula sul calcolo del numero di combinazioni con ripetizione
Siano 
due numeri naturali, con . Vogliamo dimostrare che il numero di combinazioni con ripetizione di classe di elementi distinti è
Dimostrazione
Consideriamo un qualsiasi insieme di elementi. Esso può essere sempre posto in corrispondenza biunivoca con l'insieme 
, dunque il numero di combinazioni con ripetizione di classe degli elementi di è uguale al numero di combinazioni con ripetizione degli elementi di 
.
Ciò premesso, consideriamo una qualsiasi combinazione con ripetizione di classe degli elementi di . Sia essa
dove 
sono numeri naturali appartenenti a , eventualmente ripetuti.
Poiché l'ordine con cui si susseguono gli elementi di una combinazione con ripetizione non ha importanza, possiamo supporre che siano disposti in ordine non decrescente:
A questa combinazione con ripetizione associamo la seguente sequenza di numeri naturali:
Per com'è stata costruita, questa sequenza non presenta ripetizioni, infatti
D'altro canto l'insieme dei numeri 
può essere visto come sottoinsieme dell'insieme dei numeri 
.
In particolare, la sequenza che abbiamo costruito è una combinazione semplice di lunghezza degli elementi dell'insieme .
In questo modo abbiamo individuato una corrispondenza biunivoca tra le combinazioni con ripetizione di classe degli elementi elementi di e le combinazioni semplici di classe degli elementi dell'insieme 
.
Da ciò si deduce che il numero di combinazioni con ripetizione di classe di elementi è uguale al numero di combinazioni semplici di classe di elementi.
Non ci resta che applicare la formula per il numero di combinazioni semplici
e abbiamo la tesi.
Esempi sul calcolo del numero di combinazioni con ripetizione
1) Un'urna contiene 20 palline numerate. In quanti modi si possono estrarre 3 palline, supponendo che dopo ogni singola estrazione la pallina venga reimmessa nell'urna e senza tenere conto dell'ordine con cui le palline sono state estratte?
Svolgimento: abbiamo 
elementi distinti e dobbiamo stabilire quanti sono i raggruppamenti non ordinati formati da 
elementi estratti dagli .
Poiché dopo ogni estrazione la pallina viene reimmessa nell'urna, una stessa pallina può essere estratta fino a un massimo di 3 volte, dunque usiamo la formula delle combinazioni con ripetizione
e sostituiamo e
Scriviamo il fattoriale di 22 come prodotto in cui compare 19!, così che possa essere semplificato con il 19! a denominatore
2) Una gelateria offre gelati di 9 gusti diversi. Quante varianti di cono gelato si possono comporre con 2 palline di gelato, supponendo di poter scegliere due volte lo stesso gusto?
Svolgimento: ogni variante di cono gelato è una sequenza non ordinata di 2 gusti scelti tra 9, in cui uno stesso gusto può essere ripetuto fino a 2 volte.
Il numero di varianti di cono gelato è allora uguale al numero di combinazioni con ripetizione di classe 2 di 9 elementi
3) Un'azienda produce 3 tipi di vino e per l'anniversario della sua fondazione ha deciso di mettere in commercio delle confezioni sorpresa composte da 4 bottiglie di vino. In quanti modi possono essere composte le confezioni?
Svolgimento: ogni confezione sorpresa è un raggruppamento formato da 4 bottiglie, e ogni bottiglia può contenere uno dei 3 tipi di vino.
In ogni confezione ciascun tipo di vino può ripetersi fino a un massimo di 4 volte (potrebbero infatti esserci 4 bottiglie con lo stesso tipo di vino) e l'ordine con cui le bottiglie sono disposte nella scatola è irrilevante.
Ciò vuol dire che il numero di possibili confezioni sorpresa è uguale al numero di combinazioni con ripetizione di classe 4 di 3 elementi, che sono 15.
Analogie e differenze tra combinazioni semplici e con ripetizione
Per concludere mettiamo in risalto differenze e analogie tra combinazioni semplici e combinazioni con ripetizione.
Sia le combinazioni semplici che le combinazioni con ripetizione sono raggruppamenti di elementi, si costruiscono partendo da elementi distinti e senza tenere conto dell'ordine, ma:
- le combinazioni semplici sono formate da elementi distinti, mentre nelle combinazioni con ripetizione uno stesso elemento si può ripetere fino a volte;
- nelle combinazioni semplici dev'essere necessariamente 
, perché se fosse 
non sarebbe possibile formare raggruppamenti di elementi distinti selezionandoli tra gli assegnati. Nelle combinazioni con ripetizione non c'è alcuna limitazione su , che può essere un qualsiasi numero naturale (maggiore, minore o uguale a ).
A questo punto potremmo tranquillamente chiudere il corso sul Calcolo Combinatorio. Con le combinazioni con ripetizione abbiamo infatti concluso lo studio di tutti i metodi con cui si può raggruppare un numero finito di elementi, e non ci resterebbe che rimandarvi alla scheda di esercizi sulle combinazioni.
Buona parte degli studenti incontra però qualche difficoltà quando deve risolvere gli esercizi, perché spesso non riesce a capire se deve ricorrere alle permutazioni, alle disposizioni oppure alle combinazioni. Salvo qualche rara eccezione c'è un metodo davvero semplice per capirlo: lo abbiamo spiegato nella prossima lezione, dedicata ai problemi di Calcolo Combinatorio.
Buon proseguimento su YouMath,
Giuseppe Carichino (Galois)
.....
.....
Tags: cos'è una combinazione con ripetizione - quando usare le combinazioni con ripetizione - formula sul calcolo del numero delle combinazioni con ripetizione e dimostrazione.
Ultima modifica: