Calcolo combinatorio

Il calcolo combinatorio si occupa di contare le modalità e
le configurazioni con cui si può ordinare un insieme di elementi.
Caratteristiche importanti sono: la ripetizione di un oggetto e l'ordinamento della configurazione.

Permutazione semplice, ovvero senza ripetizioni

E' una sequenza ordinata in cui ogni oggetto viene presentato una sola volta.

Ad esempio:
Sono permutazioni semplici dell'insieme di elementi A, B, C e D:
ABCD
BACD
CABC
...

La formula che esprime quante permutazioni semplici sono contemplate per un insieme di elementi è:
P_n = n! = n(n-1)(n-2)...1
dove n indica il numero di oggetti dell'insieme.

Nell'esempio di prima:
insieme di 4 elementi, per cui:
P₄ = 4! = 4⋅3⋅2⋅1 = 24

Permutazioni con ripetizioni

E' una sequenza ordinata di un insieme che presenta elementi ripetuti più volte.

Ad esempio:
Calcolare il numero di anagrammi possibili della parola CASA
CASA
AASC
SCAA
SACA
...

La formula che esprime quante permutazioni con ripetizione sono contemplate per un insieme di elementi è: $$P_{n;k_1,k_2,...,k_n}=\frac{n!}{k_1!\cdot k_2!\cdot ...\cdot k_n!}$$ Dove 'n' è il numero di oggetti dell'insieme,
'k₁' è il numero di ripetizioni dell'oggetto 1,
'k₂' è il numero di ripetizioni dell'oggetto 2, ... e così via.

Esempio A: anagrammi di 'CASA' $$P_{4;1,2,1}=\frac{4!}{1!\cdot 2!\cdot 1!}=\frac{4\cdot 3\cdot 2\cdot 1}{1\cdot 2\cdot 1\cdot 1}=4\cdot 3=12$$
Esempio B: anagrammi di 'FARFALLA' $$P_{8;2,3,\mathrm{1,2}}=\frac{8!}{2!\cdot 3!\cdot 1!\cdot 2!}=\frac{8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1\cdot 3\cdot 2\cdot 1\cdot 1\cdot 2\cdot 1}=8\cdot 7\cdot 6\cdot 5=1680$$


Disposizioni semplici

Le disposizioni sono i sottoinsiemi ordinati (conta l'ordine!)
in cui puoi suddividere l'insieme di oggetti considerato.
Sono semplici quando non c'è ripetizione.

Ad esempio: Le disposizioni semplici di classe 2 dell'insieme A,B,C,D sono:
(A,B)
(B,A)
(A,C)
(C,A)
...

Il numero di disposizioni semplici di 'n' oggetti presi 'k' a 'k' è:
D_n,k = n⋅(n-1)⋅...⋅(n-k+1)

Nell'esempio precedente quindi:
D_4,2 = 4⋅3 = 12



Disposizioni con ripetizione

Le disposizioni sono i sottoinsiemi ordinati (conta l'ordine!)
in cui puoi suddividere l'insieme di oggetti considerato.
In questo caso è contemplata la ripetizione.

Ad esempio: Le disposizioni con ripetizione di classe 2 dell'insieme A,B,C,D sono:

(A,A)
(A,B)
(B,A)
(B,B)
(C,A)
...

La disposizioni di n oggetti di classe k sono:
D'_n,k = n^k

Nell'esempio precedente quindi:
D'_4,2 = 4² = 16

Combinazioni semplici

Le combinazioni sono i sottoinsiemi non ordinati (NON conta l'ordine!)
in cui puoi suddividere l'insieme di oggetti considerato.
Sono semplici quando non c'è ripetizione.

Ad esempio: Le combinazioni semplici di classe 2 dell'insieme A,B,C,D sono:
(A,B)
(A,C)
(A,D)
(B,C)
(B,D)
(C,D)

La formula delle combinazioni semplici di n oggetti presi k a k è: $$C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{n\cdot (n-1)\cdot ...\cdot (n-k+1)}{k!}$$
Nell'esempio precedente quindi: $$C_{4,2}=\frac{D_{4,2}}{P_2}=\frac{4\cdot 3}{2!}=\frac{12}{2\cdot 1}=6$$
Le combinazioni semplici si possono calcolare anche con il coefficiente binomiale: $$C_{n,k}=\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!\cdot (n-k)!}$$
Combinazioni con ripetizione

Le combinazioni sono i sottoinsiemi non ordinati (NON conta l'ordine!)
in cui puoi suddividere l'insieme di oggetti considerato.
In questo caso è contemplata la ripetizione.

Ad esempio: Le combinazioni con ripetizione di classe 2 dell'insieme A,B,C,D sono:
(A,B)
(A,C)
(A,D)
(B,C)
(B,D)
(C,D)
(A,A)
(B,B)
(C,C)
(D,D)

La formula delle combinazioni con ripetizione di n oggetti presi k a k è: $${C\text{'}}_{n,k}=\frac{(n+k-1)!}{k!(n-1)!}$$
Nel nostro esempio infatti: $${C\text{'}}_{4,2}=\frac{(4+2-1)!}{2!(4-1)!}=\frac{5!}{2!3!}=\frac{5\cdot 4\cdot 3\cdot 2\cdot 1}{2\cdot 1\cdot 3\cdot 2\cdot 1}=\frac{5\cdot 4}{2}=\frac{20}{2}=10$$





Test su elementi di calcolo combinatorio

© compitoinclasse
compitoinclasse@virgilio.it