Il logo di batmath
www.batmath.it
pag.precedente | pag.successiva

Combinazioni

Combinazioni semplici

Il terzo problema base del calcolo combinatorio è quello del computo del numero di sottoinsiemi di un dato insieme finito. E' immediato che un sottoinsieme di k elementi, presi da un insieme di n elementi, può essere pensato come una collezione di k di n oggetti, in cui non conti l'ordine. Questo distingue il problema qui trattato da quello del calcolo delle disposizioni (semplici). Si dà la seguente definizione:

Dato un insieme A di n elementi, un suo sottoinsieme contenente k (≤n) elementi si chiama una combinazione semplice degli n elementi di classe k oppure a k a k.

Il numero delle combinazioni di n elementi di classe k si indica con Cn,k o con img. E' evidente che, se si considera una qualunque combinazione di n elementi di classe k e si permutano in tutti i modi possibili (k!) i suoi elementi si ottengono le disposizioni di n elementi di classe k. Questo ci permette di concludere (si tenga presente, se n=k, che 0!=1) che:

img.

I numeri img si chiamano anche, per un motivo legato allo sviluppo del binomio (a+b)n, coefficienti binomiali. Se k=0 il numero dei sottoinsiemi  possibili è 1 (solo l'insieme vuoto) e si pone perciò img, in accordo anche con la formula appena riportata.

Nel modello dell'urna questo problema equivale a considerare un'estrazione di k palline da un'urna che ne contiene n, distinguibili, senza reimbussolamento e senza tener conto dell'ordine: si potrebbero anche estrarre tutte le k palline contemporaneamente.

Nello schema a celle questo problema equivale a disporre k oggetti in n celle, con la condizione che in una cella non si può mettere più di un oggetto e senza tenere conto di quale oggetto si mette nella cella, ma solo se la cella è riempita oppure no. Possiamo considerare l'esempio di C4,3: dovremo disporre 3 oggetti in quattro celle; poiché non è indispensabile sapere quale oggetto finisce in una data cella, li indichiamo semplicemente con "x". Si ottiene:

a x x x  
b x x   x
c x   x x
d   x x x

Si tratta cioè di un problema di suddivisione di k oggetti in n cassetti con la condizione che in un cassetto non vada più di un oggetto e che non interessi quale oggetto ci va. La differenza con le disposizioni è proprio costituita dal fatto che qui non ha interesse quale oggetto va in un determinato cassetto.

Esempio

Sia A = {a,b,c,d} e k = 2. Allora C4,2 = 6, e i sottoinsiemi sono: {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}.

Combinazioni con ripetizione

Riprendiamo ora in esame il modello dell'urna visto prima e supponiamo di reimbussolare ogni pallina dopo l'estrazione, avendo segnato il suo contrassegno, ma senza tenere conto dell'ordine. Per esempio sia n=4 e le palline siano contrassegnate con a,b,c,d; supponiamo di estrarre, con reimbussolamento, 2 palline. Le possibili estrazioni sono:  {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,a}, {b,b}, {c,c}, {d,d}.

L'esempio mostra che potremmo anche schematizzare il problema in questo modo: dato un insieme A di n oggetti, quanti gruppi di k di questi oggetti possiamo formare, senza tenere conto dell'ordine, ma consentendo la ripetizione degli elementi? Detto ancora in altri termini: supponiamo di avere oggetti di n tipi diversi e di voler costruire, mediante essi, un insieme B di k elementi, prendendo a1 elementi del primo tipo, a2 elementi del secondo, ..., an elementi dell'ultimo (non escludendo che qualcuno degli ai sia zero), ovviamente in modo che a1+a2+...+a n=k. La domanda che ci poniamo è: in quanti modi è possibile costruire B? Per esempio si abbiano oggetti di quattro tipi, che possiamo indicare (i tipi, non gli oggetti!) con a, b, c, d, e di voler costruire un insieme B di 2 elementi. I possibili insiemi B (indicando i tipi di oggetti e non gli oggetti) sono: {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,a}, {b,b}, {c,c}, {d,d}, esattamente come prima.

Questo ci suggerisce di dare la seguente definizione:

Dati n oggetti fra loro distinti, si chiama combinazione con ripetizione, di classe k, di questi oggetti, ogni gruppo di k elementi, anche non distinti, presi tra gli n oggetti dati, nell'ipotesi che l'ordine sia ininfluente. Ovviamente si può avere kn.

Un'equazione diofantea

Riprendendo in esame l'esempio dell'urna già considerato, tenendo conto che non interessa l'ordine di apparizione delle palline, potremmo rappresentare il risultato di un'estrazione anche scrivendo quante volte compare ciascuna pallina. Le possibilità sono: {1,1,0,0}, {1,0,1,0}, {1,0,0,1}, {0,1,1,0}, {0,1,0,1}, {0,0,1,1}, {2,0,0,0}, {0,2,0,0}, {0,0,2,0}, {0,0,0,2}, che corrispondono, ordinatamente, alle combinazioni scritte prima: {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,a}, {b,b}, {c,c}, {d,d}.

Questo ci suggerisce un altro modo di pensare alle combinazioni con ripetizione: dato il numero naturale k si chiede in quanti modi esso possa essere scritto come somma di n numeri naturali. Se chiamiamo x1, x2, ..., xn, i naturali incogniti, si tratta di risolvere l'equazione x1+x2+...+x n=k. Un'equazione di questo tipo, in cui i coefficienti delle incognite sono naturali e i valori ammessi sono naturali, si chiama diofantea, dal nome del matematico greco Diofanto (tra le equazioni diofantee famosissima è quella del teorema di Fermat: xn+yn=z n, recentemente risolta in senso negativo se n > 2).

Un problema di suddivisione

Utilizzando lo schema a celle il problema può essere formulato anche in un altro modo, in accordo con quanto già fatto con le disposizioni e con le combinazioni semplici: le combinazioni con ripetizione di n oggetti di classe k possono essere pensate come la suddivisione di k oggetti in n cassetti, con la condizione che conti solo il numero degli oggetti in ogni cassetto e non il tipo di oggetto, e supponendo che qualche cassetto possa anche restare vuoto. Detto con altre parole: supponiamo di avere un insieme E di k oggetti, indistinguibili tra loro, e di volerli suddividere fra n insiemi (cassetti) E1, E2, ..., En, consentendo anche che qualcuno degli Ei possa restare vuoto. Si chiede in quanti modi ciò può essere fatto. Il problema è chiaramente equivalente a quello  di scrivere un numero naturale k come somma di n numeri naturali e, quindi, a quello delle combinazioni con ripetizione di n oggetti di classe k (si presti attenzione al fatto che si tratta delle combinazioni di n oggetti, tanti quanti il numero degli insiemi, di classe k, tante quanti sono gli oggetti da distribuire). Questa versione del problema consente un semplice calcolo del numero delle combinazioni con ripetizione, che indicheremo con Crn,k. Si trova:

img

Puoi vedere la dimostrazione della formula sulle combinazioni con ripetizione

Ancora sulla suddivisione. Si può rivisitare il precedente esempio nel modo qui di seguito descritto. Indichiamo con "0" i k oggetti da distribuire, e con "1" gli n insiemi (cassetti) in cui piazzarli. Possiamo immaginare di fare la suddivisione scrivendo tanti 1 quanti sono i contenitori, seguiti ciascuno da tanti zero quanti sono gli oggetti che vi piazziamo dentro. Per esempio, avendo quattro oggetti e tre contenitori, scrivendo 1001010, intendiamo che due oggetti sono nel primo contenitore e uno ciascuno negli altri due, scrivendo 1000011, intendiamo che i quattro oggetti sono nel primo contenitore, mentre gli altri due rimangono vuoti. In sostanza le distribuzioni degli oggetti nei contenitori si possono vedere come numeri in binario, di lunghezza n+k. Poiché questi numeri iniziano sempre con "1", si tratta di vedere in quanti modi possiamo piazzare k zeri in n+k-1 posti o, alternativamente, n-1 numeri 1 sempre in n+k-1 posti. Si ritrova, come era ovvio, lo stesso risultato di sopra.

Osservazione conclusiva. Seguendo la trattazione precedente, possiamo concludere che, nel caso delle combinazioni con ripetizione, invece di parlare di "Combinazioni di n oggetti di classe k", sarebbe più opportuno parlare di "Combinazioni di oggetti di n tipi, di classe k". Se infatti ho n tipi di oggetti, è facile pensare a insiemi costituiti anche da più oggetti dello stesso tipo; se invece dispongo di n oggetti, risulta logicamente più difficile pensare di costituire insiemi in cui gli oggetti stessi siano ripetuti. Si tratta comunque di una questione di comodità di ragionamento, utile soprattutto nello schema a celle o nei problemi di suddivisione.

pag.precedente | pag.successiva
pagina pubblicata il 07/05/2004 - ultimo aggiornamento il 26/01/2005