Calcolo combinatorio

Come si contano scelte e ordinamenti senza elencarli, con il principio di moltiplicazione, le permutazioni, le disposizioni e le combinazioni, e come si riconosce nel testo di un quiz quale modello si applica.

On this page

Il principio fondamentale del conteggio
Fattoriale e permutazioni

Il principio fondamentale del conteggio

1. Principio di moltiplicazione

Il calcolo combinatorio studia i metodi per contare in quanti modi si possono scegliere o ordinare degli oggetti, senza elencarli uno per uno. Il metodo di base è il principio di moltiplicazione, detto anche principio fondamentale del conteggio. Se una scelta si compie in due fasi successive, la prima fase si può compiere in $m$ modi e, per ciascuno di questi, la seconda si può compiere in $n$ modi, allora la scelta completa si può compiere in

m \cdot n

modi. Il principio vale perché a ciascuna delle $m$ scelte della prima fase si possono affiancare $n$ scelte della seconda, quindi le scelte complete formano $m$ gruppi di $n$ scelte ciascuno. Lo stesso vale con più fasi. Un ristorante propone $3$ primi, $4$ secondi e $2$ dolci, perciò un pasto composto da un primo, un secondo e un dolce si può scegliere in $3 \cdot 4 \cdot 2 = 24$ modi.

Diagramma ad albero

Un diagramma ad albero rappresenta le scelte fase per fase. Da un punto iniziale partono tanti rami quanti sono i modi della prima fase; dalla fine di ciascun ramo partono tanti rami quanti sono i modi della seconda fase, e così via. Ogni percorso dal punto iniziale a un’estremità finale è una scelta completa, quindi il numero delle scelte è il numero delle estremità finali. Con $2$ primi, pasta e riso, e $3$ secondi, carne, pesce e verdure, l’albero ha $2$ rami nella prima fase e $3$ rami da ciascuno di essi, perciò le scelte complete sono $2 \cdot 3 = 6$ .

Diagramma ad albero per

2

primi e

3

secondi:

2 \cdot 3 = 6

percorsi, uno per ogni pasto

Il diagramma ad albero è utile anche quando il numero di scelte di una fase dipende dalla scelta fatta nella fase precedente. In quel caso il principio di moltiplicazione non si applica direttamente, e si contano le estremità finali dell’albero.

2. Principio della somma

Se le scelte possibili si dividono in due gruppi senza elementi in comune, il primo con $m$ scelte e il secondo con $n$ , allora le scelte in tutto sono

m + n .

Il principio della somma si applica quando si compie una sola scelta tra alternative diverse; il principio di moltiplicazione si applica quando si compiono più scelte una dopo l’altra. Per andare da Roma a Milano una persona può prendere uno dei $5$ treni del mattino oppure uno dei $3$ voli, quindi ha $5 + 3 = 8$ possibilità. Se invece va in treno da Roma a Milano e poi in pullman da Milano a Como, con $4$ pullman disponibili, le possibilità sono $5 \cdot 4 = 20$ .

Fattoriale e permutazioni

1. Fattoriale

Il fattoriale di un numero naturale $n \geq 1$ è il prodotto di tutti i numeri naturali da $1$ a $n$ , e si indica con $n!$ :

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

Si pone inoltre $0! = 1$ . I primi valori sono $2! = 2$ , $3! = 6$ , $4! = 24$ , $5! = 120$ , $6! = 720$ e $7! = 5040$ . Il fattoriale cresce molto in fretta, ma nei quozienti si semplifica senza calcolarlo per intero, perché $n! = n \cdot (n - 1)!$ . Per esempio

\frac{8!}{6!} = \frac{8 \cdot 7 \cdot 6!}{6!} = 8 \cdot 7 = 56 .

2. Permutazioni semplici

Una permutazione di $n$ oggetti distinti è un modo di disporli in fila, cioè un loro ordinamento. Il numero delle permutazioni di $n$ oggetti è

P_n = n! .

La formula segue dal principio di moltiplicazione. Il primo posto della fila si occupa in $n$ modi, il secondo con uno degli $n - 1$ oggetti rimasti, il terzo con uno degli $n - 2$ , e così via fino all’ultimo posto, per il quale resta un solo oggetto. Con le permutazioni si contano gli ordinamenti di persone in fila, di libri su uno scaffale, di prove in un calendario. Cinque persone si mettono in fila davanti a uno sportello in $P_5 = 5! = 120$ modi diversi.

Le permutazioni di tre lettere

Le permutazioni delle lettere $A$ , $B$ , $C$ sono $3! = 6$ :

ABC, \quad ACB, \quad BAC, \quad BCA, \quad CAB, \quad CBA .

Le prime due iniziano con $A$ , le due successive con $B$ , le ultime due con $C$ . Fissata la prima lettera, le altre due si ordinano in $2! = 2$ modi, quindi le permutazioni sono $3 \cdot 2 = 6$ .

Permutazioni con vincoli

Quando alcuni oggetti devono stare vicini, si considerano come un unico blocco. Se in una fila di $5$ persone Anna e Bruno devono stare uno accanto all’altro, il blocco formato da Anna e Bruno e le altre $3$ persone sono $4$ elementi, che si ordinano in $4!$ modi. Dentro il blocco Anna e Bruno si ordinano in $2!$ modi, quindi per il principio di moltiplicazione le file sono

4! \cdot 2! = 24 \cdot 2 = 48 .

Quando invece un oggetto ha un posto fisso, si ordinano soltanto gli altri. Se Anna deve essere la prima della fila, le file sono $4! = 24$ .

Persone attorno a un tavolo rotondo

Attorno a un tavolo rotondo si possono considerare uguali due disposizioni che si ottengono l’una dall’altra con una rotazione, perché in entrambe ciascuno ha gli stessi vicini a destra e a sinistra. Con questa convenzione si fissa il posto di una persona e si ordinano le altre $n - 1$ , quindi le disposizioni sono $(n - 1)!$ . Sei amici si siedono attorno a un tavolo rotondo in $5! = 120$ modi. Se le rotazioni si considerano diverse, per esempio perché i posti sono numerati, le disposizioni sono $6! = 720$ .

The theory continues with 7 more sections (permutazioni con ripetizione, disposizioni semplici, disposizioni con ripetizione…), plus all worked examples, the solutions and the PDF.

Unlock now