85 Disposizioni semplici e con ripetizione

“

L’arte combinatoria è l’arte di scoprire tutte le possibili combinazioni di certe cose.”

— Gottfried Wilhelm Leibniz, Dissertatio de Arte Combinatoria (1666)

____________________________________________________________________________________

85.1 Introduzione motivazionale

Nel capitolo precedente abbiamo contato gli ordinamenti di $n$ oggetti distinti (permutazioni, 84): in tutti i $P_n = n!$ casi, gli oggetti coinvolti erano tutti gli $n$ disponibili.

Adesso passiamo a un caso più generale: cosa succede se vogliamo scegliere e ordinare solo $k$ oggetti tra gli $n$ disponibili, con $k \leq n$? La risposta è data dalle disposizioni. Esempi tipici:

In entrambi i casi, l’ordine delle scelte è importante: $(A, B, C)$ e $(C, B, A)$ contano come disposizioni diverse. È questa la differenza chiave con le combinazioni, in cui l’ordine non conta (86).

85.2 Disposizioni semplici

Definizione 85.1 — Disposizione semplice

Siano $n, k$ interi con $1 \leq k \leq n$. Si chiama disposizione semplice di $n$ oggetti distinti presi $k$ alla volta una sequenza ordinata di $k$ oggetti, scelti tra gli $n$ a disposizione, senza ripetizioni (cioè ogni oggetto compare al massimo una volta nella sequenza).

Il numero di disposizioni semplici si indica con $D_{n,k}$.

Esempio 85.1 — Le 6 disposizioni di 3 oggetti presi 2 alla volta

Tre oggetti $A, B, C$, presi a due a due. Le disposizioni semplici sono:

\[ AB,\ BA,\ AC,\ CA,\ BC,\ CB. \]

Totale: $6$.

Nota: $AB \neq BA$ — l’ordine conta. Quindi le disposizioni $AB$ e $BA$ vanno contate entrambe.

Nota — Differenza con permutazioni e combinazioni

Permutazione: ordinamento di tutti gli $n$ oggetti (caso $k = n$).
Disposizione semplice: ordinamento di una parte (di $k$ oggetti su $n$).
Combinazione: scelta non ordinata di $k$ su $n$ — l’ordine non conta (86).

Esempio: con $3$ oggetti $A, B, C$ presi a $2$ a $2$, le disposizioni sono $6$ ($AB, BA, AC, CA, BC, CB$), mentre le combinazioni sono solo $3$ ($\{A,B\}, \{A,C\}, \{B,C\}$). Ogni combinazione genera $2! = 2$ disposizioni.

85.3 Calcolo del numero di disposizioni

Teorema 85.1 — Numero delle disposizioni semplici

Per ogni $1 \leq k \leq n$:

\[ D_{n,k} = n\cdot (n - 1)\cdot (n - 2)\cdots (n - k + 1) = \frac {n!}{(n - k)!}. \]

\[ \boxed {\ D_{n,k} = \frac {n!}{(n-k)!} = n\cdot (n-1)\cdots (n-k+1)\ } \]

($k$ fattori, da $n$ verso il basso).

Dimostrazione (principio del conteggio). Costruiamo una disposizione riempiendo le $k$ posizioni una alla volta:

Per il principio del conteggio: $D_{n,k} = n\cdot (n-1)\cdots (n-k+1)$. Moltiplicando e dividendo per $(n-k)!$ si ottiene la forma in fattoriali $n!/(n-k)!$.

Nota — Casi particolari

$D_{n,1} = n$ (sequenze di un solo elemento: $n$ scelte).
$D_{n,n} = n!/(0)! = n! = P_n$ (le disposizioni di $n$ presi $n$ alla volta sono le permutazioni).
$D_{n,0} = 1$ per convenzione (la sequenza vuota).

Esempio 85.2 — Medaglie olimpiche

$8$ atleti gareggiano per le $3$ medaglie (oro, argento, bronzo). In quanti modi possono essere assegnate?

