Calcolo combinatorio: descrizione e regole

Indice

1. Coefficiente binomiale
2. Una proprietà del coefficiente binomiale
3. Binomio di Newton
4. Calcolo combinatorio
5. Permutazioni semplici
6. Permutazioni con ripetizione
7. Disposizioni
8. Disposizioni senza ripetizione
9. Disposizioni con ripetizione
10. Combinazioni
11. Combinazioni senza ripetizione
12. Combinazioni con ripetizione

Coefficiente binomiale

In questo primo paragrafo introdurremo il coefficiente binomiale, il suo simbolo e il modo in cui va calcolato.

Dati due numeri naturali, n e k, con k[math]\binom{n}{k}[/math] (che si legge "n su k") è uguale alla quantità:

Come forse già sai, in matematica, quando un certo numero naturale è seguito dal punto esclamativo, significa che ne stiamo calcolando il suo fattoriale, cioè il prodotto di tutti i numeri naturali che lo precedono e del numero stesso.
Per fare un esempio, il fattoriale del numero 6 è uguale a

Calcoliamo il coefficiente binomiale

.

Questo sarà pari a:

Il coefficiente binomiale fornisce il numero di sottoinsiemi di k elementi che si possono formare a partire da un insieme più grande, costituito da n elementi. Nel caso del nostro esempio, a partire da un insieme di 5 elementi, possiamo costruire dieci gruppi distinti, ciascuno contenente 3 elementi.

Una proprietà del coefficiente binomiale

Il coefficiente binomiale gode di un'interessante proprietà:

[math] \binom{n}{k}= \binom{n}{n-k} [/math]

È abbastanza semplice motivare questa proprietà: basta riflettere sul fatto che ogni volta che definisco un sottoinsieme di k elementi da un insieme più grande, costituito da n elementi, resta definito anche un insieme costituito da n-k elementi.

Binomio di Newton

Attraverso il concetto di coefficiente binomiale, si può anche calcolare facilmente il binomio di Newton, cioè la potenza di un qualsiasi binomio del tipo

.

Si ha che:

Per saperne di più sul coefficiente binomiale, clicca qui

Calcolo combinatorio

Passiamo adesso ad occuparci del vero argomento di questi appunti: il calcolo combinatorio. Il calcolo combinatorio si occupa dei raggruppamenti che si possono ottenere a partire da un numero finito di elementi. In base alle caratteristiche di tali raggruppamenti, distinguiamo permutazioni, disposizioni e combinazioni.

Permutazioni semplici

Si parla di permutazioni semplici quando il numero di oggetti da raggruppare è esattamente uguale al numero di posti a disposizione: questo accade cioè quando

. Per fare un esempio, pensa a tutti i possibili anagrammi della parola RAMO: ciascuno di loro costituisce una permutazione semplice.
Naturalmente, per le permutazioni conterà sempre l'ordine con il quale sono disposti gli elementi.

Per capire quante sono le possibili permutazioni di un insieme costituito da n elementi rifletti su una cosa: per la scelta del primo elemento hai n possibilità; per la scelta del secondo elemento hai n-1 possibilità, perché puoi scegliere tutti gli elementi fatta eccezione per il primo, che hai già scelto precedentemente. Iterando questo ragionamento, si ottiene che le possibili permutazioni di un insieme di n elementi sono:

Permutazioni con ripetizione

Per pensare alle permutazioni con ripetizione, puoi immaginare di dover costruire tutti i possibili anagrammi di una parola che contiene due o più lettere uguali, per esempio la parola DAMA. In questo caso, le possibili permutazioni non saranno pari al fattoriale di 4, perché alcuni anagrammi saranno identici: non c'è infatti un modo per distinguere le due lettere A tra di loro.
La formula per calcolare il numero delle permutazioni con ripetizione è:

In questa formula,

rappresenta il numero complessivo di elementi mentre

il numero di elementi uguali.

Chiariamo subito con un esempio: calcoliamo tutti i possibili anagrammi della parola DOTTO. Le lettere complessive sono 5, ma due di queste, la O e la T, si ripetono due volte ciascuna. Abbiamo così:

possibili anagrammi.

Disposizioni

Si parla di disposizioni quando bisogna creare dei sottoinsiemi costituiti da k elementi a partire da un insieme costituito da n elementi.Nelle disposizioni, a differenza delle combinazioni, è fondamentale l'ordine con cui viene creato il sottoinsieme. Le disposizioni, così come le permutazioni, possono essere sia senza ripetizione che con ripetizione.

