Sottoinsiemi, principio di divisione e anagrammi

Lezione 1 di probabilità, Unità 3-4. Prerequisiti: Cardinalità, sequenze e principio di moltiplicazione|A ∪ B| = |A| + |B| − |A ∩ B| (inclusione-esclusione), |A × B| = |A||B|, |Aᶜ| = |X| − |A|; due insiemi hanno la stessa cardinalità se sono in biiezione. Una k-sequenza di Iₙ = {1,…,n} è una k-upla ordinata (conta l'ordine): sono nᵏ; distribuire k oggetti distinti in n scatole (spartizioni) equivale a una k-sequenza di Iₙ. Principio di moltiplicazione: se un oggetto si costruisce in fasi con m₁, …, mₙ esiti e l'oggetto finale determina gli esiti di tutte le fasi, il numero è m₁⋯mₙ. I sottoinsiemi di Iₙ sono 2ⁿ.Cardinalità, sequenze e principio di moltiplicazione →; le proprietà algebriche di fattoriali e binomiali sono in Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali → e Binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton → (Analisi 1).

Il fattoriale e le sequenze senza ripetizione

$n! = n(n - 1)\cdots 2\cdot 1$ per $n \ge 1$, e $0! = 1$.

Proposizione. Il numero di permutazioni di $(1, 2, \dots, n)$ è $n!$. Proposizione. Il numero di $k$-sequenze senza ripetizione di $I_n$ è $$\frac{n!}{(n - k)!} = n(n - 1)\cdots(n - k + 1) \quad (k \le n), \qquad 0 \quad (k > n)$$

Dimostrazione (PM). Il primo termine si sceglie in $n$ modi, il secondo, diverso dal primo, in $n - 1$, …, il $k$-esimo in $n - k + 1$ modi. Se $k > n$ non si possono scegliere $k$ elementi distinti ∎. Per $k = n$ si ottengono le permutazioni, $n!$.

Esempio del prof. Da un'urna con $12$ palline ($8$ nere $N_1, \dots, N_8$ e $4$ rosse $R_1, \dots, R_4$) se ne estraggono $3$ in ordine, senza reimmissione. Quante terne hanno l'ultima pallina rossa? Conviene scegliere prima la fase vincolata: l'ultima (rossa) in $4$ modi, poi la prima tra le $11$ rimaste, poi la seconda tra le $10$: $4\cdot 11\cdot 10 = 440$ (su $12\cdot 11\cdot 10 = 1320$ terne: un terzo, come la proporzione di rosse).

La formula di Stirling. $n! \sim \sqrt{2\pi n}\left(\frac ne\right)^n$ per $n \to +\infty$ (il rapporto tende a $1$; già per $n = 30$ vale $1.003$). Dice quanto è grande $n!$: per esempio $52!$, il numero di modi di mescolare un mazzo, ha $68$ cifre (il numero di cifre di $k$ è $\lfloor\log_{10}k\rfloor + 1$).

Il principio di divisione e i sottoinsiemi

Principio di divisione. Siano $X$, $Y$ finiti e $f : X \to Y$ tale che ogni $y \in Y$ provenga da esattamente $m$ elementi di $X$. Allora $|Y| = \frac{|X|}{m}$.

Teorema (numero di sottoinsiemi). Il numero di sottoinsiemi di $k$ elementi di $I_n$ è $$C(n, k) = \binom nk = \frac{n!}{k!\,(n - k)!}$$ In particolare $\binom n0 = \binom nn = 1$.

Dimostrazione. Sia $X$ l'insieme delle $k$-sequenze senza ripetizione e $Y$ quello dei $k$-sottoinsiemi; $f$ "cambia le parentesi tonde in graffe", $(a_1, \dots, a_k) \mapsto \{a_1, \dots, a_k\}$. Ogni insieme $\{a_1, \dots, a_k\}$ proviene dalle $k!$ permutazioni di $(a_1, \dots, a_k)$. Per il principio di divisione $|Y| = \frac{n!/(n - k)!}{k!}$ ∎.

Esempio del prof. Comitati di $4$ persone tra $6$ donne e $5$ uomini, con esattamente $2$ donne e $2$ uomini: si scelgono le $2$ donne ($\binom62 = 15$ modi) e i $2$ uomini ($\binom52 = 10$); il comitato determina entrambe le scelte, quindi $15\cdot 10 = 150$.

Proprietà del binomiale (con interpretazione combinatoria)

1. $\binom nk = \binom n{n - k}$: scegliere i $k$ elementi da prendere equivale a scegliere gli $n - k$ da lasciare;
2. $(x + y)^n = \sum_{j=0}^n\binom nj x^jy^{n - j}$ (binomio di Newton): sviluppando il prodotto di $n$ fattori $(x + y)$, il termine $x^jy^{n-j}$ compare tante volte quanti sono i modi di scegliere i $j$ fattori da cui prendere $x$;
3. $\binom n0 + \cdots + \binom nn = 2^n$: si contano i sottoinsiemi di $I_n$ raggruppandoli per numero di elementi;
4. Formula di Stiefel ($n, k \ge 1$): $\binom{n-1}{k-1} + \binom{n-1}k = \binom nk$: i $k$-sottoinsiemi di $I_n$ si dividono in quelli che contengono $n$ (scelgo gli altri $k - 1$ tra $n - 1$) e quelli che non lo contengono (scelgo $k$ tra $n - 1$). È la regola del triangolo di Tartaglia: ogni numero è la somma dei due sopra.

Esempio. $\binom n0 - \binom n1 + \cdots + (-1)^n\binom nn = 0$: è il binomio di Newton con $x = -1$, $y = 1$, cioè $(1 - 1)^n = 0$. In parole: i sottoinsiemi di cardinalità pari sono tanti quanti quelli di cardinalità dispari.

Anagrammi

Un anagramma di una parola è una permutazione della sequenza delle sue lettere. Per esempio $(T, A, M, E, M, I, A, T, C, A)$ è un anagramma di $(M, A, T, E, M, A, T, I, C, A)$.

Proposizione. Il numero di anagrammi di una sequenza di lunghezza $k$ con $k_1$ ripetizioni del simbolo $1$, …, $k_n$ ripetizioni del simbolo $n$ ($k_1 + \cdots + k_n = k$) è $$\frac{k!}{k_1!\,k_2!\cdots k_n!}$$

Perché: se le lettere uguali fossero distinguibili (con indici, $A_1, A_2, A_3$, …) le permutazioni sarebbero $k!$. Ogni anagramma vero corrisponde a $k_1!\cdots k_n!$ di queste (si permutano tra loro le copie di ogni lettera): principio di divisione.

Esempio. MATEMATICA ha $10$ lettere: M ($2$), A ($3$), T ($2$), E, I, C ($1$ ciascuna): $$\frac{10!}{2!\,3!\,2!} = \frac{3\,628\,800}{24} = 151\,200$$

La procedura per contare

1. Struttura ordinata: ricondurla a sequenze, o a più fasi ciascuna riconducibile a strutture note, e usare il principio di moltiplicazione (controllando che l'oggetto finale determini le fasi).
2. Struttura non ordinata: ricondurla a insiemi, oppure contarla come struttura ordinata e usare il principio di divisione.
3. Contare solo alla fine: prima si descrive con precisione l'insieme degli esiti.

Esempi completi (estrazioni da urne, doppia coppia e full al poker) nell'Esercizio 38 · contare con sequenze, sottoinsiemi e anagrammi.

Errori comuni

• Usare $\binom nk$ quando l'ordine conta (o $\frac{n!}{(n-k)!}$ quando non conta).
• Moltiplicare per scelte che si sovrappongono (vedi l'errore del comitato).
• Dimenticare i vincoli sulle scelte successive (senza reimmissione le scelte disponibili diminuiscono).