[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Permutazioni, disposizioni, combinazioni

Il calcolo combinatorio

Tutte le volte che ho a che fare con il calcolo combinatorio, non ricordo bene le formule e le definizioni.
Allora le ho scritte qui.

Per i vostri esperimenti e calcoli, potete usare il Calcolatore combinatorio di permutazioni, disposizioni e combinazioni (javascript)


Il calcolo combinatorio ha per scopo lo studio dei raggruppamenti che si possono formare con elementi di un certo insieme, secondo un determinato criterio.

I possibili raggruppamenti sono i seguenti:

Permutazioni

di n elementi

P(k) = n!

Permutazioni con un elemento ripetuto

di n elementi di cui uno sia ripetuto m volte

P'(n,m) = n!/m!

Permutazioni con elementi ripetuti

di n elementi di cui a ripetuto m volte, b ripetuto r volte, c ripetuto s volte, etc.

P'(n,m,r,s,...) = n! / (m!*r!*s!*...)

Permutazioni cicliche

di n elementi lungo una circonferenza o un circuito chiuso

P'(n) = (n-1)!

Disposizioni semplici

di n elementi a k a k

D(n,k) = n(n-1)(n-2)...(n-k+1)

Disposizioni con ripetizione

di n elementi a k a k, con possibile ripetizione di ogni elemento fino a k volte

D'(n,k) = nk

Combinazioni semplici

di n elementi a k a k

C(n,k) = D(n,k) / P(k)

C(n,k) = [n(n-1)(n-2)...(n-k+1)] / k!

Combinazioni con ripetizione

di n elementi a k a k, con possibile ripetizione di ogni elemento fino a k volte

C'(n,k) = C(n+k-1,k)

E' uguale al numero di combinazioni semplici di n+k-1 elementi a k a k

Permutazioni - P(n)

Definizione.

Dati n elementi distinti, si dicono permutazioni, P(n), i gruppi che si possono formare in modo che:

Esempi.

Per n = 2:

ab; ba.

Per n = 3:

abc acb bac bca cab cba

Per n = 4:
abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

Calcolo delle permutazioni di nelementi.

P(n) = n!

Permutazioni di n elementi non tutti diversi - P(n, m, r, s, ..)

Definizione.

Queste permutazioni si hanno quando:

Esempio.

Ad esempio, se vogliamo costruire le permutazioni di:
abcc:

Per n = 4:
abcd abdc acbd acdbadbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

Sostituiamo:
abcc abcc acbc accbacbc accb
bacc bacc bcac bcca bcac bcca
cabc cacb cbac cbca ccab ccba
cabc cacb cbac cbca ccab ccba

Eliminiamo i doppioni:
abccabcc acbcaccbacbc accb
baccbacc bcacbccabcac bcca
cabccacbcbaccbcaccabccba
cabc cacb cbac cbca ccab ccba

Si procede allo stesso modo se gli oggetti ripetuti sono pių di uno.

Calcolo delle prmutazioni di n elementi non tutti diversi.

P(n, m, r, s, ...) = n! / m!r!s!...

Permutazioni cicliche - P'(n)

Definizione.

Sono le permutazioni di n elementi lungo una circonferenza (o circuito chiuso).

Esempio.

...

Calcolo delle permutazioni cicliche.

P'(n) = (n-1)!

Disposizioni semplici - D(n,k)

Definizione.

Dati n elementi distinti e un numero k<=n si dicono disposizioni di questi n elementi, presi a k a k (o di classe k), D(n,k), tutti i gruppi che si possono formare con gli elementi dati, in modo che:

Esempi.

Le disposizioni semplici di 3 elementi (abc) presi a 2 a 2 sono:

ab ac ba bc ca cb

Le disposizioni semplici di 4 elementi (abcd) presi a 3 a 3 sono:

abc abd acb acd adb adc bac bad
bca bcd bda bdc cab cad cba cbd
cda cdb dab dac dba dbc dca dcb

Calcolo delle disposizioni semplici.

D(n,k) = n(n-1)(n-2)...(n-k+1)

Disposizioni con ripetizione - D'(n,k)

Definizione.

Dati n elementi distinti e un numero k<=n si dicono disposizioni con ripetizione di questi n elementi, presi a k a k (o di classe k), D'(n,k), tutti i gruppi che si possono formare con gli elementi dati, in modo che:

Esempi.

Le disposizioni con ripetizione di 3 elementi (abc) presi a 2 a 2 sono:

aa ab ac ba bb bc ca cb cc

Le disposizioni con ripetizione di 4 elementi (abcd) presi a 3 a 3 sono:

aaa aab aac aad aba abb abc abd
aca acb acc acd ada adb adc add
baa bab bac bad bba bbb bbc bbd
bca bcb bcc bcd bda bdb bdc bdd
caa cab cac cad cba cbb cbc cbd
cca ccb ccc ccd cda cdb cdc cdd
daa dab dac dad dba dbb dbc dbd
dca dcb dcc dcd dda ddb ddc ddd

Calcolo delle disposizioni con ripetizione.

D'(n,k) = nk

Combinazioni semplici - C(n,k)

Definizione.

Dati n elementi distinti e un numero intero positivo k<=n, si chiamano combinazioni C(n,k) di questi n elementi, a k a k (o di classe k), tutti gruppi che si possono formare con gli elementi dati, in modo che:

Esempi.

Le combinazioni di 3 elementi (abc) presi a 2 a 2 sono:

ab ac bc

Le combinazioni di 4 elementi (abcd) presi a 3 a 3 sono:

abc abd acd bcd

Calcolo delle combinazioni.

C(n,k) = D(n,k) / P(k)

C(n,k) = [n(n-1)(n-2)...(n-k+1)] / k!

Combinazioni con ripetizione

Definizione.

Dati n elementi distinti e un numero intero positivo k<=n, si chiamano combinazioni con ripetizione C'(n,k) di questi n elementi, a k a k (o di classe k), tutti gruppi che si possono formare con gli elementi dati, in modo che:

Esempi.

Le combinazioni con ripetizione di 3 elementi (abc) presi a 2 a 2 sono:

aa ab ac bb bc cc

Le combinazioni con ripetizione di 4 elementi (abcd) presi a 3 a 3 sono:

aaa aab aac aad abb abc abd acc acd add

bbb bbc bbd bcc bcd bdd ccc ccd cdd ddd

Calcolo delle combinazioni con ripetizione.

C'(n,k) = C'(n+k-1,k)

Data creazione: 2005

Ultimo aggiornamento: luglio 2008

html 4.0


Sito Web realizzato da Gianfranco Bo