16.3. Disposizioni#

Per disposizione di \(n\) oggetti distinti in \(k\) posti si intende una qualsiasi sequenza di \(k\) simboli, ognuno rappresentante uno degli oggetti. Pertanto, il tipo di raggruppamento che corrisponde alle disposizioni dipende dall'ordine utilizzato, e gli oggetti devono essere tra loro distinguibili. Si parla di disposizioni con ripetizione quando un simbolo può apparire più volte nella sequenza, e di disposizioni semplici altrimenti.

16.3.1. Disposizioni con ripetizione#

Nelle disposizioni con ripetizione è possibile utilizzare uno stesso oggetto più di una volta, come specificato dalla definizione che segue.

Definizione 4 (Disposizione con ripetizione)

Fissato un insieme di \(n\) oggetti \(A = \{ a_1,\dots a_n \}\) e un numero \(k \in \mathbb N\), una disposizione con ripetizione è una sequenza \((a_{i_1}, \dots, a_{i_k})\), dove per ogni \(j = 1, \dots, k\) si ha \(i_j \in \{1, \dots, n\}\) e \(a_{i_j} \in A\). Indichiamo con \(D_{n, k}\) il numero di possibili disposizioni con ripetizione di \(n\) oggetti in \(k\) posti.

Esempio 11 (un esempio di disposizione con ripetizione)

Il Dipartimento H deve pianificare una sequenza di tre missioni giornaliere, rispettivamente la mattina, il pomeriggio e la sera. Per ogni missione può essere inviato uno qualsiasi dei quattro membri degli Alpha Flight: Guardian, Sasquatch, Northstar e Aurora, che indicheremo rispettivamente con le iniziali \(G\), \(S\), \(N\) e \(A\). Se ogni membro può essere dispiegato in più missioni nella stessa giornata, a ogni pianificazione corrisponde una disposizione con ripetizione degli \(n = 4\) oggetti nell'insieme \(\{G, S, N, A \}\) (i membri della squadra) in \(k = 3\) posti (i turni giornalieri). Per esempio, le tre seguenti situazioni descrivono pianificazioni (e disposizioni) differenti:

  • \((G, S, N)\) indica che Guardian, Sasquatch e Northstar svolgono rispettivamente i turni mattutino, pomeridiano e serale;

  • \((S, N, G)\), inverte i turni del mattino e del pomeriggio rispetto al punto precedente;

  • \((A, G, G)\) coinvolge Aurora al mattino e Guardian nei due turni successivi.

Calcolare il numero \(D_{n, k}\) di possibili disposizioni con ripetizione è abbastanza facile, considerando il numero di scelte possibili per ognuno dei \(k\) posti:

  • l'oggetto da inserire nel primo posto può essere scelto in \(n\) modi diversi;

  • il numero di scelte continua a essere uguale a \(n\) anche per il secondo posto, dal momento che è possibile riutilizzare l'oggetto selezionato per la prima posizione;

  • chiaramente, vi saranno \(n\) scelte possibili per tutti i rimanenti posti.

Applicando il principio fondamentale del calcolo combinatorio si ottiene pertanto che

\[ D_{n, k} = \underbrace{n \cdot n \dots \cdot n}_{k \text{ volte}} = n^k \enspace. \]

Lo stesso risultato si ottiene notando che l'insieme di tutte le disposizioni è il prodotto cartesiano \(A^k\) di \(A\) con se stesso, calcolato \(k\) volte, e ricordando che \(| A^k | = |A|^k = n^k\).

Esempio 12 (un esempio di disposizione con ripetizione)

Riprendendo l’Esempio 11, il numero totale di pianificazioni giornaliere distinte è uguale a \(D_{4,3} = 4^3 = 64\), come evidenziato nella 14, dove le colonne M, P ed S fanno riferimento ai turni del mattino, del pomeriggio e della sera, rispettivamente.

Tabella 14 Le possibili disposizioni con ripetizione di \(4\) oggetti in \(3\) posti che descrivono i turni degli Alpha Flight; le corrispondenti disposizioni semplici sono evidenziate in grassetto.#

#

M

P

S

#

M

P

S

#

M

P

S

1

\(G\)

\(G\)

\(G\)

2

\(G\)

\(G\)

\(S\)

3

\(G\)

\(G\)

\(N\)

4

\(G\)

\(G\)

\(A\)

5

\(G\)

