84 Permutazioni semplici e con ripetizione

____________________________________________________________________________________

84.1 Introduzione motivazionale

Il calcolo combinatorio è la branca della matematica che si occupa di contare configurazioni di oggetti — senza enumerarle una per una. Quando una situazione coinvolge migliaia o milioni di possibilità (le mani di carte di un mazzo, gli anagrammi di una parola, le combinazioni del Lotto, le password possibili), enumerarle a mano è impensabile: serve una formula.

Le radici sono antiche — gli indiani Pingala (iii sec. a.C.) e Halāyudha (x sec.) avevano già il triangolo dei coefficienti binomiali, secoli prima di Pascal. Ma la sistematizzazione moderna comincia nel xvii sec. con il carteggio Pascal–Fermat (1654) sui problemi del gioco d’azzardo, e culmina con l’Ars Conjectandi di Jacob Bernoulli (pubblicato postumo nel 1713), il primo trattato organico di calcolo combinatorio e probabilità.

Esistono tre operazioni combinatorie fondamentali, ognuna delle quali tratteremo in un capitolo dedicato:

Teorema 84.1 — Principio fondamentale del conteggio

Se un’attività si decompone in $k$ scelte successive indipendenti, e la prima si può fare in $n_1$ modi, la seconda in $n_2$ modi, …, la $k$-esima in $n_k$ modi, allora il numero totale di modi diversi di completare l’attività è

\[ N = n_1 \cdot n_2 \cdot n_3 \cdots n_k. \]

Esempio 84.1 — Principio del conteggio

Quante parole di $3$ lettere si possono formare con l’alfabeto italiano (21 lettere)? $21\cdot 21\cdot 21 = 21^3 = 9261$.
Quante targhe automobilistiche italiane si possono fare? Schema $LL\,NNN\,LL$ (2 lettere $+$ 3 numeri $+$ 2 lettere) con 22 lettere ammesse: $22^4\cdot 10^3 = 234256000$.
Quanti PIN di $4$ cifre? $10^4 = 10000$.

84.2 Definizione di permutazione semplice

Definizione 84.1 — Permutazione semplice

Dato un insieme di $n$ oggetti distinti, si chiama permutazione semplice un loro qualsiasi ordinamento — cioè una loro disposizione in una sequenza ordinata.

Il numero di permutazioni semplici di $n$ oggetti si indica con $P_n$.

Esempio 84.2 — Le 6 permutazioni di tre oggetti

Le permutazioni di tre oggetti $A, B, C$ sono $6$:

\[ ABC,\ ACB,\ BAC,\ BCA,\ CAB,\ CBA. \]

Nota — Cosa cambia in una permutazione

In una permutazione, gli oggetti restano gli stessi: cambia solo il loro ordine. Per esempio, le sequenze $ABC$ e $BCA$ contengono gli stessi tre oggetti, ma in posizioni diverse.

(Confronto con disposizioni e combinazioni: in quelle non vengono utilizzati tutti gli oggetti.)

84.3 Calcolo del numero Pn = n!

Teorema 84.2 — Numero delle permutazioni semplici

Il numero di permutazioni semplici di $n$ oggetti distinti è

\[ P_n = n! = n\cdot (n - 1) \cdot (n - 2)\cdots 2 \cdot 1. \]

\[ \boxed {\ P_n = n!\ }\qquad (\text {con la convenzione $0! = 1$, $1! = 1$}). \]

Dimostrazione (col principio del conteggio). Costruiamo una permutazione riempiendo le $n$ posizioni una alla volta:

Per il principio fondamentale del conteggio: $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1 = n!$ .

Nota — Il fattoriale

La funzione $n!$ (“$n$ fattoriale”) è definita da:

\[ n! = n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1,\qquad 0! := 1. \]

La definizione $0! = 1$ è una convenzione che rende coerenti le formule combinatorie (e si giustifica anche con la formula ricorsiva $n! = n\cdot (n-1)!$ estesa a $n = 1$, che richiede $0! = 1$).

Valori notevoli:

