Le combinazioni con ripetizione
Definizione
Si chiama combinazione con ripetizione di n elementi di un insieme I composto da k oggetti distinti, un gruppo di n elementi di I non necessariamente distinti e disposto in un ordine qualsiasi.
Teorema sulle combinazioni con ripetizione
Il numero di combinazioni con ripetizione di k elementi di un insieme I composto da n oggetti distinti è:
ESERCIZIO 1
Un’urna contiene 21 biglie etichettate con le lettere dell’alfabeto italiano. Per tre volte di fila, si estrae una biglia, si segna la lettera su un foglio e si rimette la biglia nell’urna. Alla fine si comunicano le 3 lettere, leggendole in ordine alfabetico. Quante triplette del genere possono essere create?
SOLUZIONE
La stessa biglia può essere estratta più di una volta: Possiamo immaginare il problema in termini di contenitori da riempire : le 21 scatole rappresentano le lettere dell’alfabeto e ogni qualvolta una certa lettera viene estratta si pone una biglia nel vano corrispondente.
L’estrazione “F,A,F” verrebbe così rappresentata dalla ripartizione con 2 biglie in F, una biglia in A e tutte le altre scatole vuote.
Abbiamo già risolto questo tipo di problema: ponendo k = 21 (numero di contenitori, cioè di lettere possibili) e n = 3 (numero di biglie, cioè di estrazioni) si ha la soluzione
ESERCIZIO 2
Da un’urna contenente 21 biglie etichettate con le lettere dell’alfabeto italiano, si estraggono 3 biglie mettendole in fila sul tavolo e ridisponendole infine in ordine alfabetico. Quante file di questo tipo possono essere create?
SOLUZIONE
Il riordino finale assicura l’irrilevanza dell’ordine di estrazione.
Si tratta banalmente di scegliere 3 oggetti su 21 (combinazione semplice) e questo si può fare in
modi.
ESERCIZIO 3
Una gelateria offre gelati di 10 gusti diversi. Quante varianti di coppetta si possono comporre con 3 palline? Nota bene: è ammesso anche scegliere 3 volte lo stesso gusto.
SOLUZIONE
Ragionando per analogia con l’esercizio 1, i gusti sono i contenitori e le biglie rappresentano le palline di gelato.
Si ha quindi k = 10 , n = 3 e la soluzione
ESERCIZIO 4
In quanti modi si può scrivere 10 come somma di 3 numeri naturali (0 escluso)? Bada bene, in questo problema i “modi” 4+3+3 e 3+4+3 sono considerate combinazioni diverse.
SOLUZIONE
Stavolta la soluzione si ottiene più facilmente pensando ai “bastoncini” piuttosto che alle formule.
Disponendo in fila 10 biglie e separandole con 2 bastoncini si possono creare tutte le somme desiderate (vedi sotto la “ripartizione” 5+2+3.
Gli interstizi sono 9 , i bastoncini 2, la soluzione non può che essere
ESERCIZIO 5
Escludendo sempre la cifra 0, quanti numeri di 5 cifre esistono, tali che le loro cifre siano disposte in ordine “uguale o crescente”? (“uguale o crescente” significa che una cifra può ripetersi, ma non può mai essere seguita da una minore. Casi accettabili sono quindi 23.678 , 35.558 o addirittura 77.777 mentre 35.823 o 12.324 non andrebbero bene).
SOLUZIONE
Il problema è complesso e per essere risolto necessita di un po’ di fantasia.
Immaginiamo di scegliere 5 cifre qualsiasi da 1 a 9 (le cifre possono anche ripetersi) e di metterle in fila in ordine crescente. Si ottengono così proprio i numeri “in salita” descritti dal problema. L’estrazione con restituzione da un’urna contenente 9 cifre e la conclusiva “messa in ordine” (la quale rende irrilevante l’ordine di estrazione), mostra che il problema è assimilabile all’ ESERCIZIO 1, cioè a una combinazione con ripetizione.
La soluzione è
Osservazione
Ragionando in modo simmetrico, i numeri “in discesa” saranno anch’essi 1287 .
I numeri “monocifra” 11.111, 22.222 , …. (9 in tutto) sono gli unici a far parte di entrambi i conteggi.
Ricordando che i numeri composti da 5 cifre (senza mai usare lo 0) sono
95 = 59.049 (disposizione con ripetizione)
possiamo concludere che i numeri “Sali e Scendi” sono i più frequenti
95 – 2 * 1287 + 9 = 56484
più del 95% del totale.