\(S\)

\(G\)

6

\(G\)

\(S\)

\(S\)

7

\(\boldsymbol{G}\)

\(\boldsymbol{S}\)

\(\boldsymbol{N}\)

8

\(\boldsymbol{G}\)

\(\boldsymbol{S}\)

\(\boldsymbol{A}\)

9

\(G\)

\(N\)

\(G\)

10

\(\boldsymbol{G}\)

\(\boldsymbol{N}\)

\(\boldsymbol{S}\)

11

\(G\)

\(N\)

\(N\)

12

\(\boldsymbol{G}\)

\(\boldsymbol{N}\)

\(\boldsymbol{A}\)

13

\(G\)

\(A\)

\(G\)

14

\(\boldsymbol{G}\)

\(\boldsymbol{A}\)

\(\boldsymbol{S}\)

15

\(\boldsymbol{G}\)

\(\boldsymbol{A}\)

\(\boldsymbol{N}\)

16

\(G\)

\(A\)

\(A\)

17

\(S\)

\(G\)

\(G\)

18

\(S\)

\(G\)

\(S\)

19

\(\boldsymbol{S}\)

\(\boldsymbol{G}\)

\(\boldsymbol{N}\)

20

\(\boldsymbol{S}\)

\(\boldsymbol{G}\)

\(\boldsymbol{A}\)

21

\(S\)

\(S\)

\(G\)

22

\(S\)

\(S\)

\(S\)

23

\(S\)

\(S\)

\(N\)

24

\(S\)

\(S\)

\(A\)

25

\(\boldsymbol{S}\)

\(\boldsymbol{N}\)

\(\boldsymbol{G}\)

26

\(S\)

\(N\)

\(S\)

27

\(S\)

\(N\)

\(N\)

28

\(\boldsymbol{S}\)

\(\boldsymbol{N}\)

\(\boldsymbol{A}\)

29

\(\boldsymbol{S}\)

\(\boldsymbol{A}\)

\(\boldsymbol{G}\)

30

\(S\)

\(A\)

\(S\)

31

\(\boldsymbol{S}\)

\(\boldsymbol{A}\)

\(\boldsymbol{N}\)

32

\(S\)

\(A\)

\(A\)

33

\(N\)

\(G\)

\(G\)

34

\(\boldsymbol{N}\)

\(\boldsymbol{G}\)

\(\boldsymbol{S}\)

35

\(N\)

\(G\)

\(N\)

36

\(\boldsymbol{N}\)

\(\boldsymbol{G}\)

\(\boldsymbol{A}\)

37

\(\boldsymbol{N}\)

\(\boldsymbol{S}\)

\(\boldsymbol{G}\)

38

\(N\)

\(S\)

\(S\)

39

\(N\)

\(S\)

\(N\)

40

\(\boldsymbol{N}\)

\(\boldsymbol{S}\)

\(\boldsymbol{A}\)

41

\(N\)

\(N\)

\(G\)

42

\(N\)

\(N\)

\(S\)

43

\(N\)

\(N\)

\(N\)

44

\(N\)

\(N\)

\(A\)

45

\(\boldsymbol{N}\)

\(\boldsymbol{A}\)

\(\boldsymbol{G}\)

46

\(\boldsymbol{N}\)

\(\boldsymbol{A}\)

\(\boldsymbol{S}\)

47

\(N\)

\(A\)

\(N\)

48

\(N\)

\(A\)

\(A\)

49

\(A\)

\(G\)

\(G\)

50

\(\boldsymbol{A}\)

\(\boldsymbol{G}\)

\(\boldsymbol{S}\)

51

\(\boldsymbol{A}\)

\(\boldsymbol{G}\)

\(\boldsymbol{N}\)

52

\(A\)

\(G\)

\(A\)

53

\(\boldsymbol{A}\)

\(\boldsymbol{S}\)

\(\boldsymbol{G}\)

54

\(A\)

\(S\)

\(S\)

55

\(\boldsymbol{A}\)

\(\boldsymbol{S}\)

\(\boldsymbol{N}\)

56

\(A\)

\(S\)

\(A\)

57

\(\boldsymbol{A}\)

\(\boldsymbol{N}\)

\(\boldsymbol{G}\)

58

\(\boldsymbol{A}\)

\(\boldsymbol{N}\)

\(\boldsymbol{S}\)

59

\(A\)

\(N\)

