Cardinalità, sequenze e principio di moltiplicazione

Lezione 1 di probabilità, Unità 1-2. Per calcolare probabilità "casi favorevoli su casi possibili" bisogna saper contare gli elementi di insiemi grandi senza elencarli: è il compito della combinatoria (quante mani di 5 carte su 52? quanti anagrammi di una parola?).

Cardinalità

La cardinalità $|X|$ di un insieme finito $X$ è il numero dei suoi elementi distinti.

Proprietà. Siano $A, B \subseteq X$ finiti.

1. Se $A \cap B = \emptyset$: $|A \cup B| = |A| + |B|$;
2. in generale $|A \cup B| = |A| + |B| - |A \cap B|$;
3. $|A \times B| = |A|\cdot|B|$;
4. $|A^c| = |X| - |A|$.

La 2 si capisce così: sommando $|A| + |B|$ gli elementi comuni vengono contati due volte, quindi si toglie $|A \cap B|$ una volta. La 4 è utilissima per contare gli insiemi descritti con "almeno uno": spesso è più facile contare il complementare ("nessuno").

Esempio del prof. Parole di 6 lettere (sequenze, anche senza senso) con un alfabeto di 24 lettere che contengono almeno una Z. Il complementare sono le parole senza Z, che usano 23 lettere: $23^6$. Le parole in tutto sono $24^6$. Quindi $$24^6 - 23^6 = 191\,102\,976 - 148\,035\,889 = 43\,067\,087$$

Il principio di inclusione-esclusione con tre insiemi

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$ Un elemento che sta in tutti e tre viene contato $3$ volte nei singoli, tolto $3$ volte nelle intersezioni a due, e quindi va ri-aggiunto una volta.

Esempio del prof. In un campus ci sono $120$ studenti, ognuno studia almeno una tra Matematica, Fisica, Inglese: $90$ studiano M, $70$ F, $100$ I; $60$ M e F, $50$ F e I, $40$ M e I. Quanti studiano tutte e tre? Siccome tutti studiano almeno una materia, $|M \cup F \cup I| = 120$: $$120 = 90 + 70 + 100 - 60 - 50 - 40 + x = 110 + x \quad\Longrightarrow\quad x = 10$$

Principio della biiezione. Due insiemi finiti hanno la stessa cardinalità se e solo se esiste una corrispondenza biunivoca tra loro.

Esempio. I multipli di $4$ tra $1$ e $40$ sono $\{4, 8, \dots, 40\}$, in biiezione con $\{1, 2, \dots, 10\}$ tramite $4k \leftrightarrow k$: sono $10$.

Sequenze: quando conta l'ordine

Si indica $I_n := \{1, 2, \dots, n\}$ (e $I_0 = \emptyset$).

Definizione. Una $k$-sequenza di $I_n$ è una $k$-upla ordinata $(a_1, \dots, a_k)$ di elementi di $I_n$, non necessariamente distinti (un elemento di $I_n\times\cdots\times I_n$, $k$ volte). È senza ripetizione se i suoi termini sono distinti.

Esempio. Estraendo nell'ordine $5$ numeri da un'urna con $90$ numeri (senza rimetterli) l'esito è una $5$-sequenza senza ripetizione di $I_{90}$.

Una permutazione di $(a_1, \dots, a_k)$ è una qualunque sequenza ottenuta riordinandone i termini: $(1, 3, 2)$ è una permutazione di $(1, 2, 3)$; $(2, 1, 2)$ lo è di $(1, 2, 2)$.

Spartizioni: distribuire oggetti distinti

Definizione. Una $n$-spartizione di $I_k$ è una $n$-upla ordinata $(C_1, \dots, C_n)$ di sottoinsiemi di $I_k$ a due a due disgiunti (anche vuoti) con unione $I_k$.

È il modello di "distribuire $k$ oggetti distinti in $n$ scatole distinte": $C_j$ è l'insieme degli oggetti finiti nella scatola $j$. Esempio: distribuire $7$ libri a $4$ persone, $(\{7, 2\}, \emptyset, \{1, 4, 5\}, \{3, 6\})$.

Proposizione. Le $n$-spartizioni di $I_k$ sono tante quante le $k$-sequenze di $I_n$.