Soluzione. Disposizione semplice di $8$ presi $3$ alla volta:

\[ D_{8,3} = 8\cdot 7\cdot 6 = 336. \]

Esempio 85.3 — Elezione di un direttivo

In un’associazione di $20$ soci si devono eleggere presidente, vicepresidente, segretario. In quanti modi?

Soluzione. Tre cariche distinte $\Rightarrow $ l’ordine conta. Disposizione di $20$ presi $3$:

\[ D_{20,3} = 20\cdot 19\cdot 18 = 6840. \]

Esempio 85.4 — Anagrammi parziali

Quante “parole” di $4$ lettere distinte si possono formare con le $5$ vocali $\{A, E, I, O, U\}$?

Soluzione. $D_{5,4} = 5\cdot 4\cdot 3\cdot 2 = 120$.

Esempio 85.5 — Calcolo con fattoriali

$D_{10, 4} = \dfrac {10!}{6!} = \dfrac {10\cdot 9\cdot 8\cdot 7\cdot 6!}{6!} = 10\cdot 9\cdot 8\cdot 7 = 5040$.

(Nota: si semplifica subito il $6!$ a numeratore e denominatore, evitando di calcolare $10! = 3628800$.)

85.4 Disposizioni con ripetizione

Definizione 85.2 — Disposizione con ripetizione

Siano $n, k$ interi con $n \geq 1$ e $k \geq 0$ (non c’è limitazione $k \leq n$!). Si chiama disposizione con ripetizione di $n$ oggetti presi $k$ alla volta una sequenza ordinata di $k$ oggetti scelti tra gli $n$, ammettendo ripetizioni (ogni oggetto può comparire più volte).

Il numero di disposizioni con ripetizione si indica con $D'_{n,k}$.

Teorema 85.2 — Numero delle disposizioni con ripetizione

