LogicaUniPR - Guida Interattiva

6.1 I Pilastri del Conteggio: Principio della Somma e del Prodotto

Alla base di quasi tutti i problemi di conteggio ci sono due principi fondamentali:

6.1.1 Principio della Somma

Immagina di dover fare una scelta tra due gruppi di opzioni, e queste opzioni si escludono a vicenda (cioè, non puoi scegliere da entrambi i gruppi contemporaneamente). Se il primo gruppo ha $m$ opzioni e il secondo gruppo ha $n$ opzioni, allora hai un totale di $m+n$ modi per fare la tua scelta.

Formalmente: Se $A$ e $B$ sono due insiemi finiti e disgiunti (cioè $A \cap B = \emptyset$), allora il numero di elementi nell'unione di $A$ e $B$ è la somma dei loro elementi: $|A \cup B| = |A| + |B|$.

Generalizzazione: Se hai $k$ compiti $T_1, T_2, \dots, T_k$, che possono essere svolti rispettivamente in $n_1, n_2, \dots, n_k$ modi, e nessuno dei compiti può essere svolto contemporaneamente ad un altro, allora il numero di modi per svolgere uno qualsiasi di questi compiti è $n_1 + n_2 + \dots + n_k = \sum_{i=1}^{k} n_i$.

Esempio: Per pranzo, puoi scegliere tra 3 tipi di primi piatti oppure 4 tipi di secondi piatti. Quante scelte hai per un piatto principale? $3 + 4 = 7$ scelte.

6.1.2 Principio del Prodotto

Supponi di dover compiere una procedura che consiste in una sequenza di più passaggi (o compiti). Se il primo passaggio può essere fatto in $m$ modi e, indipendentemente dalla scelta fatta per il primo passaggio, il secondo passaggio può essere fatto in $n$ modi, allora l'intera procedura a due passaggi può essere fatta in $m \cdot n$ modi.

Formalmente: Se $A$ e $B$ sono due insiemi finiti, il numero di elementi nel loro prodotto cartesiano $A \times B$ (cioè il numero di coppie ordinate $(a,b)$ con $a \in A, b \in B$) è $|A \times B| = |A| \cdot |B|$.

Generalizzazione: Se una procedura consiste in $k$ passaggi sequenziali, e il primo passaggio può essere fatto in $n_1$ modi, il secondo in $n_2$ modi (per ognuno dei modi del primo), ..., il $k$-esimo in $n_k$ modi (per ognuna delle combinazioni dei passaggi precedenti), allora il numero totale di modi per eseguire l'intera procedura è $n_1 \cdot n_2 \cdot \dots \cdot n_k = \prod_{i=1}^{k} n_i$.

Esempio: Per creare una password di 2 caratteri, dove il primo carattere è una lettera maiuscola (26 scelte) e il secondo è una cifra (10 scelte), hai $26 \cdot 10 = 260$ password possibili.

6.2 Il Fattoriale ($n!$): Un Prodotto Fondamentale

Il fattoriale di un numero naturale non negativo $n$, indicato con $n!$, è il prodotto di tutti i numeri interi positivi da $1$ fino a $n$. È una funzione che cresce molto rapidamente!

Definizione:
Se $n > 0$, $n! = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 3 \cdot 2 \cdot 1 = \prod_{i=1}^{n} i$.
Per convenzione, si definisce $0! = 1$. Questa definizione è utile per far funzionare molte formule combinatorie anche nei casi limite.

Possiamo anche definire il fattoriale in modo ricorsivo:
$n! = \begin{cases} 1 & \text{se } n=0 \\ n \cdot (n-1)! & \text{se } n > 0 \end{cases}$

$1! = 1$
$2! = 2 \cdot 1 = 2$
$3! = 3 \cdot 2 \cdot 1 = 6$
$4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$
$5! = 5 \cdot 4! = 5 \cdot 24 = 120$

6.3 Permutazioni: Quando l'Ordine Conta!

Una permutazione è un arrangiamento ordinato di un insieme di oggetti. In una permutazione, l'ordine in cui gli oggetti sono disposti è fondamentale.

6.3.1 Permutazioni Semplici (di $n$ oggetti distinti)

Quanti modi ci sono per ordinare $n$ oggetti distinti? Questo è il numero di permutazioni semplici di $n$ oggetti, indicato con $P_n$.
Per il primo posto abbiamo $n$ scelte, per il secondo $n-1$ (perché un oggetto è già stato usato), per il terzo $n-2$, e così via, fino all'ultimo posto per cui rimane 1 scelta.
Per il principio del prodotto: $P_n = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 1 = n!$.