\(N\)

60

\(A\)

\(N\)

\(A\)

61

\(A\)

\(A\)

\(G\)

62

\(A\)

\(A\)

\(S\)

63

\(A\)

\(A\)

\(N\)

64

\(A\)

\(A\)

\(A\)

16.3.2. Disposizioni semplici#

Nelle disposizioni con ripetizione, ogni oggetto può comparire più volte nella sequenza. Quando invece ogni oggetto può essere inserito in una sola posizione, si parla di disposizioni semplici, o disposizioni senza ripetizione. In questo caso è quindi necessario imporre \(k \leq n\), perché dopo che tutti gli \(n\) oggetti sono stati inseriti in una sequenza non ve ne sono altri che possono essere scelti ulteriormente.

Definizione 5 (Disposizione semplice)

Fissato un insieme di \(n\) oggetti \(A = \{ a_1,\dots a_n \}\) e un numero \(k \in \mathbb N\), con \(k \leq n\), una disposizione semplice è una sequenza \((a_{i_1}, \dots, a_{i_k})\), dove per ogni \(j = 1, \dots, k\) si ha \(i_j \in \{1, \dots, n\}\) e \(a_{i_j} \in A\), e per ogni \(j, l = 1, \dots, k\) con \(j \neq l\) si ha \(a_{i_j} \neq a_{i_l}\). Indichiamo con \(d_{n, k}\) il numero di possibili disposizioni semplici di \(n\) oggetti in \(k\) posti.

Esempio 13

Se nell’Esempio 11 non fosse possibile assegnare più di un turno giornaliero a una stessa persona, le sequenze come \((A, G, G)\) non sarebbero più ammesse, e a ogni turnazione corrisponderebbe una e una sola disposizione semplice di quattro oggetti in tre posti.

Per calcolare il numero \(d_{n, k}\) di disposizioni semplici di \(n\) oggetti in \(k\) posti, possiamo seguire un ragionamento analogo a quello delle permutazioni semplici:

  • l'oggetto da inserire nel primo posto può esere scelto in \(n\) modi diversi;

  • il secondo posto può essere riempito in \(n - 1\) modi possibili, non potendo più riusare l'oggetto selezionato per la prima posizione;

  • la terza scelta può essere fatta in \(n - 2\) modi, e così via fino all'ultimo posto, che sarà riempibile scegliendo tra \(n - k + 1\) oggetti.

Applicando il principio fondamentale del calcolo combinatorio si ottiene che