\[ \begin {array}{c|c} n & n! \\ \hline 0 & 1 \\ 1 & 1 \\ 2 & 2 \\ 3 & 6 \\ 4 & 24 \\ 5 & 120 \\ 6 & 720 \\ 7 & 5040 \\ 10 & 3628800 \\ 20 & \approx 2.4\times 10^{18} \\ 100 & \approx 9.3\times 10^{157} \end {array} \]

La crescita è rapidissima: cresce più velocemente di ogni esponenziale $a^n$.

Nota — Formula di Stirling – cenni

Per $n$ grande, esiste un’approssimazione famosa (Stirling, 1730):

\[ n! \approx \sqrt {2\pi n}\left (\frac {n}{e}\right )^n. \]

Per esempio, per $n = 10$: $10! = 3628800$, mentre la formula di Stirling dà $\approx 3598696$ (errore $< 1\%$). La precisione migliora rapidamente al crescere di $n$. (Approfondimenti in 138.)

Esempio 84.3 — Permutazioni di libri

In quanti modi posso disporre $5$ libri diversi su uno scaffale?

Soluzione. $P_5 = 5! = 120$.

Esempio 84.4 — Permutazioni con vincoli

In quanti modi posso disporre $5$ libri in fila, con la condizione che un certo libro $A$ stia per primo?

Soluzione. La prima posizione è fissata da $A$. Restano $4$ libri da disporre nelle restanti $4$ posizioni: $P_4 = 4! = 24$.

Esempio 84.5 — Disposizione di persone a tavola

In quanti modi posso disporre $7$ persone attorno a un tavolo (in fila, non circolare)?

Soluzione. $P_7 = 7! = 5040$.

(Per il tavolo circolare la formula sarebbe diversa, perché le configurazioni che differiscono per una rotazione globale sono considerate uguali: $P_7^{\text {circ}} = 6! = 720$.)

Esempio 84.6 — Anagrammi senza lettere ripetute

Quanti anagrammi (sequenze di lettere) della parola “ROMA” esistono? Le quattro lettere sono distinte.

Soluzione. $P_4 = 4! = 24$. (Tra di essi, sono parole italiane sensate solo poche: “ROMA”, “AMOR”, … — gli altri sono anagrammi puri.)

84.4 Permutazioni con ripetizione

Il caso $P_n = n!$ presupposto che i $n$ oggetti fossero tutti distinti. Cosa accade se alcuni oggetti sono uguali? Allora due permutazioni che si ottengono scambiando solo oggetti uguali sono in realtà indistinguibili, e vanno contate una sola volta.

Teorema 84.3 — Permutazioni con ripetizione

Siano dati $n$ oggetti suddivisi in $k$ gruppi di oggetti indistinguibili tra loro:

$n_1$ oggetti di tipo 1,
$n_2$ oggetti di tipo 2,
…
$n_k$ oggetti di tipo $k$,

con $n_1 + n_2 + \cdots + n_k = n$. Il numero di permutazioni distinte è

\[ P_n^{(n_1, n_2, \ldots , n_k)} = \frac {n!}{n_1!\cdot n_2!\cdots n_k!}. \]

\[ \boxed {\ P_n^{(n_1, n_2, \ldots , n_k)} = \frac {n!}{n_1!\,n_2!\cdots n_k!}\ }\qquad \text {con $n_1 + n_2 + \cdots + n_k = n$.} \]

Dimostrazione. Se trattassimo gli $n$ oggetti come tutti distinti, avremmo $n!$ permutazioni. Ma per ogni “vera” permutazione distinguibile, esistono molte permutazioni “finte” che si ottengono scambiando tra loro gli oggetti del gruppo 1 ($n_1!$ scambi), quelli del gruppo 2 ($n_2!$ scambi), …, quelli del gruppo $k$ ($n_k!$ scambi). Per il principio del conteggio, le permutazioni che corrispondono allo stesso ordinamento distinguibile sono $n_1!\cdot n_2!\cdots n_k!$. Dividendo:

Nota — Coefficiente multinomiale

