Nozioni di calcolo combinatorio

Disposizioni semplici (D_n,k): si definiscono disposizioni semplici di n soggetti tutti distinti di classe k (scelti a k alla volta) tutti i sottoinsiemi che si possono formare con k degli n elementi in modo tale che differiscano tra loro per la natura di almeno uno degli elementi componenti o per l’ordine con cui questi si presentano. Tali disposizioni possono anche essere viste come: a partire da un gruppo n si ottengono sottogruppi di k unità e non è ammessa la ripetizione dell’oggetto. In formula:  D_n,k = n!/(n-k)!

Esempio 1: disposizione di 4 elementi a gruppi di 3 diversi tra loro per ordine o natura.

D_4,3 = 4!/(4-3)! = 4!/1! = 24 gruppi

Esempio 2: disposizione di 10 elementi a gruppi di 4 diversi tra loro per ordine o natura

D_10,4 = 10!/(10-4)! = 10! / 6! = (10*9*8*7*6*5*4*3*2*1)/(6*5*4*3*2*1) = 10*9*8*7 = 5040

Permutazioni semplici (P_n): si definiscono permutazioni semplici di n oggetti tutti distinti (P_n) tutti i gruppi che si possono formare con gli n oggetti, in modo tale che differiscano esclusivamente per l’ordine con cui questi si presentano. Pn=n!

Esempio1: permutazione di 3 elementi a gruppi di 3 diversi tra loro per l’ordine. Soggetti a,b,c possono formare le seguenti possibili permutazioni: (a,b,c)(a,c,b)(b,a,c)(b,c,a)(c,a,b)(c,b,a). In formula: Pn=n!=3!=6

Esempio2: ci sono 4 posti liberi al cinema, i soggetti A,B,C,D in quanti modi possono disporsi? Pongo n=4 e K=4, non avviene distinzione per natura ma solo per ordine, non ci possono essere ripetizioni, queste particolari disposizioni sono permutazioni semplici e vengono indicate con: Dn,n = Pn = n!= 4!

Combinazioni semplici (C_n,k): si definiscono combinazioni semplici di n soggetti tutti distinti di classe k tutti i sottogruppi che si possono formare con k degli n elementi in maniera tale che differiscano tra di loro esclusivamente per la natura di almeno un componente. C_n,k= D_n,k/P_k =coefficiente binomiale =  n  =    n    = n!/[k!(n-k)!]

                                                                         k        n-k   

cioè:                              Valore sopra!                            .

Valore sotto! * (Valore sopra – Valore sotto)!

Esempio 1: combinazione di 4 elementi a gruppi di 3 diversi per la loro natura. C_n,k= n!/(k!(n-k)!) = 4!/(3!(4-3)!)

Esempio 2: combinazione di 4 elementi a gruppi di 4 diversi per la loro natura. C_n,k= 4!/(4!(4-4)!) = 4!/(4!0!)=0!=1 N.B.

Con ripetizione

Disposizioni con ripetizione (D^r_n,k): si definiscono disposizioni con ripetizione di n soggetti tutti distinti di classe k (scelti k alla volta) tutti i sottoinsiemi che si possono formare con k degli n elementi in modo tale che differiscano tra loro per natura di almeno uno degli elementi componenti, per l’ordine con cui questi si presentano o per la presenza ripetuta di qualche elemento. D^r_n,k = n^k

Esempio: 3 soggetti (a,b,c) concorrono all’attribuzione di 2 ruoli non alternativi, possibili disposizioni: (a,a)(a,b)(a,c)(b,a)(b,b)(b,c)(c,a)(c,b)(c,c) = D^r_n,k = n^k = 3² = 9

Combinazioni con ripetizione (C^r_n,k): si definiscono combinazioni con ripetizione di n soggetti tutti distinti di classe k (scelti k alla volta) tutti i gruppi che si possono formare con k degli n elementi in modo tale che differiscano tra loro per la natura di almeno uno degli elementi componenti o per la presenza ripetuta di qualche elemento. C^r_n,k=C_n+k-1,k =n+k-1

                                                                                                                                                                                                               k

Esempio: 5 soggetti (a,b,c,d,e) concorrono all’attribuzione di 3 ruoli senza nessuna limitazione sui ruoli occupati:

C^r_n,k = n+k-1 = 5+3-1  = 7! / (3!4!) = 5040/144 = 35

k            3

Permutazioni con ripetizione (P^r_n;k1,…kh)

Si definiscono permutazioni con ripetizione di n oggetti gli ordinamenti che si possono formare considerando distinti i gruppi che differiscono tra loro per la posizione d’ordine di almeno un elemento: n! / k₁! * … * k_h!