\[d_{n, k} = n (n-1) \ldots (n-k+1) = n (n-1) \ldots (n-k+1) \cdot \frac{(n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} \enspace.\]

Esempio 14

La 14 evidenzia in grassetto le pianificazioni dell’Esempio 13, il cui numero è uguale a \(d_{4, 3} = 4 \cdot 3 \cdot 2 = 24\).

Quando \(k=n\), per formare una disposizione bisogna utilizzare tutti gli elementi di \(A\), quindi le permutazioni semplici sono un caso particolare di disposizioni semplici. Coerentemente, si ha che \(d_{n, n} = n!/0! = n! = p_n\).

Vero o falso?#

Analizzate ciascuna delle seguenti affermazioni, che riguardano le disposizioni, e dite se è vera o falsa, motivando il vostro ragionamento. Cliccate su di essa per visualizzare la risposta corretta.

Nelle disposizioni, due sequenze con gli stessi elementi in ordine diverso sono considerate distinte.

Vera. Le disposizioni sono sequenze ordinate: l'ordine degli elementi è parte integrante della configurazione. Nell' Esempio 11, per esempio, \((G, S, N)\) e \((S, N, G)\) descrivono pianificazioni diverse perché assegnano i turni in ordine differente, sebbene coinvolgano gli stessi tre eroi. Questa dipendenza dall'ordine distingue le disposizioni dalle combinazioni.

Il numero di disposizioni con ripetizione di \(n\) oggetti in \(k\) posti è \(n^k\).

Vera. Per il principio fondamentale del calcolo combinatorio, ogni posto può essere riempito in \(n\) modi indipendenti (la ripetizione consente di riutilizzare qualunque oggetto). Il numero totale di sequenze è quindi \(\underbrace{n \cdot n \cdots n}_{k} = n^k\). Nell' Esempio 11, \(4\) eroi in \(3\) turni producono \(D_{4,3} = 4^3 = 64\) pianificazioni distinte.

Per le disposizioni semplici è necessario che il numero di posti non superi il numero di oggetti disponibili (\(k \leq n\)).

Vera. Nelle disposizioni semplici ogni oggetto può comparire al più una volta nella sequenza. Una volta inseriti tutti gli \(n\) oggetti, non ve ne sono altri da selezionare, quindi non è possibile riempire più di \(n\) posizioni. La Definizione 5 impone esplicitamente \(k \leq n\).

Il numero di disposizioni con ripetizione di \(n\) oggetti in \(k\) posti è \(n \cdot k\).

Falsa. La formula corretta è \(D_{n,k} = n^k\), non \(n \cdot k\). Per il principio fondamentale, si moltiplicano le \(k\) scelte indipendenti (ognuna con \(n\) opzioni), ottenendo \(n^k\). La formula \(n \cdot k\) sarebbe la somma di \(k\) copie di \(n\), che non ha corrispondenza con il conteggio delle sequenze. Ad esempio, \(D_{4,3} = 4^3 = 64 \neq 4 \cdot 3 = 12\).

Con \(4\) oggetti e \(3\) posti, le disposizioni con ripetizione e quelle semplici producono lo stesso numero di sequenze.

Falsa. Con \(n = 4\) e \(k = 3\): le disposizioni con ripetizione sono \(D_{4,3} = 4^3 = 64\), mentre quelle semplici sono \(d_{4,3} = 4 \cdot 3 \cdot 2 = 24\). Come mostrato nella 14, le \(64\) righe della tabella includono le \(24\) disposizioni semplici (in grassetto) più \(40\) sequenze aggiuntive che contengono almeno una ripetizione.

Le permutazioni semplici di \(n\) oggetti sono un caso particolare di disposizioni semplici, ottenuto ponendo \(k = n\).

Vera. Quando \(k = n\), una disposizione semplice deve usare tutti gli \(n\) oggetti disponibili senza ripetizioni, cioè è esattamente una permutazione semplice. Coerentemente, si ha \(d_{n,n} = n!/(n-n)! = n!/0! = n! = p_n\): la formula delle disposizioni semplici con \(k = n\) coincide con quella delle permutazioni.

16.3.3. Esercizi#

Esercizio 57 (•)

Il sistema informatico dello S.H.I.E.L.D. genera codici di accesso formati da cinque caratteri, ognuno scelto tra otto simboli speciali, con possibilità di ripetizione. Quanti codici distinti è possibile generare?

Esercizio 58 (••)

La Guardia Reale del Wakanda deve pianificare le ronde dei prossimi tre giorni, selezionando per ogni giorno un guerriero diverso tra i sei disponibili. In quanti modi si può organizzare il calendario?

Esercizio 59 (••)

I Defenders devono coprire quattro turni distinti in una giornata (alba, mattina, pomeriggio, notte), scegliendo ogni volta un membro diverso tra nove candidati. In quanti modi si può compilare la turnazione?

Esercizio 60 (••)

I membri dei Guardiani della galassia — Star-Lord, Gamora, Drax, Rocket e Groot — devono assegnare tre ruoli distinti: portavoce, vice-portavoce e archivista. Quante assegnazioni sono possibili, sapendo che Groot non può ricoprire il ruolo di portavoce, essendo il suo linguaggio limitato all’espressione «Io sono Groot»?

Esercizio 61 (••)

Per una missione degli Young Avengers si devono assegnare tre ruoli distinti (comando, ricognizione, supporto) a sette eroi. In quanti modi si possono assegnare i ruoli se Patriot e Wiccan non possono essere entrambi selezionati?

Esercizio 62 (•••)

Gli Avengers devono pianificare una sequenza di quattro missioni consecutive, scegliendo ogni volta un membro diverso tra Iron Man, Thor, Capitan America, Vedova Nera e Occhio di Falco. Iron Man deve partecipare alla prima o all'ultima missione. Quante pianificazioni sono possibili?

16.3.4. Concetti fondamentali#

Pensate ai concetti fondamentali illustrati in questo paragrafo ed elencateli. Nella lista qui sotto sono già presenti gli stessi concetti, ma nascosti. Cliccate sul pulsante per mostrarli sotto forma di parole chiave, quindi confrontateli con la vostra lista. Provate infine a descrivere ciascun concetto con parole vostre.

Contenuti