[HOME - BASE Cinque - Appunti di Matematica ricreativa]
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 |
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!
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!...
Definizione.
Sono le permutazioni di n elementi lungo una circonferenza (o circuito chiuso).
Esempio.
...
Calcolo delle permutazioni cicliche.
P'(n) = (n-1)!
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)
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
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!
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