La formula $\dfrac {n!}{n_1!\,n_2!\cdots n_k!}$ si chiama coefficiente multinomiale. È una generalizzazione del coefficiente binomiale (86): per $k = 2$ e $n_1 + n_2 = n$, vale $\dfrac {n!}{n_1!\,n_2!} = \binom {n}{n_1}$.

Esempio 84.7 — Anagrammi di MAMMA

Quanti anagrammi distinti ha la parola “MAMMA”?

Soluzione. Cinque lettere, di cui $3$ M e $2$ A. Quindi

\[ P_5^{(3, 2)} = \frac {5!}{3!\cdot 2!} = \frac {120}{6\cdot 2} = 10. \]

Esempio 84.8 — Anagrammi di BANANA

Quanti anagrammi distinti ha “BANANA”?

Soluzione. Sei lettere: $1$ B, $3$ A, $2$ N. Quindi

\[ P_6^{(1, 3, 2)} = \frac {6!}{1!\cdot 3!\cdot 2!} = \frac {720}{1\cdot 6\cdot 2} = 60. \]

Esempio 84.9 — Anagrammi di MATEMATICA

Dieci lettere: $\{M, M, A, A, A, T, T, E, I, C\}$. Quindi $2$ M, $3$ A, $2$ T, e una E, una I, una C.

\[ P_{10}^{(2, 3, 2, 1, 1, 1)} = \frac {10!}{2!\cdot 3!\cdot 2!\cdot 1!\cdot 1!\cdot 1!} = \frac {3628800}{2\cdot 6\cdot 2} = \frac {3628800}{24} = 151200. \]

Esempio 84.10 — Sequenze binarie

Quante sequenze binarie di lunghezza $10$ esistono con esattamente $3$ uno e $7$ zero?

Soluzione. $P_{10}^{(3, 7)} = \dfrac {10!}{3!\cdot 7!} = \dfrac {3628800}{6\cdot 5040} = 120$.

(Equivalentemente: il numero è $\binom {10}{3}$, vedi 86.)

84.5 Esempi svolti

Esempio 84.11 — Disposizione in fila con vincolo

In quanti modi $4$ ragazzi e $3$ ragazze possono mettersi in fila, con la condizione che le ragazze stiano tutte all’inizio?

Soluzione. Prima permutiamo le $3$ ragazze tra loro nei primi $3$ posti: $3! = 6$ modi. Poi i $4$ ragazzi tra loro nei posti $4, 5, 6, 7$: $4! = 24$ modi. Totale (per il principio del conteggio): $6\cdot 24 = 144$.

Esempio 84.12 — Permutazioni con due gruppi

In quanti modi posso disporre $4$ libri di matematica e $3$ di fisica su uno scaffale, in modo che i libri della stessa materia stiano consecutivi (in blocchi separati)?

Soluzione. Due fasi:

Scelgo l’ordine dei due blocchi: $2$ scelte (matematica–fisica, oppure fisica–matematica).
Permuto i $4$ libri di matematica tra loro: $4! = 24$.
Permuto i $3$ libri di fisica tra loro: $3! = 6$.

Totale: $2\cdot 24\cdot 6 = 288$.

Esempio 84.13 — Anagrammi senza vincoli alfabetici

Quanti anagrammi di “ABRACADABRA”?

Soluzione. Conta delle lettere: $A=5, B=2, R=2, C=1, D=1$. Totale $11$ lettere.

\[ P_{11}^{(5, 2, 2, 1, 1)} = \frac {11!}{5!\cdot 2!\cdot 2!\cdot 1!\cdot 1!} = \frac {39916800}{120\cdot 2\cdot 2} = \frac {39916800}{480} = 83160. \]

Esempio 84.14 — Sequenze su tre simboli

Quante sequenze di lunghezza $9$ si possono formare con esattamente $4$ A, $3$ B, $2$ C?

Soluzione. $\dfrac {9!}{4!\cdot 3!\cdot 2!} = \dfrac {362880}{24\cdot 6\cdot 2} = \dfrac {362880}{288} = 1260$.

Esempio 84.15 — Mazzo di carte con due carte indistinguibili

