Capitolo 4 - Dipartimento di Matematica

4.3 Esercizi
105
dove
S1 (A1 , ..., An ) = C(n, 1)(n − 1)! = n!,
n!
S2 (A1 , ..., An ) = C(n, 2)(n − 2)! = ,
2!
.........
n!
Sk (A1 , ..., An ) = C(n, k)(n − k)! = ,
k!
.........
n!
Sn (A1 , ..., An ) = C(n, n)(n − n)! =
= 1.
n!
Sommando i vari termini e raccogliendo n! si ottiene il risultato.
�
Esempio 4.24 (Il problema dei cappelli) Ognuna delle n persone che sono entrate
in un locale ha lasciato il proprio cappello alla guardarobiera. In quanti modi si possono ridistribuire gli n cappelli in modo che tutti abbiano un cappello diverso dal
proprio? Se la guardarobiera ubriaca distribuisce a caso i cappelli in uscita, qual è la
probabilità che nessuno riprenda il proprio cappello?
Soluzione. Etichettiamo persone e cappelli con In , assumendo che il cappello i appartenga alla persona i. Indichiamo l’esito di una distribuzione di cappelli con una
n-sequenza di In , dove il termine all’i-esimo posto è il cappello ricevuto dalla iesima persona. L’evento che nessuno riceva il proprio cappello è costituito da tutti gli
scombussolamenti di (1, ..., n) che sono in tutto Dn . Se la distribuzione di cappelli
avviene casualmente, ogni n-sequenza di In è ugualmente probabile: la probabilità di
un tale evento vale quindi
Dn
1
1
1
(−1)n
= 1 − + − + ... +
.
n!
1! 2! 3!
n!
Si noti che essendo
e−1 = 1 − 1 +
1
1
1
− + ... + (−1)n + ...
2! 3!
n!
tale probabilità, per n grande, si avvicina a 1/e.
4.3 Esercizi
Esercizio 4.1 Un pasticcere prepara dei cesti di 6 ovetti di cioccolato; questi possono
avere la carta che li confeziona di 5 colori: Blu, Verde, Rossa, Bianca, Gialla. L’ordine
con cui sono collocati gli ovetti nel cesto non conta.
(a) Qual è il numero massimo di cesti distinti che può formare?
106
Inclusione/esclusione
(b) La pasticceria dispone di tutti i cesti che si possono formare in questo modo. Un
signore compra tutti i cesti nei quali vi sia almeno un ovetto Blu o esattamente 2
ovetti Gialli. Quanti ne compra?
Esercizio 4.2 In quanti modi è possibile dare 16 caramelle ad un bimbo, da un grande
cesto contenente caramelle al limone, alla menta ed al rabarbaro, in modo che ne
riceva esattamente 3 di almeno uno dei gusti?
Esercizio 4.3 Determinare il numero di mani di 13 carte da un mazzo di 52, che
hanno 4 Re, o 4 Assi, o esattamente quattro picche.
Esercizio 4.4 Quante parole di 5 lettere si possono formare utilizzando un alfabeto di
26 lettere (con possibili ripetizioni) in modo che ogni parola cominci oppure finisca
con una vocale?
Esercizio 4.5 In quanti modi possiamo formare una sequenza di lunghezza 5 utilizzando un alfabeto di 3 lettere in modo che almeno due lettere consecutive
coincidano?
Esercizio 4.6 Supponiamo che in una libreria ci siano 200 libri, 70 in francese e 100
di argomento matematico. Quanti sono i libri non scritti in francese e di argomento
diverso dalla matematica se ci sono 30 libri francesi di matematica?
Esercizio 4.7 200 studenti possono frequentare tre corsi di Matematica: Matematica
Discreta, Analisi e Geometria. Ogni corso è seguito da 80 studenti. Ogni coppia di
discipline ha 30 studenti in comune; 15 studenti frequentano tutte e tre le materie.
(a) Quanti sono gli studenti che non frequentano nessuna delle tre discipline?
(b) Quanti sono gli studenti che frequentano solo il corso di Matematica Discreta?
Esercizio 4.8 Quanti sono i numeri tra 1 e 30 che sono primi con 30?
Esercizio 4.9 Quante sono le 10 sequenze di I9 nelle quali compaiono le cifre 1,2 e
3?
Esercizio 4.10 Quanti sono i modi di distribuire 20 persone diverse in 3 aule in modo
che in ogni aula vi sia almeno una persona?
Esercizio 4.11 Quanti sono gli anagrammi di SALUMI dove si verifichi almeno una
delle tre possibilità: (i) S precede A, (ii) A precede L, (iii) L precede U? Per precedere
si intende che sia posizionata prima, non necessariamente immediatamente prima.
Esercizio 4.12 I Brusegan, i Visentin e i Casarin hanno ciascuno 5 figli. Se i 15 figli
campeggiano in 5 tende differenti, 3 per ogni tenda, e sono assegnati in maniera casuale alle 5 tende, qual è la probabilità che ogni famiglia abbia almeno due dei suoi
figli nella stessa tenda?
4.3 Esercizi
107
Esercizio 4.13 Qual è la probabilità che una mano di 13 carte prese da un mazzo di
52 abbia:
(a) almeno un seme mancante?
(b) almeno una carta di ogni seme?
(c) almeno una carta per ogni tipo di figura (cioè almeno un asso, almeno un jack,
almeno una regina ed almeno un re)?
Esercizio 4.14 Quante sono le 9-sequenze di I3 nelle quali compaiono tre 1, tre 2 e
tre 3, senza tre numeri uguali consecutivi?
Esercizio 4.15 Quante sono le permutazioni delle 21 lettere dell’alfabeto italiano che
non contengono nessuna delle seguenti parole: ARCO, UVE, LUNA, GIN.
Esercizio 4.16 In quanti modi si possono distribuire 25 palline identiche in 6 contenitori distinti in modo che vi siano al massimo 6 palline in uno qualunque dei primi
3 contenitori?
Esercizio 4.17 Uno stregone ha 5 amici. Durante una lunga conferenza di stregoni,
è andato a cena con ogni amico 10 volte, ogni data coppia di amici 5 volte, ogni data
terna di amici 3 volte, ogni data quaterna di amici 2 volte ed una volta sola con tutti e
5 gli amici. Se inoltre lo stregone ha cenato 6 volte da solo, quanti giorni è durata la
conferenza?
Esercizio 4.18 Supponiamo che in un dipartimento di matematica vi siano 10 corsi
che devono essere assegnati a 5 professori diversi. In quanti modi si possono assegnare a ciascuno dei 5 professori due corsi all’anno in due anni accademici successivi in
modo che nessun professore insegni gli stessi 2 corsi entrambi gli anni?
Esercizio 4.19 Quante permutazioni di (1, 2, ..., n) ci sono, nelle quali i non sia immediatamente seguito da i + 1, con 1 ≤ i ≤ n − 1, e n non sia immediatamente
seguito da 1?
Esercizio 4.20 In quanti modi si possono distribuire 10 libri a 10 ragazzi (uno ad ogni
ragazzo), ed in seguito raccogliere i libri e ridistribuirli in modo che tutti i ragazzi
abbiano un nuovo libro?
Esercizio 4.21 In una città vengono venduti 3 giornali: A,B e C. Da un’indagine
risulta che il 47% degli abitanti legge il giornale A, il 34% il giornale B, il 12% il
giornale C; l’8 % legge A e B, il 5% A e C, il 4% B e C; infine il 4% legge tutti e 3 i
giornali. Se si sceglie a caso una persona, trovare la probabilità che
(a) non legga alcun giornale;
(b) legga un solo giornale;
108
Inclusione/esclusione
Esercizio 4.22 Dobbiamo inserire in una tabella, di 4 righe e 6 colonne, 9 numeri
distinti compresi tra 1 e 90 (estremi inclusi).
(a) Quante tabelle distinte si possono realizzare?
(b) Quante sono le tabelle che hanno una riga vuota oppure il 90 nella prima riga?
Esercizio 4.23 È assegnato un alfabeto composto da 13 simboli distinti.
(a) Quante parole di 8 lettere contenenti almeno un simbolo ripetuto esattamente 3
volte è possibile scrivere?
(b) Quante parole di 8 lettere contenenti almeno due simboli distinti ripetuti
esattamente 3 volte è possibile scrivere?
Esercizio 4.24 Si considerano le carte rosse di un mazzo da poker di 52 carte (13 di
cuori, 13 di quadri). Distribuisco a 13 persone prima le carte di cuori e poi le carte di
quadri (una carta ciascuno di ogni tipo).
(a) Quanti sono i possibili esiti di tale distribuzione?
(b) Qual è la probabilità che almeno una persona riceva una coppia (due carte con lo
stesso numero)?
Soluzioni degli esercizi
Soluzione es. 4.1. (a) Il numero massimo di cesti possibili è uguale al numero di 5risoluzioni di 6, ovvero C(6 + 4, 4) = 210.
(b) Indichiamo con B l’insieme dei cesti con almeno un ovetto blu e con G
l’insieme dei cesti con esattamente 2 ovetti gialli. Si ha
|B ∪ G| = |B| + |G| − |B ∩ G| = C(5 + 4, 4) + C(4 + 3, 3) − C(3 + 3, 3) = 141
Soluzione es. 4.2. Siano AL , AM , AR le distribuzioni di caramelle nelle quali il bimbo riceve rispettivamente esattamente 3 caramelle al limone, alla menta, al rabarbaro.
Dobbiamo calcolare |AL ∪ AM ∩ AR |. Si ha
|AL ∪AM ∩AR | = |AL |+|AM |+|AR |−|AL ∩AM |−|AL ∩AR |−|AM ∩AR |+|AL ∩AM ∩AR |
Ora |AL | = |AM | = |AR | è il numero di 2-risoluzioni di 16 − 3 = 13, ovvero
C(14, 1) = 14; analogamente |AL ∩ AM | = |AL ∩ AR | = |AM ∩ AR | = 1 e
|AL ∩ AM ∩ AR | = 0. Pertanto
|AL ∪ AM ∩ AR | = 14 × 3 − 3 + 0 = 39
Soluzione es. 4.3. Siano AR , A1 e AP le mani contenenti rispettivamente quattro Re,
quattro assi, quattro picche. Si ha
� � � �� � � �
� � � � � � � �
48
13
39
44
12
36
11
33
|AR ∪A1 ∪AP | = 2
+
−
−2
×
+
×
.
9
4
9
5
3
6
2
3
4.3 Esercizi
109
Soluzione es. 4.4. Indichiamo con C ed F rispettivamente l’insieme delle parole che
cominciano con una vocale e che finiscono con una vocale. Dobbiamo calcolare |C ∪
F |. Si ha |C| = 5 × 264 = |F |, |C ∩ F | = 52 × 263 . Pertanto
|C ∪ F | = |C| + |F | − |C ∩ F | = 5 × 264 + 5 × 264 − 52 × 263 = 4 130 360
Soluzione es. 4.5. Indichiamo con Xi le sequenze nelle quali la i-esima e la i + 1esima lettera coincidono, i = 1, ..., 4. Dobbiamo calcolare |X1 ∪ ... ∪ X4 |. Si ha
|Xi | = 35−1 ; |Xi ∩ Xi+1 | = 35−2 ; se i + 1 < j abbiamo |Xi ∩ Xj | = 35−2 ;
|Xi ∩ Xi+1 ∩ Xi+2 | = 35−3 ; |X1 ∩ X2 ∩ X4 | = |X1 ∩ X3 ∩ X4 | = 35−3 ;
|X1 ∩ X2 ∩ X3 ∩ X4 | = 3. Si ha
� �
� �
� �
4
4
4
5−1
5−2
5−3
|X1 ∪ ... ∪ X4 | = 4 × 3
−
×3
+
×3
−
× 35−4 = 195
2
3
4
Soluzione es. 4.6. Indichiamo con F e M rispettivamente gli insiemi dei libri in
francese e di quelli di carattere matematico. Dobbiamo calcolare |F c ∩ M c |. Si ha
|F c ∩ M c | = |(F ∪ M )c | = 200 − |F ∪ M | = 200 − [|F | + |M | − |F ∩ M |] =
= 200 − 70 − 100 + 30 = 60
Soluzione es. 4.7. Indichiamo con D, A e G rispettivamente gli insiemi degli studenti
di Matematica Discreta, Analisi e Geometria.
(a): Dobbiamo calcolare |Dc ∩ Ac ∩ Gc |. Si ha
|Dc ∩ Ac ∩ Gc | = |(D ∪ A ∪ G)c | = 200 − |D ∪ A ∪ G| =
= 200 − [|D| + |A| + |G| − |D ∩ A| − |D ∩ G| − |G ∩ A| + |D ∩ A ∩ G|] =
= 200 − 3 × 80 + 3 × 30 − 15 = 35
(b): Dobbiamo calcolare la cardinalità di S = D ∩ Ac ∩ Gc . Si ha
80 = |D| = |S| + |D \ S| = |S| + [|D ∩ A| + |D ∩ G| − |D ∩ A ∩ G| =
Pertanto |S| = 35.
= |S| + [30 + 30 − 15] = |S| + 45
Soluzione es. 4.8. Indichiamo con A2 , A3 e A5 i numeri ra 1 e 30 divisibili
rispettivamente per 2, 3, 5. Dobbiamo calcolare |Ac2 ∩ Ac3 ∩ Ac5 |. Si ha
|Ac2 ∩ Ac3 ∩ Ac5 | = |(A2 ∪ A3 ∪ A5 )c | =
30 − 15 − 10 − 6 + 5 + 3 + 2 − 1 = 8
110
Inclusione/esclusione
Soluzione es. 4.9. Indichiamo con Ai , i = 1, 2, 3, le 10 sequenze di I9 nelle quali non
compare il numero i. Dobbiamo calcolare |Ac1 ∩ Ac2 ∩ Ac3 |. Si ha
|Ac1 ∩ Ac2 ∩ Ac3 | = |(A1 ∪ A2 ∪ A3 )c | = 910 − |(A1 ∪ A2 ∪ A3 )| =
� �
3
10
10
9 − [3 × 8 ] + [
× 710 ] − [61 0] = 1 052 518 500
2
Soluzione es. 4.10. Etichettate con I3 le aule, ogni distribuzione delle persone corrisponde ad una 20-sequenza di I3 . Indichiamo con Xi , i = 1, 2, 3, le 20 sequenze di
I3 in cui non compare il numero i. Dobbiamo calcolare |X1c ∩ X2c ∩ X3c |. Si ha
|X1c ∩ X2c ∩ X3c | = |(X1 ∪ X2 ∪ X3 )c | = 320 − |X1 ∪ ... ∪ Xn | =
= 320 − 3 × 220 + 3 = 3 483 638 676
Soluzione es. 4.11. Indichiamo con XSA , XAL e XLU rispettivamente gli insiemi di parole dove S precede A, A precede L, L precede U. Dobbiamo calcolare
|XSA ∪ XAL ∪ XLU |. Una parola in XSA si costruisce decidendo quante lettere
inserire prima della S, quante tra la S e la A e quante dopo la A, e poi negli spazi
decisi inserendo una 4-sequenza senza ripetizioni di {L, �
U, �
M, I}. Pertanto prima
6
calcoliamo le soluzioni di x1 + x2 + x3 = 4 che sono
, e poi le 4-sequenze
2
senza ripetizioni
|XSA | = |XAL | =
� � di {L, U, M, I} che sono 4! Si ha �dunque
�
6
6
|XLU | =
× 4! Analogamente |XSA ∩ XAL | =
× 3! = |XLU ∩ XAL | e
2
3
� �
6
|XSA ∩XAL ∩XLU | =
×2! Per quanto riguarda |XSA ∩XLU | si può procedere
4
cosı̀: sia P una parola in XSA e P � la parola ottenuta da P scambiando le lettere L e
1
U ; una ed una sola tra P e P � appartiene a XLU e quindi |XSA ∩ XLU | = |XSA |.
2
Allora
� �
� �
� �
� �
1 6
6
6
6
×2! = 690
|XSA ∪XAL ∪XLU | =
×4!×3−
×3!×2−
×4!+
4
2
3
2
2
Soluzione es. 4.12. Etichettiamo con I5 le tende. Le possibili assegnazioni dei 15 figli
nelle tende sono S(5, 15; (3, 3, 3, 3, 3)). Vanno evitate le assegnazioni nelle quali c’è
una tenda nella quale è stato alloggiato un figlio di ogni famiglia. Indichiamo con Ai
le assegnazioni nelle quali nella tenda i c’è un figlio di ogni famiglia. Si ha
� �
5
|A1 ∪...∪A5 | = 5×[53 ×S(4, 12; (3, 3, 3, 3))]−
×[53 ×43 ×S(3, 9; (3, 3, 3))]+
2
� �
� �
5
5
3
3
3
+
×[5 ×4 ×3 ×S(2, 6; (3, 3))]−
×[53 ×43 ×33 ×23 ×S(1, 3; (3))]+
3
4
4.3 Esercizi
111
� �
5
+
× [53 × 43 × 33 × 23 × 13 ] = 132 888 000
5
Infatti si ottiene un’assegnazione in Ai scegliendo chi mettere nella tenda i (53 modi)
e poi riempiendo le altre 4 tende (S(4, 12; (3, 3, 3, 3)) modi); un’assegnazione in
Ai ∩ Aj , i < j , scegliendo chi mettere nella tenda i (53 modi), chi nella tenda j (43
modi) e poi riempiendo le altre 3 tende (S(3, 9; (3, 3, 3)) modi); ... e cosı̀ via.
La probabilità cercata è dunque
1 − 132 888 000/
15!
3!5 × 132 888 000
=
1
−
≈ 0.9753 = 97, 53%
3!5
15!
Soluzione es. 4.13. Indichiamo con AC , AQ , AF , AP le mani di 13 carte rispettivamente prive di cuori, quadri, fiori e picche.
(a): dobbiamo calcolare |AC ∪ AQ ∪ AF ∪ AP | =
� � � � � � � �� �
39
4
26
4
13
=4×
−
×
+
= 32 427 298 180
13
2
13
3
13
(b): dobbiamo calcolare
�
52
− |AC ∪ AQ ∪ AF ∪ AP | = 602 586 261 420
|(AC ∪ AQ ∪ AF ∪ AP ) | =
13
c
�
(c): Siano XA , XK , XQ , XJ le mani di 13 carte prive rispettivamente di assi,
re, donne, jack. Si ha
� �
52
c
c
c
c
c
|XA ∩XK ∩XQ ∩XJ | = |(XA ∪XK ∪XQ ∪XJ ) | =
−|XA ∪XK ∪XQ ∪XJ | =
13
� �
� � � � � � � � � � � � � �
52
48
4
44
4
40
4
36
−[4×
−
×
+
×
−
×
] = 128 971 619 088
13
13
2
13
3
13
4
13
Soluzione es. 4.14. Indichiamo con Ai , i = 1, 2, 3, le 9 sequenze di I3 in cui compaiono tre i consecutivi. Dobbiamo calcolare |Ac1 ∩ Ac2 ∩ Ac3 |. Tenendo conto che
le sequenze in A1 , ad esempio, possono essere viste come 7 sequenze di {111, 2, 3}
con occupancy (1, 3, 3), si ha
|Ac1 ∩ Ac2 ∩ Ac3 | = |(A1 ∪ A2 ∪ A3 )c | = S(3, 9; (3, 3, 3)) − |A1 ∪ A2 ∪ A3 | =
=
9!
− [3 × S(3, 7; (1, 3, 3)) − 3 × S(3, 5; (1, 1, 3)) + S(3, 3; (1, 1, 1))] = 1 314
3!3
Soluzione es. 4.15. Siano XARCO , XU V E , XLU N A , XGIN le permutazioni di
(A, B, C, ..., Z) che contengono rispettivamente le sottoparole ARCO, UVE,
LUNA, GIN. Dobbiamo calcolare
c
c
c
c
|XARCO
∩XUc V E ∩XLU
N A ∩XGIN | = |(XARCO ∪XU V E ∪XLU N A ∪XGIN ) | =
112
Inclusione/esclusione
21! − |XARCO ∪ XU V E ∪ XLU N A ∪ XGIN | =
= 21! − [|XARCO | + |XU V E | + |XLU N A | + |XGIN | − ...]
Ora si osservi che ARCO, UVE, GIN non hanno lettere in comune, mentre LUNA ha
una lettera in comune con ciascuna delle altre. Una permutazione in XARCO è una
permutazione della 18-sequenza (ARCO, B, D, E, ..., N, P, Q, S, ..., Z); pertanto
XARCO ha cardinalità 18! Analogamente XARCO ∩ XU V E è l’insieme delle permutazioni della 16-sequenza (ARCO, U V E, B, D, F, ..., N, P, Q, S, T, Z) e quindi
ha cardinalità 16! L’intersezione XARCO ∩ XLU N A è l’insieme delle permutazioni
della 15-sequenza (LU N ARCO, B, D, ..., I, M, P, Q, S, T, V Z) e quindi ha cardinalità 15! Le intersezioni XU V E ∩ XLU N A , XGIN ∩ XLU N A sono vuote. Cosı̀
procedendo si ottiene
21! − |XARCO ∪ XU V E ∪ XLU N A ∪ XGIN | =
= 21!−[18!+19!+18!+19!−16!−16!−15!−17!−0−0+14!+0+0+0−0] =
= 50 835 245 976 984 268 800
Soluzione es. 4.16. Indichiamo con Xi , i = 1, 2, 3, le distribuzioni di palline con
rispettivamente almeno 7 palline nel contenitore i. Dobbiamo calcolare |X1c ∩ X2c ∩
X3c |:
� �
30
c
c
c
c
− |X1 ∪ X2 ∪ X3 | =
|X1 ∩ X2 ∩ X3 | = |(X1 ∪ X2 ∪ X3 ) | =
5
� �
� �
� � � �
30
23
16
9
=
− [3 ×
−3×
+
] = 54 537
5
5
5
5
Soluzione es. 4.17. La durata della conferenza corrisponde al numero di cene fatte
dallo stregone. Etichettati con I5 gli amici dello stregone, rappresentiamo con Xi ,
i ∈ I5 , l’insieme delle cene a cui ha partecipato l’amico i. Allora la durata della
conferenza è uguale a giorni
� �
� �
� �
5
5
5
6 + |X1 ∪ ... ∪ X5 | = 6 + 5 × 10 −
×5+
×3−
× 2 + 1 = 27
2
3
4
Soluzione es. 4.18. Etichettati con I10 i corsi e con I5 i docenti, l’assegnazione di due
corsi per il primo anno può essere fatta fissando una qualunque 10-sequenza di I5
con occupancy (2, 2, 2, 2, 2). Ora decisa l’assegnazione per il primo anno dobbiamo
scegliere quella per il secondo. Se indichiamo con Xi , i = 1, ..., 5, le assegnazioni
dei 10 corsi per il secondo anno che vedono il professore i ricevere gli stessi corsi
dell’anno precedente, per il secondo anno abbiamo |X1c ∩ ... ∩ X5c | assegnazioni
possibili. Si ha
|X1c ∩ ... ∩ X5c | = |(X1 ∪ ... ∪ X5 )c | = S(5, 10; (2, 2, 2, 2, 2)) − |X1 ∪ ... ∪ X5 | =
4.3 Esercizi
113
� �
5
= S(5, 10; (2, 2, 2, 2, 2)) − [5 × S(4, 8; (2, 2, 2, 2)) −
× S(3, 6; (2, 2, 2))+
2
� �
� �
5
5
+
× S(2, 4; (2, 2)) −
× S(1, 2; (2)) + 1] = 101 644
3
4
Pertanto le assegnazioni per i due anni possono essere assegnate in
S(5, 10; (2, 2, 2, 2, 2)) × 101 644 = 11 526 429 600 modi.
Soluzione es. 4.19. Sia Xi , 1 ≤ i ≤ n − 1, l’insieme delle permutazioni di
(1, 2, ..., n) nelle quali i sia seguito da i + 1 e Xn l’insieme delle permutazioni
di (1, 2, ..., n) nelle quali n è seguito da 1. Dobbiamo calcolare |X1c ∩ ...Xnc |. Si ha
|X1c ∩ ... ∩ Xnc | = |(X1 ∪ ... ∪ Xn )c | = n! − |X1 ∪ ... ∪ Xn | =
� �
� �
n
n−1 n
= n! − [n × (n − 1)! −
× (n − 2)! + ... + (−1)
] = Dn
2
n
dove Dn è il numero degli scombussolamenti di (1, 2, ..., n).
Soluzione es. 4.20. Etichettati con I10 sia i libri che i ragazzi, le distribuzioni di libri sono tante quante le permutazioni di (1, 2, ..., 10), ovvero 10! Nella seconda distribuzione devo prendere uno scombussolamento della sequenza scelta nella prima
distribuzione. Pertanto in tutto le due distribuzioni possono essere fatte in
10! × D10 = 10! × 10!(1 −
1
1
1
1
+ − + ... +
) = 4 844 306 476 800
1! 2! 3!
10!
Soluzione es. 4.21. Indichiamo con XA , XB e XC gli insiemi di persone che leggono
rispettivamente i giornali A,B e C e con X l’insieme degli abitanti della città.
(a): Si ha
P (Ac ∩ B c ∩ C c ) =
=1−[
|Ac ∩ B c ∩ C c |
|A ∪ B ∪ C|
=1−
=
|X|
|X|
|A|
|B|
|C|
|A ∩ B| |A ∩ C| |B ∩ C| |A ∩ B ∩ C|
+
+
−
−
−
+
=
|X| |X| |X|
|X|
|X|
|X|
|X|
= 1 − 0.47 − 0.34 − 0.12 + 0.08 + 0.05 + 0.04 − 0.04 = 0.2 = 20%
(b): Dal punto precedente sappiamo che il 80% della popolazione legge almeno
un giornale. La probabilità cercata è
P (A∪B∪C)−P ((A∩B)∪(A∩C)∪(B∩C)) = 0.8−[
= 0.8−[
|(A ∩ B) ∪ (A ∩ C) ∪ (B ∩ C)|
=
|X|
|A ∩ B| + |A ∩ C| + |B ∩ C| |A ∩ B ∩ C|
−
= 0.8−0.08−0.05−0.04+0.04 = 0.67 = 67%
|X|
|X|
114
Inclusione/esclusione
Soluzione es. 4.22. (a) Ogni tabella può essere realizzata nelle seguenti fasi: 1) scelta
di 9 posizioni ove inserire i numeri; 2) scelta dei numeri da mettere nella prima, nella
seconda, ..., nella nona posizione. In tutto abbiamo un numero di scelte pari a
� �
24
× S(90, 9) = 188 490 124 624 286 522 822 400
8
(b) Sia A∅ l’insieme delle tabelle con una riga vuota e A90 quello delle tabelle
con il 90 nella prima riga.
|A∅ ∪ A90 | = |A∅ | + |A90 | − |A∅ ∩ A90 | =
� �
� �
� �
18
23
17
=4×
× S(90, 9) + 6 ×
× S(89, 8) − 3 × 6 ×
× S(89, 8) =
9
8
8
= 56 973 572 375 629 752 944 640
Soluzione es. 4.23. Etichettiamo con I13 l’alfabeto. Ogni parola di 8 lettere corrisponde ad una 8-sequenza di I13 . Sia Xi , i ∈ I13 , l’insieme delle parole nelle quali il
simbolo i è ripetuto esattamente tre volte.
(a): dobbiamo calcolare
� �
� � � �� �
8
13
8
5
5
|X1 ∪ ... ∪ X13 | = 13 ×
× 12 −
×
× 112 = 175 864 416.
3
2
3
3
(b): dobbiamo calcolare
| ∪i<j
� � �� �
5
13
8
× 112 = 5 285 280
(Xi ∪ Xj )| =
×
3
2
3
�
Soluzione es. 4.24. Ogni distribuzione corrisponde ad assegnare due permutazioni
della sequenza (1, 2, 3, ..., 13).
(a): vi sono 13!2 = 38 775 788 043 632 640 000 possibili distribuzioni.
(b): Nessuna persona riceve una coppia se e solo se la seconda permutazione è
uno scombussolamento della prima. La probabilità cercata è pertanto
1−
13! × D13
1
1
1
= 1 − (1 − + − ... −
) ≈ 0.632 = 63.2%
2
13!
1! 2!
13!