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 n elementi distinti e sia k un numero naturale. Si dicono combinazioni con ripetizione di classe k tutti i raggruppamenti che si possono formare dagli n elementi, in modo che:

 

- ogni raggruppamento contenga esattamente k elementi;

 

- ogni elemento possa essere ripetuto fino a k 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 k di n 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 k di n elementi distinti tutti i raggruppamenti ordinati di k elementi, formati a partire dagli n elementi assegnati, e nei quali uno stesso elemento può essere ripetuto fino a k volte.

 

Combinazioni con ripetizione e disposizioni con ripetizione sono quindi raggruppamenti di k elementi in cui uno stesso elemento può essere ripetuto fino a un massimo di k 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 k di n 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 A=\{a,b,c,d\}.

 

Partiamo dalle disposizioni con ripetizione di classe 2 degli elementi di A, che sono:

 

\\ aa \ \ ; \ \ ab \ \ ; \ \ ac \ \ ; \ \ ad \\ \\ ba \ \ ; \ \ bb \ \ ; \ \ bc \ \ ; \ \ bd \\ \\ ca \ \ ; \ \ cb \ \ ; \ \ cc \ \ ; \ \ cd \\ \\ da \ \ ; \ \ db \ \ ; \ \ dc \ \ ; \ \ dd

 

Individuiamo quelle che cambiano solo per l'ordine, e che quindi individuano la medesima combinazione:

 

\\ ab \ \mbox{ e } \ ba \ \ \ ; \ \ \ ac \ \mbox{ e } \ ca \\ \\ ad \ \mbox{ e } \ da \ \ \ ; \ \ \ bc \ \mbox{ e } \ cb \\ \\ bd \ \mbox{ e } \ db \ \ \ ; \ \ \ cd \ \mbox{ e } \ dc

 

Ci siamo! Tutte e sole le combinazioni con ripetizione di classe 2 degli elementi di A sono:

 

\\ aa \ \ ; \ \ ab \ \ ; \ \ ac \ \ ; \ \ ad \ \ ; \ \ bb \\ \\ bc \ \ ; \ \ bd \ \ ; \ \ cc \ \ ; \ \ cd \ \ ; \ \ dd

 

Calcolo del numero di combinazioni con ripetizione

 

Il numero di combinazioni con ripetizione di classe k di n elementi distinti si indica con C'_{n,k}, ed è dato dal coefficiente binomiale n+k-1 su k

 

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

 

Poiché n è il numero di elementi distinti di partenza, possiamo supporre che sia n \ge 1. In questo modo la quantità n+k-1 è maggiore o uguale a k per ogni k \in \mathbb{N}.

 

Dalla formula del coefficiente binomiale risulta

 

\dbinom{n+k-1}{k} = \frac{(n+k-1)!}{k! (n+k-1-k)!} = \frac{(n+k-1)!}{k! (n-1)!}

 

pertanto vale la seguente formula per il calcolo del numero di combinazioni con ripetizione:

 

C'_{n,k} = \frac{(n+k-1)!}{k! (n-1)!}

 

Nota bene: nelle combinazioni con ripetizione non vi è alcuna limitazione su k, che può essere un qualsiasi numero naturale (maggiore, minore o uguale a n).

 

Dimostrazione della formula sul calcolo del numero di combinazioni con ripetizione

 

Siano n,k due numeri naturali, con n \ge 1. Vogliamo dimostrare che il numero di combinazioni con ripetizione di classe k di n elementi distinti è

 

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

 

Dimostrazione

 

Consideriamo un qualsiasi insieme A di n \ge 1 elementi. Esso può essere sempre posto in corrispondenza biunivoca con l'insieme \mathbb{N}_A=\{1,2,...,n\}, dunque il numero di combinazioni con ripetizione di classe k degli elementi di A è uguale al numero di combinazioni con ripetizione degli elementi di \mathbb{N}_A.

 

Ciò premesso, consideriamo una qualsiasi combinazione con ripetizione di classe k degli elementi di \mathbb{N}_A. Sia essa

 

m_1, m_2, ...., m_k

 

dove m_1, m_2, ...,m_k sono numeri naturali appartenenti a \mathbb{N}_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:

 

m_1 \le m_2 \le ... \le m_k

 

A questa combinazione con ripetizione associamo la seguente sequenza di numeri naturali:

 

m_1, m_2+1, ..., m_k+k-1

 

Per com'è stata costruita, questa sequenza non presenta ripetizioni, infatti

 

m_1 < m_2+1 < ... < m_k+k-1

 

D'altro canto l'insieme dei numeri m_1,m_2+1,...,m_k+k-1 può essere visto come sottoinsieme dell'insieme dei numeri 1, 2, ..., n+k-1.

 

In particolare, la sequenza che abbiamo costruito è una combinazione semplice di lunghezza k degli elementi dell'insieme 1, 2, ..., n+k-1.

 

In questo modo abbiamo individuato una corrispondenza biunivoca tra le combinazioni con ripetizione di classe k degli elementi n elementi di \mathbb{N}_A=\{1,2,...,n\} e le combinazioni semplici di classe k degli n+k-1 elementi dell'insieme \{1,2,...,n+k-1\}.

 

Da ciò si deduce che il numero di combinazioni con ripetizione di classe k di n elementi è uguale al numero di combinazioni semplici di classe k di n+k-1 elementi.

 

Non ci resta che applicare la formula per il numero di combinazioni semplici

 

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

 

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 n=20 elementi distinti e dobbiamo stabilire quanti sono i raggruppamenti non ordinati formati da k=3 elementi estratti dagli n.

 

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

 

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

 

e sostituiamo n=20 e k=3

 

C'_{20,3}=\dbinom{20+3-1}{3} = \dbinom{22}{3}=\frac{22!}{3!(22-3)!}=\frac{22!}{3! \cdot 19!}=

 

Scriviamo il fattoriale di 22 come prodotto in cui compare 19!, così che possa essere semplificato con il 19! a denominatore

 

=\frac{19! \cdot 20 \cdot 21 \cdot 22}{3! \cdot 19!} = \frac{20 \cdot 21 \cdot 22}{6} = 1540

 

 

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

 

C'_{n,k}=\dbinom{n+k-1}{k} = \dbinom{9+2-1}{2} = \dbinom{10}{2} = 45

 

 

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.

 

C'_{n,k}=\dbinom{n+k-1}{k}=\dbinom{3+4-1}{4} = \dbinom{6}{4}=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 k elementi, si costruiscono partendo da n elementi distinti e senza tenere conto dell'ordine, ma:

 

- le combinazioni semplici sono formate da k elementi distinti, mentre nelle combinazioni con ripetizione uno stesso elemento si può ripetere fino a k volte;

 

- nelle combinazioni semplici dev'essere necessariamente k \le n, perché se fosse k>n non sarebbe possibile formare raggruppamenti di k elementi distinti selezionandoli tra gli n assegnati. Nelle combinazioni con ripetizione non c'è alcuna limitazione su k, che può essere un qualsiasi numero naturale (maggiore, minore o uguale a n).

 

 


 

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)

 

Lezione precedente.....Esercizi correlati.....Lezione successiva

 
 

Tags: cos'è una combinazione con ripetizione - quando usare le combinazioni con ripetizione - formula sul calcolo del numero delle combinazioni con ripetizione e dimostrazione.