Se in un mazzo di $40$ carte sostituiamo l’asso di coppe con un secondo asso di denari (così abbiamo due carte “asso di denari”), in quanti modi distinti possiamo mescolare il mazzo?

Soluzione. $40!/2!$ — il fattore $2!$ tiene conto delle due carte indistinguibili.

Numericamente: $40! \approx 8.16\times 10^{47}$, quindi il risultato è $\approx 4.08\times 10^{47}$.

84.6 Esercizi proposti

Esercizio 84.1

1.

Calcola:

(a) $4!$;
(b) $7!$;
(c) $10!$;
(d) $\dfrac {8!}{5!}$;
(e) $\dfrac {(n+1)!}{n!}$ (semplifica simbolicamente);
(f) $\dfrac {n!}{(n-2)!}$.

2.

Quante permutazioni hanno: (a) $6$ oggetti; (b) $8$ oggetti; (c) un singolo oggetto?

3.

In quanti modi possono entrare in classifica $5$ atleti che partecipano a una gara (senza ex-aequo)?

4.

Quanti sono gli anagrammi della parola “ITALIA”?

5.

Quanti sono gli anagrammi della parola: (a) “ANANAS”; (b) “MISSISSIPPI”; (c) “COMBINATORIO”.

6.

In quanti modi $8$ persone possono fare la fila alla cassa?

7.

In una squadra di calcio di $11$ giocatori (tutti distinti), in quanti modi si può scegliere la formazione iniziale schierata sul campo (lista ordinata)?

8.

Quante sequenze binarie di lunghezza $8$ contengono esattamente $5$ uno e $3$ zero?

9.

Quanti numeri di $5$ cifre si possono formare con le cifre $\{1, 2, 3, 4, 5\}$ se ciascuna deve apparire una sola volta?

10.

Quante sequenze di lunghezza $7$ si possono formare con le lettere $\{A, A, B, B, C, C, D\}$?

11.

In quanti modi $5$ ragazzi e $5$ ragazze possono mettersi in fila se i ragazzi e le ragazze devono alternarsi?

12.

(Discussione.) Spiega perché $0! = 1$ e non $0$. (Suggerimento: pensare alla formula ricorsiva $n! = n\cdot (n-1)!$ e alle convenzioni che rendono coerenti le altre formule combinatorie.)

13.

(Sfida.) Quanti modi diversi ha un mazzo di $52$ carte di essere mescolato? Confronta con il numero di atomi nell’universo osservabile ($\approx 10^{80}$).

84.7 Riepilogo del capitolo

Riepilogo

Calcolo combinatorio: arte di contare configurazioni senza enumerarle.
Principio fondamentale del conteggio: se un’attività si decompone in $k$ scelte successive indipendenti, con $n_1, n_2, \ldots , n_k$ modi per ciascuna, il totale è $n_1\cdot n_2\cdots n_k$.
Permutazione semplice: un ordinamento di $n$ oggetti distinti. Numero:
\[ P_n = n! = n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1. \]
Convenzione: $0! = 1$.
Crescita del fattoriale: rapidissima, più veloce di ogni esponenziale. $10! \approx 3.6\times 10^{6}$, $20! \approx 2.4\times 10^{18}$.
Formula di Stirling (asintotica): $n! \approx \sqrt {2\pi n}\,(n/e)^n$ per $n$ grande.
Permutazione con ripetizione: dato $n_1 + n_2 + \cdots + n_k = n$ oggetti, di cui $n_i$ identici di tipo $i$:
\[ P_n^{(n_1, n_2, \ldots , n_k)} = \frac {n!}{n_1!\,n_2!\cdots n_k!}. \]

Si chiama coefficiente multinomiale.
Esempi tipici: anagrammi di parole con lettere ripetute (MAMMA: $10$, BANANA: $60$, MATEMATICA: $151200$).
Prossimi passi: disposizioni (scelte ordinate di $k$ su $n$, 85); combinazioni e coefficienti binomiali (scelte non ordinate, 86); binomio di Newton (87). Tutte le formule combinatorie troveranno applicazione in calcolo della probabilità (67÷125).

Capitolo 84 Permutazioni semplici e con ripetizione