Esercizio 41anagrammi e allineamenti dagli appelli

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, $52$ carte da gioco in modo che i $4$ 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 $8$ lettere, con la L ripetuta $2$ volte (le altre M, A, R, T, E, O una volta): $$\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 ($5$ lettere, L doppia): $\frac{5!}{2!} = 60$.

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

2. Anagrammi di SANSCRITO senza due S vicine

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

Metodo dei "buchi". Prima si dispongono le $7$ lettere diverse da S: $7! = 5040$ modi. Tra loro e agli estremi ci sono $8$ "buchi" ($\_\,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 $2$ buchi su $8$: $\binom82 = 28$. Ogni anagramma senza S vicine si ottiene in un solo modo, quindi (PM) $$7!\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: $8$ oggetti distinti, $8! = 40\,320$. E $181\,440 - 40\,320 = 141\,120$ ✓.

3. Le 52 carte con i 4 assi vicini

Metodo del blocco. Si incollano i $4$ assi in un blocco: insieme alle altre $48$ carte si hanno $49$ "oggetti" distinti da allineare, $49!$ modi. Dentro il blocco gli assi si possono ordinare in $4! = 24$ modi. Ogni allineamento con gli assi vicini determina l'ordine degli oggetti e quello interno al blocco: $$49!\cdot 4!$$ In probabilità: mescolando a caso, gli assi sono tutti vicini con probabilità $\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 $20$-sequenza di $I_{20}$ (per ogni carta, il suo contenitore). $|\Omega| = 20^{20}$, esiti equiprobabili.

Favorevoli. Nessun contenitore vuoto con $20$ carte e $20$ contenitori significa una carta per contenitore: la funzione è una biiezione, cioè una sequenza senza ripetizione, $20!$ casi. $$P = \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!$).