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 \le 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 raggruppamenti ordinati di \( k \) elementi distinti presi da un insieme di \( n \) elementi, senza ripetizioni. Il numero totale di tali disposizioni è $$ D(n,k)=n \cdot (n-1) \cdot \ldots \cdot (n-k+1) $$ che rappresenta il prodotto dei primi \( k \) fattori decrescenti a partire da \( n \). In alternativa, si può esprimere la stessa quantità anche nella forma $$ D(n,k) = \frac{n!}{(n-k)!} $$

Le disposizioni semplici di $ n $ elementi distinti di classe $ k $ sono tutti i modi possibili di scegliere $ k $ elementi tra gli $ n $ disponibili tenendo conto dell’ordine.

Ogni gruppo di $ k $ elementi differisce dagli altri per almeno un elemento o per l'ordine degli elementi.

In altre parole, due disposizioni semplici sono diverse se cambia almeno un elemento oppure se gli stessi elementi compaiono in un ordine diverso. 

Esempio. Considero un insieme con $ n=3 $ elementi $ \{ A, B, C \} $. Le disposizioni semplici di classe $ k=2 $ sono tutti i raggruppamenti possibili di due elementi senza ripetizione e tenendo conto dell'ordine. Complessivamente, ci sono sei disposizioni semplici: $$ AB, BA, AC, CA, BC, CB $$ Nelle disposizioni l'ordine degli elementi, ossia la loro "disposizione", è importante. Ad esempio, "AB" e "BA" sono due disposizioni distinte. Lo stesso vale per "AC" e "CA", ecc.

Inoltre, non si contano le disposizioni contenenti lo stesso elemento più volte come "AA", "BB", "CC".

Numero delle disposizioni semplici di classe k

Dato un insieme composto da $ n $ elementi.

Le disposizioni semplici di classe $ k $ sono tutti i gruppi ordinati di $ k $ elementi scelti fra gli $ n $ disponibili. La formula seguente indica esattamente quanti sono questi gruppi:

$$ D(n,k)=n \cdot (n-1) \cdot \cdot \cdot (n-k+1) $$

Il prodotto dei primi $ k $ fattori decrescenti a partire da $ n $ fornisce quindi il numero totale delle disposizioni semplici di classe $ k $.

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 $$

Esempio 2

Supponiamo di avere 4 elementi: A, B, C, D.

Voglio formare disposizioni di classe 2, cioè gruppi ordinati di 2 elementi.

I gruppi possibili sono:

AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

Quindi, le disposizioni semplici $ D_{4,2} $ sono 12

$ D_{4,2} = 4 · 3 = 12 $$

Esempio 3

Considero ancora l'insieme di 4 elementi: A, B, C, D.

Ora voglio formare gruppi ordinati di 3 elementi.

Utilizzo la formula per sapere quanti gruppi sono

$$ D_{n,3} = n · (n - 1) · (n - 2) $$

$$ D_{4,3} = 4 · 3 · 2 = 24 $$

Significa che le disposizioni possibili sono 24.

In effetti, prendendo A come primo elemento ci sono 6 gruppi

ABC, ABD, ACB, ACD, ADB, ADC

Altri 6 gruppi si ottengono prendendo B come primo elemento:

BAC, BAD, BCA, BCD, BDA, BDC

Altri 6 con C come primo elemento:

CAB, CAD, CBA, CBD, CDA, CDB

E infine altri 6 gruppi con D come primo elemento:

DAB, DAC, DBA, DBC, DCA, DCB

Complessivamente, ci sono 24 gruppi.

Nota. Come già visto negli esempi precedenti, l'ordine degli elementi è molto importante. Ad esempio "ABC" e "CBA" sono due disposizioni semplici distinte. Inoltre, in ogni disposizione non ci sono ripetizioni dello stesso elemento. Ad esempio, non si considerano "AAB", "ABB", ecc.

Le disposizioni con ripetizione

Le disposizioni con ripetizione consentono di utilizzare più volte lo stesso elemento all’interno della stessa disposizione. $$ D'(n,k)=n^k $$

Una disposizione di classe $ k $ è un gruppo formato da $ k $ elementi selezionati da un insieme di $ n $ elementi.

Anche in questo caso l’ordine conta, proprio come nelle disposizioni semplici. La differenza è che qui uno stesso elemento può comparire più volte in posizioni diverse.

Ogni gruppo di $ k $ elementi si distingue dagli altri per almeno un elemento oppure per l’ordine con cui gli elementi compaiono.

Un esempio pratico

Con tre lettere A, B, C quante stringhe diverse di due lettere si possono formare?

I dati del problema sono

$$ n=3 $$

$$ k =2 $$

Il numero delle disposizioni con ripetizione di classe k=2 è:

$$ D'(3,2) = 3 ^ 2 = 9 $$

Ecco tutte le 9 disposizioni con ripetizione possibili:

AB, AC, AA, BA, BC, BB, CA, CB, CC

In questo caso è ammessa la presenza dello stesso elemento più volte nello stesso gruppo, come in AA, BB o CC.

Nota. Le disposizioni semplici (cioé senza ripetizione) sarebbero, invece, solo 3·2=6 perché non permettono di utilizzare due o più volte lo stesso elemento. Il confronto tra le disposizioni semplici e quelle con ripetizione dovrebbe rendere più chiara la differenza.

Esempio 2

Considero un insieme composto da 4 elementi: A, B, C, D.

Le disposizioni di classe 2 con ripetizione sono gruppi ordinati di due elementi tratti dall’insieme. I gruppi possibili sono:

AB, AC, AD, AA, BA, BC, BD, BB, CA, CB, CD, CC, DA, DB, DC, DD

Quindi, le disposizioni semplici $ D'_{4,2} $ sono 16

$$ D'_{4,2} = 4^2 = 16 $$

Nota. A differenza delle disposizioni semplici, in questo caso sono ammesse le ripetizioni degli stessi elementi come "AA", "BB", "CC", "DD".

Note

Alcune note e osservazioni personali a margine sulle disposizioni:

• La differenza tra disposizioni e combinazioni
  Nelle disposizioni l’ordine degli elementi è rilevante. Nelle combinazioni, invece, l’ordine non ha alcuna importanza. In altre parole:
  • le combinazioni sono insiemi di elementi, quindi indipendenti dall’ordine
  • le disposizioni sono sequenze ordinate, quindi l’ordine è essenziale

  Esempio. Le stringhe AB e BA sono considerate due disposizioni diverse, perché l’ordine cambia. Dal punto di vista delle combinazioni, però, rappresentano un unico gruppo, indicabile come {A,B}, perché ciò che conta è solo l’insieme degli elementi, non la loro sequenza.

• La differenza tra disposizioni e permutazioni
Nelle disposizioni considero raggruppamenti di $ k $ elementi scelti da un insieme di n elementi, con $ k $ minore di $ n $. Nelle permutazioni, invece, considero raggruppamenti che coinvolgono tutti gli $ n $ elementi dell’insieme.

Nota. Quando $ k=n $ il numero delle disposizioni semplici coincide con il numero delle permutazioni. Ad esempio, se $ n=3 $ e $ k=3 $ si hanno sei disposizioni semplici $$ D'(3,3)=3·2·1=6 $$ e anche sei permutazioni $$ n!=3·2·1 = 6 $$ Il risultato è lo stesso.

E così via.