Disposizioni Semplici

Dato un insieme $A$ composto da $n$ elementi, una disposizione semplice di $n$ elementi di classe $k$ , con $0 < k \leq n$ , è una sequenza ordinata di $k$ elementi dell'insieme, in cui ogni elemento compare una sola volta.

Le disposizioni semplici sono utili per calcolare il numero di possibili sequenze di elementi di un insieme, in cui l'ordine degli elementi è importante e ogni elemento compare una sola volta.

Introduzione

Per comprendere le disposizioni semplici ci conviene partire da un esempio.

Supponiamo che ad un torneo di calcio partecipino 4 squadre: A, B, C e D. Di queste squadre, solo le prime tre classificate ricevono un premio.

Proviamo a calcolare quante sono le possibili classifiche delle prime tre squadre. Tali classifiche sono composte da tre elementi, che possiamo rappresentare con una sequenza di tre lettere.

Per effettuare questo calcolo, proviamo a procedere graficamente.

Costruiamo dapprima le possibili classifiche che hanno come prima classificata la squadra A. Per farlo, adoperiamo un diagramma ad albero:

Come possiamo osservare, le possibili classifiche con la squadra A in testa sono sei: ABC, ABD, ACD, ACB, ADB e ADC.

Procediamo ora a costruire le possibili classifiche con la squadra B in testa:

Anche in questo caso le possibili classifiche sono sei: BAC, BAD, BCD, BCA, BDA e BDC.

Tenendo presente che le possibili squadre in testa possono essere 4, possiamo concludere che il numero totale di possibili classifiche è $4 \cdot 6 = 24$ .

Definizione di Disposizione Semplice

Come abbiamo visto nell'esempio precedente, siamo partiti da un insieme di elementi di cardinalità $n$ e abbiamo selezionato $k$ elementi per formare una sequenza. In particolare, nell'esempio avevamo un insieme di 4 elementi e abbiamo selezionato 3 elementi per formare delle terne.

Ognuna di tali sequenze ha delle caratteristiche ben precise:

Ogni elemento dell'insieme può comparire una sola volta nella sequenza;
L'ordine degli elementi nella sequenza è importante.

Queste sequenze sono dette disposizioni semplici.

Definizione

Le Disposizioni Semplici

Dato un insieme di $n$ elementi, una disposizione semplice di $n$ elementi di classe $k$ , con $0 < k \leq n$ , è una sequenza ordinata di $k$ elementi dell'insieme, in cui ogni elemento compare una sola volta.

Ogni disposizione semplice differisce dalle altre per almeno un elemento e per l'ordine degli elementi.

Esse prendono anche il nome di Permutazioni Parziali o k-Permutazioni.

Calcolo delle Disposizioni Semplici

Quindi, una disposizione semplice di classe $k$ è una sequenza, o meglio una n-pla (ennupla), di $k$ elementi dell'insieme, in cui ogni elemento compare una sola volta. Ogni disposizione semplice differisce dalle altre per almeno un elemento o per l'ordine degli elementi o per entrambi.

Quello che ci poniamo ora è: quante sono le disposizioni semplici di classe $k$ di un insieme di $n$ elementi?

Riprendiamo l'esempio precedente. Abbiamo un insieme di 4 elementi e vogliamo selezionare 3 elementi per formare delle terne.

Il procedimento che abbiamo usato è stato il seguente:

Abbiamo prima scelto una squadra per la prima posizione; ma di squadre per la prima posizione ne abbiamo 4;
Una volta scelta la squadra per la prima posizione, abbiamo scelto una squadra per la seconda posizione; ma di squadre per la seconda posizione ne rimangono 3 in quanto la squadra scelta per la prima posizione non può essere ripescata;
Infine, una volta scelte le squadre per la prima e la seconda posizione, abbiamo scelto la squadra per la terza posizione; ma di squadre per la terza posizione ne rimangono 2.

Quindi, il numero totale di disposizioni semplici di classe 3 di un insieme di 4 elementi è $4 \cdot 3 \cdot 2 = 24$ .

Possiamo generalizzare il procedimento appena descritto. Il numero di disposizioni semplici di classe $k$ di un insieme di $n$ elementi è dato da:

D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)

Questo risultato può essere sintetizzato adoperando la funzione fattoriale. Infatti, se prendiamo la formula di sopra:

D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)

e moltiplichiamo e dividiamo per $(n-k)!$ , otteniamo:

= \frac{n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1) \cdot (n-k)!}{(n-k)!}

= \frac{n!}{(n-k)!}

Quindi:

Definizione

Numero di Disposizioni Semplici

Dato un insieme di $n$ elementi, il numero di disposizioni semplici di classe $k$ , con $0 < k \leq n$ , è dato da:

