Lezione 11Calcolo combinatorio

Modulo: Probabilità, Lezione 1 ("Calcolo combinatorio"), slide per prendere appunti. Le lezioni di probabilità sono numerate qui da 11 a 20, dopo le dieci di analisi.

Argomenti trattati

1. Unità 1 - Sequenze e spartizioni: cardinalità e sue proprietà, inclusione-esclusione (il campus), principio della biiezione; sequenze, permutazioni, spartizioni e loro corrispondenza con le sequenze; sottoinsiemi; modelli combinatori.
2. Unità 2 - Principio di moltiplicazione e numero di sequenze: il principio di moltiplicazione e il suo uso sbagliato (il comitato con almeno una donna); $n^k$ sequenze; $2^n$ sottoinsiemi.
3. Unità 3 - Il fattoriale e le sequenze senza ripetizione: fattoriale, formula di Stirling, permutazioni, $\frac{n!}{(n-k)!}$ sequenze senza ripetizione; l'urna con l'ultima pallina rossa.
4. Unità 4 - Principio di divisione e numero di sottoinsiemi: binomiale, principio di divisione, $\binom nk$ sottoinsiemi, proprietà del binomiale e triangolo di Tartaglia; la procedura per contare; doppia coppia, full, anagrammi.

Teoria

• 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 →
• 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

• Esercizio 38 · contare con sequenze, sottoinsiemi e anagrammi — esercizio di ricapitolazione, esercizi del MOOC, anagrammi
• Esercizio 41 · anagrammi e allineamenti dagli appelli — combinatoria dagli appelli 2015-2018