Nozioni di calcolo combinatorio

Disposizioni semplici (Dn,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:  Dn,k = n!/(n-k)!

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

D4,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

D10,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 (Pn): si definiscono permutazioni semplici di n oggetti tutti distinti (Pn) 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 (Cn,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. Cn,k= Dn,k/Pk =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. Cn,k= n!/(k!(n-k)!) = 4!/(3!(4-3)!)

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

Con ripetizione

Disposizioni con ripetizione (Drn,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. Drn,k = nk

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) = Drn,k = nk = 32 = 9

Combinazioni con ripetizione (Crn,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. Crn,k=Cn+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:

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

k            3

Permutazioni con ripetizione (Prn;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! / k1! * … * kh!

 

Schema riassuntivo:

Conta l’ordine

Conta la natura

Contano entrambi

Qualcosa si ripete?

SI (K>n)

Prn,k1…kh

CRn,R

DRn,k

NO (K≤n)

Pn

Cn,k

Dn,k

Richiedi gli appunti

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *


sette + 9 =

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>