\[ D'_{n,k} = n^k. \]

\[ \boxed {\ D'_{n,k} = n^k\ }\qquad (n \geq 1,\ k \geq 0). \]

Dimostrazione. Per ognuna delle $k$ posizioni nella sequenza, abbiamo tutti e $n$ gli oggetti a disposizione (perché le ripetizioni sono ammesse). Per il principio del conteggio: $n\cdot n\cdots n = n^k$ ( $k$ fattori).

Nota — Differenze chiave con le disposizioni semplici

Con ripetizione: $k$ può essere qualsiasi (anche $> n$). Senza ripetizione: $k \leq n$.
Con ripetizione: ogni scelta è indipendente — $n$ alternative ovunque. Senza ripetizione: le scelte si riducono a ogni passo.

Esempio 85.6 — PIN

Quanti PIN diversi di $4$ cifre si possono comporre (cifre $0$-$9$, ripetizioni ammesse)?

Soluzione. $D'_{10, 4} = 10^4 = 10000$.

(Se imponessimo cifre tutte diverse, sarebbero $D_{10, 4} = 10\cdot 9\cdot 8\cdot 7 = 5040$ — circa la metà.)

Esempio 85.7 — Targhe automobilistiche

Le targhe automobilistiche italiane attuali hanno la forma $LL\,NNN\,LL$ (2 lettere + 3 cifre + 2 lettere), con $22$ lettere ammesse (sono escluse alcune) e $10$ cifre.

Quante targhe diverse si possono fare?

Soluzione.

\[ D'_{22, 4}\cdot D'_{10, 3} = 22^4\cdot 10^3 = 234256\cdot 1000 = 234256000. \]

Esempio 85.8 — Lanci ripetuti di un dado

Si lancia un dado a $6$ facce per $4$ volte di seguito. Quante sequenze di esiti diverse sono possibili?

Soluzione. Ogni lancio è una scelta indipendente tra $6$ esiti: $D'_{6, 4} = 6^4 = 1296$.

Esempio 85.9 — Password

Una password di $8$ caratteri scelti tra $26$ lettere minuscole, $26$ maiuscole e $10$ cifre (totale $62$ caratteri) ha

\[ 62^8 = 218340105584896 \approx 2.2\times 10^{14} \]

possibilità diverse. Aggiungendo $10$ simboli speciali (es. $\$, !, @, \ldots $, totale $72$ caratteri): $72^8 \approx 7.2\times 10^{14}$. Questa esplosione combinatoria è la base della sicurezza delle password.

Tabella riassuntiva

Nota — Confronto tra permutazioni e disposizioni

\[ \begin {array}{l|c|l} \text {Tipo} & \text {Formula} & \text {Quando si usa} \\ \hline P_n = D_{n,n} & n! & \text {ordinamento di tutti gli $n$ oggetti} \\ D_{n,k}\ (k \leq n) & n!/(n-k)! & \text {scelta ordinata di $k$ su $n$, senza ripetizioni} \\ D'_{n,k}\ (\text {ogni $k$}) & n^k & \text {scelta ordinata di $k$ su $n$, con ripetizioni} \\ P_n^{(n_1,\ldots ,n_k)} & \dfrac {n!}{n_1!\cdots n_k!} & \text {permutazione con elementi ripetuti} \end {array} \]

85.5 Esempi svolti

Esempio 85.10 — Numeri di $3$ cifre senza ripetizione

Quanti numeri naturali di $3$ cifre, senza cifre ripetute, si possono formare con $\{0, 1, 2, 3, 4, 5\}$?

Soluzione. Attenzione: il numero non può iniziare con $0$. Procedo a passi:

Prima cifra (centinaia): $5$ scelte (tutte tranne $0$);
Seconda cifra (decine): $5$ scelte (le $5$ rimaste, incluso lo $0$);
Terza cifra (unità): $4$ scelte.

Totale: $5\cdot 5\cdot 4 = 100$.

(Se fossero ammesse cifre ripetute: $5\cdot 6\cdot 6 = 180$.)

Esempio 85.11 — Sequenze binarie

Quante sequenze binarie di lunghezza $5$ esistono?

Soluzione. $D'_{2, 5} = 2^5 = 32$. (Sono $00000, 00001, 00010, \ldots , 11111$.)

Esempio 85.12 — Codice di sicurezza

Un codice di sicurezza è costituito da $4$ cifre seguite da $2$ lettere (su un alfabeto di $26$ lettere). Ripetizioni ammesse. Quanti codici diversi sono possibili?

Soluzione. $10^4 \cdot 26^2 = 10000\cdot 676 = 6760000$.

Esempio 85.13 — Numero di disposizioni con condizione

Quante disposizioni semplici di $7$ oggetti distinti, presi $4$ alla volta, contengono un certo oggetto $A$?

Soluzione. Strategia: prima fisso la posizione di $A$ (4 scelte), poi completo con le altre $3$ posizioni con disposizioni semplici di $6$ oggetti (gli altri $6$, escluso $A$) presi $3$ alla volta:

\[ 4 \cdot D_{6, 3} = 4 \cdot (6\cdot 5\cdot 4) = 4\cdot 120 = 480. \]

Esempio 85.14 — Verifica della formula

Verificare che $D_{n,n} = P_n$, sostituendo $k = n$ nella formula $D_{n,k} = n!/(n-k)!$.

Soluzione.

\[ D_{n,n} = \frac {n!}{(n-n)!} = \frac {n!}{0!} = \frac {n!}{1} = n! = P_n. \checkmark \]

Esempio 85.15 — Squadre di calcio

Un allenatore deve scegliere e disporre la formazione titolare di $11$ giocatori da una rosa di $22$ (uno per ogni posizione tattica, che sono tutte diverse). Quanti schieramenti possibili?

Soluzione. $D_{22, 11} = \dfrac {22!}{11!}$. Numericamente:

\[ 22\cdot 21\cdot 20\cdot 19\cdot 18\cdot 17\cdot 16\cdot 15\cdot 14\cdot 13\cdot 12 \approx 1.13\times 10^{13}. \]

Cioè più di dieci mila miliardi di schieramenti possibili.

85.6 Esercizi proposti

Esercizio 85.1

1.

Calcola:

(a) $D_{6, 3}$;
(b) $D_{10, 5}$;
(c) $D_{5, 2}$;
(d) $D_{15, 4}$.

2.

Verifica che $D_{n,k} = D_{n,k-1}\cdot (n - k + 1)$ (formula ricorsiva).

3.

Calcola:

(a) $D'_{4, 5}$;
(b) $D'_{6, 2}$;
(c) $D'_{10, 6}$;
(d) $D'_{2, 10}$.

4.

In una gara con $10$ partecipanti, in quanti modi si possono assegnare le prime $3$ posizioni?

5.

In un’aula con $30$ studenti, in quanti modi si possono nominare un capoclasse, un vicecapoclasse e un cassiere (tutti distinti)?

6.

Quante parole di $5$ lettere distinte si possono formare con le $21$ lettere dell’alfabeto italiano?

7.

Quante parole di $5$ lettere (anche con ripetizione) si possono formare con le $21$ lettere?

8.

Un dado a $6$ facce viene lanciato $5$ volte. Quante sequenze di esiti diverse?

9.

Quanti numeri di $4$ cifre si possono formare con le cifre $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (senza usare lo zero) con: (a) ripetizioni ammesse; (b) senza ripetizioni?

10.

Quanti numeri di $5$ cifre tutte diverse si possono formare con $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$?

11.

Quante targhe di formato $LLNNN$ ($2$ lettere $+$ $3$ cifre) esistono usando $22$ lettere e $10$ cifre, con ripetizioni ammesse?

12.

Una password è composta da $6$ caratteri scelti tra $26$ lettere maiuscole e $10$ cifre. Quante password esistono? Confronta con quelle di $8$ caratteri.

13.

Quante anagrammi parziali di $4$ lettere si possono formare con le lettere distinte di “ROMA”?

14.

(Discussione.) Spiega perché $D'_{n, k}$ può essere calcolato anche per $k > n$, mentre $D_{n, k}$ richiede $k \leq n$.

15.

(Sfida.) Quanti numeri di $5$ cifre tutte distinte si possono formare con le cifre $\{0, 1, 2, 3, 4, 5\}$? (Attenzione: la prima cifra non può essere $0$.)

85.7 Riepilogo del capitolo

Riepilogo

Disposizione: scelta ordinata di $k$ oggetti tra $n$.
Disposizione semplice ($k \leq n$, senza ripetizione):
\[ D_{n,k} = n\cdot (n-1)\cdot (n-2)\cdots (n-k+1) = \frac {n!}{(n-k)!}. \]

Esempio archetipo: assegnare $k$ medaglie a $n$ atleti.
Disposizione con ripetizione ($k$ qualsiasi, ripetizioni ammesse):
\[ D'_{n,k} = n^k. \]

Esempio archetipo: comporre un PIN di $k$ cifre.
Casi notevoli:
- $D_{n,n} = n! = P_n$ (le disposizioni di $n$ presi $n$ sono le permutazioni);
- $D_{n,1} = n$;
- $D_{n,0} = 1$ (convenzione);
- $D'_{n,0} = 1$ (sequenza vuota).
Quando usare quale: l’ordine delle scelte conta sempre (altrimenti sarebbero combinazioni, 86); la differenza tra le due varianti sta nella ripetibilità degli oggetti.
Approccio costruttivo: ogni problema combinatorio elementare si risolve applicando il principio fondamentale del conteggio, scelta dopo scelta. Le formule $D_{n,k}$ e $D'_{n,k}$ sono “solo” le formule generali di questa procedura.
Prossimo passo: scelte non ordinate di $k$ su $n$ — le combinazioni, e l’introduzione del coefficiente binomiale $\binom {n}{k}$ (86).

Capitolo 85 Disposizioni semplici e con ripetizione