D_{n,k} = \frac{n!}{(n-k)!}

Esempi

Vediamo, adesso, alcuni esempi.

Esempio

Serie A

La Serie A italiana di calcio è composta attualmente (nel 2024) da 20 squadre. Di queste, le prime 4 classificate si qualificano per la Champions League.

Quante sono le possibili classifiche delle prime 4 squadre?

Per rispondere, sappiamo che l'insieme di partenza è composto da $n=20$ elementi o squadre. Di queste, vogliamo selezionare sequenze di 4 elementi o squadre, quindi $k=4$ .

Il numero di disposizioni semplici di classe 4 di un insieme di 20 elementi è dato da:

D_{20,4} = \frac{20!}{(20-4)!} = \frac{20!}{16!}

= 20 \cdot 19 \cdot 18 \cdot 17

= 116280

Quindi, il numero di possibili classifiche delle prime 4 squadre è 116280.

Esempio

Codici Alfanumerici

Supponiamo di voler realizzare un sistema che cataloga i prodotti di un magazzino assegnando a ciascuno un codice particolare.

Tale codice è composto da

3 cifre numeriche tutte diverse tra loro;
2 lettere dell'alfabeto, sempre diverse tra loro.

Ad esempio, alcuni codici validi possono essere:

123AB
456CD
789EF

Quanti sono i possibili codici che possiamo realizzare?

Dobbiamo scomporre il problema in due parti:

Calcolare il numero di disposizioni semplici di 3 cifre numeriche diverse tra loro;
Calcolare il numero di disposizioni semplici di 2 lettere dell'alfabeto diverse tra loro.

Per il primo punto, abbiamo un insieme di 10 elementi (i numeri da 0 a 9) e vogliamo selezionare sequenze di 3 elementi, quindi $n=10$ e $k=3$ . Il numero di disposizioni semplici di classe 3 di un insieme di 10 elementi è dato da:

D_{10,3} = \frac{10!}{(10-3)!} = \frac{10!}{7!}

= 10 \cdot 9 \cdot 8

= 720

Per il secondo punto, abbiamo un insieme di 26 elementi (le lettere dell'alfabeto) e vogliamo selezionare sequenze di 2 elementi, quindi $n=26$ e $k=2$ . Il numero di disposizioni semplici di classe 2 di un insieme di 26 elementi è dato da:

D_{26,2} = \frac{26!}{(26-2)!} = \frac{26!}{24!}

= 26 \cdot 25

= 650

Il numero totale di possibili codici è dato dal prodotto dei due numeri calcolati:

D_{10,3} \cdot D_{26,2} = 720 \cdot 650 = 468000

Quindi, il numero di possibili codici che possiamo realizzare è 468000.

Esempio

Numeri di 4 Cifre Senza Ripetizioni

Quanti sono i possibili numeri di 4 cifre che possiamo formare utilizzando le cifre da 0 a 9, senza ripetizioni?

Questo problema, a prima vista, può risultare banale. Infatti, sembrerebbe che il numero di possibili numeri sia dato da:

D_{10,4} = \frac{10!}{(10-4)!} = \frac{10!}{6!} = 5040

Tuttavia, questo risultato non è corretto.

Nel computo totale abbiamo, purtroppo, inserito anche quei numeri che iniziano per 0. Ma tali numeri non sono numeri di 4 cifre, bensì numeri di 3 cifre.

Per ottenere il risultato finale, allora, dobbiamo sottrarre il numero di numeri che iniziano per 0. Tale valore è dato dal numero di disposizioni semplici di classe 3 di un insieme di 9 elementi (le cifre da 1 a 9), ossia:

D_{9,3} = \frac{9!}{(9-3)!} = \frac{9!}{6!} = 504

Per cui il risultato finale è dato da:

D_{10,4} - D_{9,3} = 5040 - 504 = 4536

Quindi, il numero di possibili numeri di 4 cifre che possiamo formare utilizzando le cifre da 0 a 9, senza ripetizioni, è 4536.

In Sintesi

Le disposizioni semplici sono sequenze ordinate di $k$ elementi di un insieme di $n$ elementi, in cui ogni elemento compare una sola volta. Il numero di disposizioni semplici di classe $k$ di un insieme di $n$ elementi è dato da:

D_{n,k} = \frac{n!}{(n-k)!}

Questo risultato può essere ottenuto anche tramite la formula:

D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)

Le disposizioni semplici sono utili per calcolare il numero di possibili sequenze di elementi di un insieme, in cui l'ordine degli elementi è importante e ogni elemento compare una sola volta.

Nella prossima lezione studieremo, invece, le Disposizioni con Ripetizione, ossia quelle sequenze ordinate in cui gli elementi possono comparire più volte.

Lezione Precedente Indice del capitolo