Disposizioni senza ripetizione

Le disposizioni senza ripetizione sono dette anche disposizioni semplici: sono quelle nelle quali un elemento, dopo che è stato selezionato una volta, non può essere selezionato di nuovo. Usiamo le disposizioni semplici per rispondere a domande del tipo: quanti numeri di tre cifre, tutte diverse tra loro, posso formare utilizzando i numeri da 1 a 6?

Per rispondere a questa domanda possiamo osservare che, per scegliere la prima cifra del numero, ho a disposizione sei possibilità. Poi, una volta fissata la prima cifra, ho cinque possibilità per scegliere la seconda cifra e quattro possibilità per la terza. In totale, con i numeri da 1 a 6 si possono formare

numeri da tre cifre, tutte diverse tra loro.

In generale, il numero di possibili disposizioni di k elementi da un insieme costituito da n elementi è pari a:

oppure, equivalentemente:

Disposizioni con ripetizione

Le disposizioni con ripetizione differiscono da quelle precedenti perché, come dice il nome, un elemento scelto può anche essere scelto una seconda o una terza volta.

Come al solito, facciamo subito un esempio: se ho a disposizione le lettere A, B, C e D, quante parole da tre lettere posso creare? Saranno considerate valide anche le parole costituite da tre lettere uguali, come AAA oppure CCC. Saranno invece considerate differenti le parole ABC e BAC: ricorda, infatti, che siamo nell'ambito delle disposizioni, per le quali l'ordine è importante.

In questo caso avrò quattro possibili scelte per la prima lettera, quattro possibili scelte per la seconda lettera e ancora quattro possibili scelte per la terza lettera:

In generale, il numero di possibili disposizioni con ripetizione di un insieme di k elementi presi da un insieme più grande, costituto da n elementi è pari a:

Combinazioni

Ciò che rende le combinazioni diverse dalle disposizioni è il fatto che nelle prime l'ordine non è importante. In altri termini, si definisce combinazione un raggruppamento di k elementi estratti da un insieme più grande, costituito da n elementi, nell'ipotesi che l'ordine con cui gli elementi vengono estratti sia ininfluente. Come ormai è consuetudine, anche le combinazioni si differenziano in combinazioni senza ripetizione e combinazioni con ripetizione.

Combinazioni senza ripetizione

Bisogna eleggere due rappresentanti in una classe costituita da 25 studenti. Quante sono le possibili coppie che si possono venire a formare? Questa domanda è un classico esempio di esercizio da risolvere pensando alle combinazioni senza ripetizione. Infatti, non è importante l'ordine con cui vengono eletti i due rappresentanti né, chiaramente, lo stesso studente può essere eletto due volte.

Per fare questo calcolo, si parte dal numero di disposizioni semplici e si raggruppano tra loro i gruppi, in questo caso le coppie, che differiscono solo per l'ordine con cui compaiono i nomi, cioè per una permutazione dei loro elementi.

La formula generale per calcolare il numero di combinazioni di k elementi a partire da un insieme più grande di n elementi è:

, cioè:

Combinazioni con ripetizione

Iniziamo da un esempio semplice. Una gelateria ha a disposizione solo i gusti: fragola, cioccolato e stracciatella: quanti sono i possibili coni da due gusti che si possono formare, ammettendo che si possa scegliere anche due volte lo stesso gusto? Proviamo ad elencarli, iniziando dai gusti doppi: fragola+fragola, cioccolato+cioccolato e stracciatella+stracciatella. Poi abbiamo fragola e cioccolato, cioccolato e stracciatella, fragola e stracciatella. Nient'altro. In tutto sono 6: ma come possiamo arrivare alla risposta corretta in casi più complessi di questo?

La formula generale delle combinazioni con ripetizione prevede che, a partire da un insieme costituito da n elementi si può formare un numero di raggruppamenti di ordine k, nei quali non è importante l'ordine con cui gli elementi compaiono e sono ammesse le ripetizioni, pari a:

Così facendo siamo tornati proprio all'inizio della lezione, richiamando il binomio di Newton.

Per approfondire ancora il discorso sulle combinazioni, clicca qui.

Il calcolo combinatorio è un argomento complesso, ma speriamo che questa piccola guida possa esserti d'aiuto.

per ulteriori approfondimenti vedi anche qua