Esempio: In quanti modi si possono anagrammare le lettere della parola "TRE"?
Abbiamo 3 lettere distinte. Il numero di anagrammi (permutazioni) è $P_3 = 3! = 6$.
Gli anagrammi sono: TRE, TER, RTE, RET, ETR, ERT.

6.3.2 $k$-Permutazioni (Disposizioni Semplici $D_{n,k}$)

A volte vogliamo ordinare solo una parte degli oggetti disponibili. Una $k$-permutazione (o disposizione semplice di $n$ oggetti di classe $k$, indicata $D_{n,k}$ o $P(n,k)$) è una sequenza ordinata di $k$ oggetti distinti scelti da un insieme di $n$ oggetti distinti (con $k \le n$).

Per il primo posto abbiamo $n$ scelte, per il secondo $n-1$, ..., per il $k$-esimo posto abbiamo $n-(k-1) = n-k+1$ scelte.
$D_{n,k} = P(n,k) = n \cdot (n-1) \cdot \dots \cdot (n-k+1)$.
Questa formula può essere scritta in modo più compatto usando i fattoriali:
$D_{n,k} = \frac{n!}{(n-k)!}$.

Esempio: In una gara con 8 cavalli ($n=8$), quanti sono i possibili ordini di arrivo per i primi 3 posti (podio, $k=3$)? L'ordine conta.
$D_{8,3} = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$ possibili podi.

Formalmente, una $k$-permutazione da un insieme $S$ di $n$ elementi è una funzione iniettiva $f: I_k \to S$, dove $I_k = \{1, \dots, k\}$.

6.3.3 Permutazioni con Ripetizione (di oggetti non tutti distinti)

Cosa succede se gli $n$ oggetti che vogliamo ordinare non sono tutti distinti? Ad esempio, gli anagrammi della parola "MAMMA".
Se abbiamo $n$ oggetti in totale, di cui $n_1$ sono di un tipo (indistinguibili tra loro), $n_2$ di un secondo tipo, ..., $n_j$ di un $j$-esimo tipo, tali che $n_1 + n_2 + \dots + n_j = n$, allora il numero di permutazioni distinte è:
$P_n^{(n_1, n_2, \dots, n_j)} = \frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_j!}$.

Esempio: Quanti anagrammi della parola "SASSO"?
$n=5$ lettere totali.
S: 3 volte ($n_1=3$)
A: 1 volta ($n_2=1$)
O: 1 volta ($n_3=1$)
Numero di anagrammi = $\frac{5!}{3! \cdot 1! \cdot 1!} = \frac{120}{6 \cdot 1 \cdot 1} = 20$.

6.4 Disposizioni: Formare Gruppi Ordinati

Il termine "disposizione" è strettamente legato a quello di "permutazione di $k$ elementi da $n$". Una disposizione si riferisce alla formazione di gruppi di $k$ elementi scelti da un insieme di $n$ elementi, dove l'ordine degli elementi nel gruppo è importante.

6.4.1 Disposizioni Semplici (Senza Ripetizione)

Le disposizioni semplici di $n$ elementi distinti di classe $k$ (o "presi a $k$ a $k$") sono esattamente le $k$-permutazioni che abbiamo visto: sequenze ordinate di $k$ elementi distinti scelti da $n$.
$D_{n,k} = \frac{n!}{(n-k)!}$.

6.4.2 Disposizioni con Ripetizione

Nelle disposizioni con ripetizione di $n$ elementi distinti di classe $k$, ogni elemento può essere scelto più volte, e l'ordine conta. Per ognuna delle $k$ posizioni nel gruppo, abbiamo $n$ scelte possibili (perché possiamo riutilizzare gli elementi).

Per il principio del prodotto, il numero di disposizioni con ripetizione è:
$D'_{n,k} = n \cdot n \cdot \dots \cdot n$ ($k$ volte) $= n^k$.

Esempio: Quanti numeri di 3 cifre si possono formare usando le cifre $\{1, 2, 3, 4\}$, se le ripetizioni sono permesse?
Qui $n=4$ (le cifre disponibili) e $k=3$ (la lunghezza del numero).
Numero di numeri possibili = $D'_{4,3} = 4^3 = 4 \cdot 4 \cdot 4 = 64$.
(Esempi: 111, 123, 321, 442, ecc.)

