Salta al contenuto
Note per Studenti Esercizio 41 · anagrammi e allineamenti dagli appelli

Esercizio 41anagrammi e allineamenti dagli appelli

Esame
In questa pagina 5

Testo (esercizi di combinatoria dagli appelli).

  1. (Appello 3, 12 luglio 2017.) Contare gli anagrammi di MARTELLO che non cominciano con MAR.
  2. (Appello 3, a.a. 2017/18.) Quanti sono gli anagrammi di SANSCRITO nei quali non vi sono due S vicine?
  3. (Appello 4, a.a. 2017/18.) Quanti sono i modi per allineare, di faccia, 5252 carte da gioco in modo che i 44 assi siano vicini fra loro?
  4. (Appello 4, a.a. 2015/16.) Qual è la probabilità che, distribuendo a caso venti carte da gioco diverse in venti contenitori (vuoti), nessuno dei contenitori resti vuoto? Esprimere il risultato in forma di frazione.

Teoria: 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 →, 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 →, Probabilità uniforme su uno spazio finitoSu uno spazio campionario finito Ω con esiti equiprobabili la probabilità uniforme è P(A) = |A|/|Ω| (casi favorevoli su casi possibili); equivalentemente P({ω}) = 1/|Ω| per ogni esito. Gli eventi sono i sottoinsiemi di Ω. Proprietà: P(∅) = 0, P(Ω) = 1, P(A ∪ B) = P(A) + P(B) − P(A ∩ B), P(Aᶜ) = 1 − P(A). Scegliere Ω in modo che gli esiti siano davvero equiprobabili è una scelta di modello, non di matematica (dado con facce ripetute, somma di due dadi, paradosso dei compleanni).Probabilità uniforme su uno spazio finito →.

1. Anagrammi di MARTELLO che non cominciano con MAR

Tutti gli anagrammi. MARTELLO ha 88 lettere, con la L ripetuta 22 volte (le altre M, A, R, T, E, O una volta): 8!2!=40 3202=20 160\frac{8!}{2!} = \frac{40\,320}{2} = 20\,160

Quelli che cominciano con MAR. Le prime tre lettere sono fissate; restano da anagrammare T, E, L, L, O (55 lettere, L doppia): 5!2!=60\frac{5!}{2!} = 60.

Per complementare: 20 160−60=20 10020\,160 - 60 = 20\,100.

2. Anagrammi di SANSCRITO senza due S vicine

SANSCRITO ha 99 lettere: S (22 volte) e A, N, C, R, I, T, O (77 lettere distinte). Totale anagrammi: 9!2!=181 440\frac{9!}{2!} = 181\,440.

Metodo dei "buchi". Prima si dispongono le 77 lettere diverse da S: 7!=50407! = 5040 modi. Tra loro e agli estremi ci sono 88 "buchi" (_ X _ X _⋯X _\_\,X\,\_\,X\,\_\cdots X\,\_). Le due S, per non essere vicine, devono andare in due buchi diversi; siccome le S sono uguali conta solo quali buchi, cioè un sottoinsieme di 22 buchi su 88: (82)=28\binom82 = 28. Ogni anagramma senza S vicine si ottiene in un solo modo, quindi (PM) 7!⋅(82)=5040⋅28=141 1207!\cdot\binom82 = 5040\cdot 28 = 141\,120

Controllo con il complementare: gli anagrammi con le due S vicine si contano incollando "SS" in un blocco unico: 88 oggetti distinti, 8!=40 3208! = 40\,320. E 181 440−40 320=141 120181\,440 - 40\,320 = 141\,120 ✓.

3. Le 52 carte con i 4 assi vicini

Metodo del blocco. Si incollano i 44 assi in un blocco: insieme alle altre 4848 carte si hanno 4949 "oggetti" distinti da allineare, 49!49! modi. Dentro il blocco gli assi si possono ordinare in 4!=244! = 24 modi. Ogni allineamento con gli assi vicini determina l'ordine degli oggetti e quello interno al blocco: 49!⋅4!49!\cdot 4! In probabilità: mescolando a caso, gli assi sono tutti vicini con probabilità 49! 4!52!=2452⋅51⋅50≈0.00018\frac{49!\,4!}{52!} = \frac{24}{52\cdot 51\cdot 50} \approx 0.00018.

4. Venti carte in venti contenitori, nessuno vuoto

