Le disposizioni
Nel calcolo combinatorio una disposizione è un sottoinsieme ordinato di k elementi estratti da un insieme di n elementi. $$ D(n,k) $$ dove k≤n
Nelle disposizioni ha importanza l'ordine degli elementi.
Il numero di disposizioni di classe k è il numero di k-ple ordinate composte da k elementi estratti da un insieme di n elementi.
Esistono due tipi di disposizioni: semplici e con ripetizione.
Le disposizioni semplici
Le disposizioni semplici sono disposizioni senza ripetizioni degli stessi elementi. $$ D(n,k)=n \cdot (n-1) \cdot \cdot \cdot (n-k+1) $$
Dato un insieme composto da n elementi.
Il numero delle disposizioni semplici di classe k, ossia con k elementi distinti, è dato dalla formula
$$ D(n,k)=n \cdot (n-1) \cdot \cdot \cdot (n-k+1) $$
Nota. Se tutti gli elementi sono distinti k=n la formula è uguale a quella delle permutazioni. $$ D(n,k=n)=n! $$ Se invece gli elementi sono tutti uguali k=1, c'è una sola disposizione semplice $$ D(n,1)=n $$
Un esempio pratico
A una gara partecipano 10 atleti.
Quante sono le possibili disposizioni dei primi tre posti sul podio?
I dati del problema sono
$$ n=10 $$
$$ k =3 $$
Le disposizioni semplici sono
$$ D(10,3) = 10 \cdot 9 \cdot 8 = 720 $$
Le disposizioni con ripetizione
Le disposizioni con ripetizione ammettono la presenza di elementi uguali nella disposizione. $$ D'(n,k)=n^k $$
Un esempio pratico
Con tre lettere A,B,C quante stringhe diverse da due lettere si possono creare?
I dati del problema sono
$$ n=3 $$
$$ k =2 $$
Le disposizioni con ripetizione di classe k=2 sono
$$ D'(3,2) = 3 ^ 2 = 9 $$
Nota. Ecco tutte le 32 disposizioni con ripetizione possibili. Le disposizioni semplici (senza ripetizione) sono invece 3·2=6. Questo esempio dovrebbe rendere più chiara la differenza tra le disposizioni semplici e le disposizioni con ripetizione.
La differenza tra disposizioni e combinazioni
Nelle disposizioni è importante l'ordine degli elementi.
Nelle combinazioni, invece, non conta l'ordine degli elementi.
Esempio. Le stringhe AB e BA sono due disposizioni diverse ma identificano una sola combinazione {AB}. Le combinazioni sono insiemi di lettere in cui l'ordine non conta. Le disposizioni sono invece delle stringhe dove l'ordine è importante.
La differenza tra disposizioni e permutazioni
Nelle disposizioni definisco raggruppamenti con k<n elementi.
Nelle permutazioni, invece, prendo in considerazione dei raggruppamenti con n elementi.
Nota. Se k=n il numero delle disposizioni semplici eguaglia quello le permutazioni. Ad esempio, se n=3 e k=3 ho D'(3,3)=3·2·1=6 disposizioni semplici e n!=3·2·1 permutazioni.
E così via.