Matematica per le applicazioni I - calcolo combinatorio

   
   
unità. Infatti si ha + +   k 1 k k 1

Calcolo Combinatorio Adolfo Scimone pag 1

Calcolo combinatorio

Consideriamo un insieme di n oggetti di natura qualsiasi. Indicheremo questi oggetti con a , a ,..., a .

1 2 n

Con questi n oggetti si vogliono formare dei gruppi, ciascuno formato da uno stesso numero k di oggetti con k n .

Disposizioni semplici di n oggetti

Definizione: Dati n oggetti e detto k un numero intero positivo minore o uguale a n, si chiamano disposizioni semplici di questi n oggetti presi a k a k o della classe k, tutti i gruppi che si possono formare con gli n oggetti dati in modo che ogni gruppo contenga soltanto k degli oggetti dati, e che due gruppi qualunque differiscano fra loro o per qualche oggetto, oppure per l’ordine con cui gli oggetti sono

disposti. Esempio – Dati tre oggetti, indicati con le lettere A,B,C, le disposizioni di classe 2 sono tutte le filerealizzabili usando ogni volta due delle tre lettere: AB, BA, AC, CA, BC, CB. Si tratta, quindi, di sei file possibili.

Indichiamo quindi con D il numero delle disposizioni semplici di n oggetti di classe k.

Teorema – Il numero delle disposizioni semplici di n oggetti di classe k è dato da:

D_n,k = n! / (n-k)!

Cioè D è uguale al prodotto dei k numeri consecutivi decrescenti a partire da n.

Dimostrazione: Gli n elementi diversi a₁, a₂,..., a_n presi ad uno ad uno danno luogo, ovviamente, ad n disposizioni di classe uno:

D_n,1 = n!

Per formare tutti i gruppi di classe 2 consideriamo, successivamente, ciascun gruppo di classe 1 e, di seguito, poniamo uno alla volta ciascuno degli n-1 elementi estranei al gruppo considerato. Ogni gruppo di classe 1 genera così n-1 disposizioni di classe 2.

gruppi di classe 2. Possiamo quindi scrivere= −D D ( n 1) (2)n ,2 n ,1

Per formare tutti i gruppi di classe 3, consideriamo, successivamente, ciascun gruppo di classe 2 e ,−di seguito, poniamo uno alla volta ciascuno degli n 2 elementi estranei al gruppo considerato.−Ogni gruppo di classe 2 genera così n 2 gruppi di classe 3. Possiamo quindi scrivere= −D D ( n 2) (3)n ,3 n ,2 − −e così via.

Per formare i gruppi di classe k 1 consideriamo ciascun gruppo di classe k 2 e− − = − +poniamo uno alla volta ciascuno degli n ( k 2) n k 2 elementi estranei al gruppoconsiderato. Avremo quindi:= − +D ( n k 2) D (k-1)− −n , k 1 n , k 2 −

Per formare infine tutti i gruppi di classe k, consideriamo ciascun gruppo di classe k 1 e poniamo,− − = − +di seguito, uno alla volta ciascuno degli n ( k 1) n k 1 elementi estranei al gruppoconsiderato.Avremo= − +D ( n k 1) D (k)−n , k n , k

1. Moltiplicando membro a membro le k relazioni (1), (2),……,(k) precedenti otteniamo
2. Calcolo Combinatorio Adolfo Scimone pag 2⋅ ⋅ ⋅ = − − − + − +D D .... D nD (n 1) D ( n 2)..... D (n k 2) D ( n k 1)− −n ,1 n ,2 n , k n ,1 n ,2 n , k 2 n ,k 1
3. cioè ⋅ ⋅ ⋅ = − − − + − +D D .... D n ( n 1)(n 2).....(n k 2)(n k 1) D D ....D −n ,1 n ,2 n , k n ,1 n ,2 n , k 1
4. Dividendo per i fattori comuni contenuti nei due membri otteniamo
5. = − − − + − +D n ( n 1)( n 2).....(n k 2)(n k 1)n , k
6. Disposizioni con ripetizione
7. Siano dati n elementi distinti a , a ,..., a1 2 n
8. proponiamoci di calcolare il numero dei gruppi che si possono formare prendendo k degli elementi dati, con k qualunque e con l’eventuale ripetizione di qualche elemento. Si ha
9. <i) Se è k n si ritrovano le disposizioni semplici, oltre a quelle nelle quali un elemento è ripetuto come nel caso

ottenere un 13.= =Si ha n 3 k 13= =' 13D n 1.594.233 colonne3,13Permutazioni di n oggettiDefinizione Si chiamano permutazioni semplici di n oggetti (elementi) distinti le disposizioni semplici degli n elementi presi ad n ad n.In altre parole si può anche dire : Le permutazioni di n oggetti distinti sono tutti i gruppi formati ciascuno da tutti gli n oggetti dati e che differiscono fra loro soltanto per l’ordine degli oggetti.Indicando con P il numero delle permutazioni di n elementi, si han=P Dn n , n =e quindi avremo ( k n)= − − ⋅ ⋅P n ( n 1)( n 2)...........3 2 1ncioè = ⋅ ⋅ −P 1 2 3...............( n 1) nnCalcolo Combinatorio Adolfo Scimone pag 3cioèIl numero delle permutazioni semplici di n oggetti distinti è uguale al prodotto dei primi n numeri naturali.Definizione Se k è un numero intero maggiore di 1, chiamasi fattoriale del numero k, e si indica con k!, il numero che risulta dal prodotto dei primi

n numeri interi, cioè n = k!/(1*2*3*...*(k-1)*k) = Se k = 1 o k = 0, si pone per definizione n = 1! = 1 0! = 1

Combinazioni semplici

Definizione: Si chiamano combinazioni semplici di n elementi distinti presi a k a k (o di classe ≤ k) k n, tutti i possibili gruppi di k oggetti che si possono formare con gli n elementi in modo da considerare distinti solo quei gruppi che differiscono per almeno un elemento.

Confrontando la precedente definizione con quella delle disposizioni semplici, potremo dire che, per esempio, i due gruppi abc; acb costituiscono due disposizioni diverse (differiscono per l'ordine degli elementi) ma formano la stessa combinazione.

Risulta quindi evidente che ogni combinazione può generare tante disposizioni quante sono le permutazioni dei suoi k elementi. Si ha quindi n = D C k = n!/(k!(n-k)!), k ≤ n, k ≥ 0.