Spazio campionario. Ogni carta va in un contenitore a caso, indipendentemente: un esito è una funzione {carte} → {contenitori}, cioè una 2020-sequenza di I20I_{20} (per ogni carta, il suo contenitore). ∣Ω∣=2020|\Omega| = 20^{20}, esiti equiprobabili.

Favorevoli. Nessun contenitore vuoto con 2020 carte e 2020 contenitori significa una carta per contenitore: la funzione è una biiezione, cioè una sequenza senza ripetizione, 20!20! casi. P=20!2020≈2.3⋅10−8P = \frac{20!}{20^{20}} \approx 2.3\cdot 10^{-8} Praticamente impossibile: è molto più probabile che qualche contenitore resti vuoto e qualcun altro ne riceva più di una.

Errori comuni

  • Dimenticare le lettere ripetute (si dividerebbe per niente e si conterebbe il doppio).
  • Nel metodo dei buchi, ordinare le S (sono uguali: si sceglie un insieme di buchi, non una sequenza).
  • Nell'esercizio 3, dimenticare l'ordine interno del blocco (4!4!).

Versione ripasso

Testo (esercizi di combinatoria dagli appelli).

  1. (Appello 3, 12 luglio 2017.) Contare gli anagrammi di MARTELLO che non cominciano con MAR.
  2. (Appello 3, a.a. 2017/18.) Quanti sono gli anagrammi di SANSCRITO nei quali non vi sono due S vicine?
  3. (Appello 4, a.a. 2017/18.) Quanti sono i modi per allineare, di faccia, 5252 carte da gioco in modo che i 44 assi siano vicini fra loro?
  4. (Appello 4, a.a. 2015/16.) Qual è la probabilità che, distribuendo a caso venti carte da gioco diverse in venti contenitori (vuoti), nessuno dei contenitori resti vuoto? Esprimere il risultato in forma di frazione.

Teoria: 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 →, 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 →, Probabilità uniforme su uno spazio finitoSu uno spazio campionario finito Ω con esiti equiprobabili la probabilità uniforme è P(A) = |A|/|Ω| (casi favorevoli su casi possibili); equivalentemente P({ω}) = 1/|Ω| per ogni esito. Gli eventi sono i sottoinsiemi di Ω. Proprietà: P(∅) = 0, P(Ω) = 1, P(A ∪ B) = P(A) + P(B) − P(A ∩ B), P(Aᶜ) = 1 − P(A). Scegliere Ω in modo che gli esiti siano davvero equiprobabili è una scelta di modello, non di matematica (dado con facce ripetute, somma di due dadi, paradosso dei compleanni).Probabilità uniforme su uno spazio finito →.

  1. MARTELLO: 88 lettere, L doppia: 8!2!=20 160\frac{8!}{2!} = 20\,160. Quelli che iniziano con MAR: anagrammi di T, E, L, L, O: 5!2!=60\frac{5!}{2!} = 60. Per complementare: 20 160−60=20 10020\,160 - 60 = 20\,100.
  2. SANSCRITO: 99 lettere, S doppia, totale 9!2!=181 440\frac{9!}{2!} = 181\,440. Metodo dei buchi: si dispongono le 77 lettere diverse da S (7!=50407! = 5040), che lasciano 88 buchi; le S (uguali) occupano un insieme di 22 buchi: (82)=28\binom82 = 28. Totale 5040⋅28=141 1205040\cdot28 = 141\,120. Controllo: con le S vicine (SSSS in blocco, 8!=40 3208! = 40\,320) 181 440−40 320=141 120181\,440 - 40\,320 = 141\,120.
  3. Blocco dei 44 assi: 4949 oggetti, 49!49! allineamenti, per l'ordine interno 4!4!: 49!⋅4!49!\cdot4!. (Probabilità a caso: 49! 4!52!=2452⋅51⋅50≈0.00018\frac{49!\,4!}{52!} = \frac{24}{52\cdot51\cdot50}\approx0.00018.)
  4. Esiti: funzioni carte →\to contenitori, 2020-sequenze di I20I_{20}, 202020^{20} equiprobabili. Nessun vuoto con 2020 carte e 2020 contenitori significa una biiezione: 20!20! casi. P=20!2020≈2.3⋅10−8P = \frac{20!}{20^{20}}\approx2.3\cdot10^{-8}

Errori tipici: dimenticare le lettere ripetute; nel metodo dei buchi ordinare le S (sono uguali: si sceglie un insieme di buchi); dimenticare l'ordine interno del blocco (4!4!).

Teoria collegata