Perché: si mettono in fila gli oggetti $1, \dots, k$ e sotto ciascuno si scrive il numero della scatola in cui va: $a_i$ = scatola che contiene $i$. Per i $7$ libri dell'esempio: $(a_1, \dots, a_7) = (3, 1, 4, 3, 3, 4, 1)$. Questa corrispondenza è biunivoca. Viceversa $(C_1, C_2, C_3) = (\{1, 3, 5\}, \{2\}, \{4\})$ corrisponde alla sequenza $(1, 2, 1, 3, 1)$.

Modelli. Una funzione $f : I_k \to I_n$ è descritta dalla sequenza $(f(1), \dots, f(k))$; distribuire $5$ smartphone distinti a $8$ persone è una $5$-sequenza di $I_8$ (per ogni telefono, chi lo riceve).

Il principio di moltiplicazione

Principio di moltiplicazione (PM). Supponiamo che gli elementi di un insieme $X$ si costruiscano con una procedura in $n$ fasi, in cui la prima fase ha $m_1$ esiti possibili, la seconda (per ogni esito della prima) $m_2$, …, la $n$-esima $m_n$, e che l'elemento costruito determini univocamente gli esiti di tutte le fasi. Allora $$|X| = m_1\cdot m_2\cdots m_n$$

Esempio del prof. Comitati di $2$ persone, scegliendo tra $6$ donne e $5$ uomini, con esattamente una donna e un uomo. Fase 1: la donna ($6$ modi); fase 2: l'uomo ($5$ modi). Dal comitato $\{D, U\}$ si risale a entrambe le scelte. PM: $6\cdot 5 = 30$.

Un errore fatale ma comune. Comitati di $2$ persone tra $2$ donne e $2$ uomini con almeno una donna. Contandoli a mano sono $5$: $\{D_1, D_2\}$, $\{D_1, U_1\}$, $\{D_1, U_2\}$, $\{D_2, U_1\}$, $\{D_2, U_2\}$. Il ragionamento "fase 1: scelgo una donna ($2$ modi); fase 2: scelgo un altro membro qualsiasi ($3$ modi)" dà $2\cdot 3 = 6$. L'errore: il comitato $\{D_1, D_2\}$ si ottiene sia scegliendo prima $D_1$ e poi $D_2$, sia scegliendo prima $D_2$ e poi $D_1$: l'oggetto finale non determina gli esiti delle fasi, e il PM non si può applicare (si conta due volte lo stesso comitato).

Proposizione. Il numero di $k$-sequenze di $I_n$ è $n^k$.

Dimostrazione. Si sceglie il primo termine ($n$ modi), il secondo ($n$ modi), …, il $k$-esimo ($n$ modi); la sequenza determina tutte le scelte. PM: $n^k$ ∎.

Numero di sottoinsiemi. Un sottoinsieme $A \subseteq I_n$ corrisponde alla $2$-spartizione $(A, A^c)$, e quindi a una $n$-sequenza di $\{0, 1\}$ (per ogni elemento: $1$ se sta in $A$, $0$ altrimenti). Quindi i sottoinsiemi di $I_n$ sono $2^n$.

Il seguito (fattoriale, binomiali, anagrammi) è in Sottoinsiemi, principio di divisione e anagrammin! conta le permutazioni di n oggetti; le k-sequenze senza ripetizione di Iₙ sono n!/(n−k)!. Principio di divisione: se ogni elemento di Y corrisponde a esattamente m elementi di X, |Y| = |X|/m. Da qui i k-sottoinsiemi di Iₙ sono C(n,k) = n!/(k!(n−k)!) (ogni insieme viene da k! sequenze). Anagrammi di una parola con k₁, …, kₙ ripetizioni: k!/(k₁!⋯kₙ!). Procedura: strutture ordinate → sequenze e PM; non ordinate → insiemi o principio di divisione; contare solo alla fine. Stirling: n! ~ √(2πn)(n/e)ⁿ.Sottoinsiemi, principio di divisione e anagrammi →; esercizi nell'Esercizio 38 · contare con sequenze, sottoinsiemi e anagrammi.

Errori comuni

• Applicare il PM quando l'oggetto finale non determina le fasi (il comitato con "almeno una donna").
• Contare "almeno uno" direttamente invece che con il complementare.
• Confondere sequenze (conta l'ordine) e sottoinsiemi (non conta).