Il calcolo combinatorio ha per
obiettivo la costruzione di raggruppamenti di elementi distinti o no, che
secondo un determinato criterio, si possono formare con elementi di un certo
insieme.
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 |
Pr(n,m) = n!/m! |
|
Permutazioni con elementi ripetuti di
n elementi di cui aa ripetuto m volte, ab ripetuto r volte, ac ripetuto s
volte, etc. |
Pr(n,m,r,s,...) =
n!/(m!*r!*s!*...) |
|
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 |
Dr(n,k) = n^k |
|
Combinazioni semplici di
n elementi a k a k |
C(n,k) = D(n,k)/P(k) C(n,k) =
[n(n-2)(n-b)...(n-k+1)]/n! |
|
Combinazioni con ripetizione di
n elementi a k a k, con possibile ripetizione di ogni elemento fino a k volte |
Cr(n,k)
= C(n+k-1,k) E' uguale al numero di
combinazioni semplici di n+k-1 elementi a k a k |
Permutazioni
Definizione: Si chiamano
permutazioni di n elementi distinti, tutti i raggruppamenti diversi che si
possono formare con gli elementi dati, rispettando le seguenti proprietà:
1. Ciascun raggruppamento contiene
n elementi.
2. Uno stesso elemento non può
figurare più volte in un raggruppamento.
3. Due qualsiasi raggruppamenti
sono da considerarsi distinti quando differiscono solo per l’ordine con cui
sono disposti gli elementi.
La tabella seguente mostra le
permutazioni al variare di n
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;
Si può notare che il numero delle
permutazioni in funzione di n è dato da n!, quindi abbiamo nel caso di n = 2, 2
permutazioni, per n = 3, 6, e per n = 4, 24 permutazioni.
Permutazioni con uno o più elementi
ripetuti
Si hanno quando:
1. Negli n elementi da permutare
ve ne è uno ripetuto m volte.
2. Oppure ve ne sono diversi
ripetuti, a1 ripetuto m volte, a2 ripetuto r volte, a3 ripetuto s volte, etc.
Ad esempio, se vogliamo costruire
le permutazioni di:
abcc
- prendiamo le permutazioni di 4
elementi, a b c d
- sostituiamo c al posto di d
- eliminiamo le permutazioni
uguali.
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;
Sostituiamo:
abcc; abcc; acbc; accb;acbc; accb;
bacc; bacc; bcac; bcca; bcac;
bcca;
cabc; cacb; cbac; cbca; ccab;
ccba;
cabc; cacb; cbac; cbca; ccab;
ccba;
Eliminiamo i doppioni:
abcc; abcc; acbc;
accb; acbc; accb;
bacc; bacc; bcac;
bcca; bcac; bcca;
cabc; cacb; cbac; cbca; ccab; ccba;
cabc; cacb; cbac; cbca; ccab;
ccba;
Si procede allo stesso modo se gli
oggetti ripetuti sono più di uno.
Disposizioni
Definizione: dati n elementi
distinti, e indicato con k un numero intero positivo e minore o uguale a n, si
chiamano disposizioni di questi n elementi, presi a k a k (o di classe k),
tutti i raggruppamenti diversi che si possono formare con gli elementi dati, in
modo che valgano le seguenti proprietà:
1. ciascun raggruppamento contiene
k elementi;
2. uno stesso elemento non può
figurare più volte in un raggruppamento;
3. due qualsiasi raggruppamenti
sono da considerarsi distinti quando uno di essi contiene almeno un elemento
che non figura nell’altro, oppure gli elementi di un raggruppamento sono gli
stessi dell’altro ma differiscono per l’ordine con cui sono disposti.
Per esempio, le disposizioni di
tre elementi (abc) presi a due a due sono:
ab; ac; ba;
bc; ca; cb.
Se facciamo un confronto con le
permutazioni di tre elementi ci si accorge che è possibile ricavare da queste
le disposizioni, eliminando gli n-k elementi da ciascuna permutazione cioè:
Permutazioni: abc; acb; bac; bca;
cab; cba.
Disposizioni: ab; ac; ba; bc; ca;
cb.
Combinazioni
Definizione: dati n elementi
distinti, e indicato con k un numero intero positivo e minore o uguale a n, si
chiamano combinazioni semplici di questi n elementi, presi a k a k (o di classe
k), tutti i raggruppamenti diversi che si possono formare con gli elementi
dati, in modo che valgano le seguenti proprietà:
1. ciascun raggruppamento contiene
k elementi;
2. uno stesso elemento non può
figurare più volte in un raggruppamento;
3. l'ordine degli elementi non ha
importanza, e quindi due raggruppamenti sono da considerarsi diversi soltanto
quando differiscono tra loro almeno per un elemento.
In altri termini, una combinazione
è un sottoinsieme (di cardinalità k) di un altro insieme (di cardinalità n).
Per esempio: con n=5 e k=3 si ha:
abc; abd; abe; acd; ace; ade; bcd;
bce; bde; cde.
Osservando le prime combinazioni,
si nota che si passa dalla precedente alla successiva aumentando di a l'ultimo
elemento. Però quando quest'ultimo è il valore massimo aumenta il penultimo che
a sua volta non può superare il valore n-1 e cosi di seguito. Ma quando cambia
un valore che non sia l'ultimo, i successivi vanno incrementati di 1.