6.5 Combinazioni: Quando l'Ordine NON Conta!

A differenza delle permutazioni e delle disposizioni, nelle combinazioni l'ordine in cui gli oggetti vengono scelti o raggruppati NON ha importanza. Una combinazione è essenzialmente un sottoinsieme.

6.5.1 Combinazioni Semplici (Senza Ripetizione)

Una combinazione semplice di $n$ oggetti distinti presi a $k$ alla volta (o di classe $k$) è il numero di modi di scegliere un sottoinsieme di $k$ elementi da un insieme di $n$ elementi. L'ordine di scelta non crea un nuovo sottoinsieme (es. $\{a,b,c\}$ è lo stesso sottoinsieme di $\{c,a,b\}$).

Il numero di combinazioni semplici si indica con $C_{n,k}$ o, più comunemente, con il coefficiente binomiale $\binom{n}{k}$ (leggi "$n$ su $k$").

Per calcolarlo, partiamo dalle disposizioni $D_{n,k}$ (dove l'ordine conta). Ogni gruppo di $k$ elementi può essere ordinato in $k!$ modi (le permutazioni di $k$ elementi). Quindi, per ottenere il numero di combinazioni (dove l'ordine non conta), dividiamo il numero di disposizioni per $k!$:

$\binom{n}{k} = C_{n,k} = \frac{D_{n,k}}{k!} = \frac{n!}{k!(n-k)!}$ (per $0 \le k \le n$).

Esempio: Quante possibili squadre di calcio a 5 ($k=5$) si possono formare da un gruppo di 10 giocatori ($n=10$)? L'ordine dei giocatori nella squadra non conta.
Numero di squadre = $\binom{10}{5} = \frac{10!}{5!(10-5)!} = \frac{10!}{5!5!} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 2 \cdot 3 \cdot 2 \cdot 7 \cdot 3 = 252$.

6.5.2 Proprietà dei Coefficienti Binomiali

• $\binom{n}{0} = 1$ (C'è un solo modo di scegliere 0 elementi: l'insieme vuoto).
• $\binom{n}{n} = 1$ (C'è un solo modo di scegliere $n$ elementi: l'intero insieme).
• $\binom{n}{1} = n$ (Ci sono $n$ modi di scegliere 1 elemento).
• Legge dei Tre Fattoriali (o di simmetria): $\binom{n}{k} = \binom{n}{n-k}$. Scegliere $k$ elementi da includere è come scegliere $n-k$ elementi da escludere.
• Legge di Stifel (o di Pascal): $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (per $n, k > 0$). Questa è la regola che genera il Triangolo di Tartaglia.

6.5.3 Triangolo di Tartaglia (o di Pascal)

È una disposizione triangolare dei coefficienti binomiali, dove ogni numero è la somma dei due numeri che lo sovrastano immediatamente. La riga $n$-esima (partendo da $n=0$) contiene i coefficienti $\binom{n}{k}$ per $k=0, \dots, n$.

      1              (n=0)
     1 1             (n=1)
    1 2 1            (n=2)
   1 3 3 1           (n=3)
  1 4 6 4 1          (n=4)
 1 5 10 10 5 1         (n=5)
... e così via ...
                        

6.5.4 Teorema Binomiale (o Binomio di Newton)

I coefficienti binomiali sono chiamati così perché compaiono come coefficienti nello sviluppo della potenza di un binomio $(a+b)^n$:

$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$

$= \binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1}b^1 + \binom{n}{2}a^{n-2}b^2 + \dots + \binom{n}{n}a^0 b^n$.

Esempio: Sviluppare $(a+b)^4$.
I coefficienti dalla riga $n=4$ del Triangolo di Tartaglia sono 1, 4, 6, 4, 1.
$(a+b)^4 = \binom{4}{0}a^4b^0 + \binom{4}{1}a^3b^1 + \binom{4}{2}a^2b^2 + \binom{4}{3}a^1b^3 + \binom{4}{4}a^0b^4$
$= 1a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + 1b^4$.

Un'identità importante derivata dal teorema binomiale (ponendo $a=1, b=1$) è:
$\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$.
Questo conferma che il numero totale di sottoinsiemi di un insieme di $n$ elementi (somma dei modi di scegliere 0 elementi, 1 elemento, ..., $n$ elementi) è $2^n$.

6.6 Esercizi del Capitolo 6