26  39 

ESERCIZI MATEMATICA DISCRETA (23/01/09) Soluzioni

Esercizio 1. Si può applicare il principio di inclusione-esclusione in forma negativa. Se A è l’insieme di tutte le parole di lunghezza 5 sull’alfabeto {a,b,c,d,e,f,g,i} (che ha cardinalità 8

), e se B,C sono i sottoinsiemi di A contenenti rispettivamente le parole che soddisfano la condizione a) e la condizione b), si deve calcolare A-BC, dove:

BC=B+C-BC=38

+8

-38

dunque la risposta al quesito è: 8

-[38

+8

-38

]

Esercizio 2. Ogni anagramma è una parola di lunghezza 9 sull’alfabeto {c,a,r,m,e,l} in cui la lettera a è ripetuta 3 volte, la lettera l è ripetuta 2 volte, le lettere c,e,m,r sono ripetute ognuna 1 volta. Per calcolare il numero di tali parole si può usare il principio delle scelte multiple: il numero delle scelte delle 3 posizioni in cui inserire la lettera a è



 



 3

9

; fissata una di tali scelte, il numero delle scelte

delle 2 posizioni in cui inserire la lettera l è



 



 2

6

; fissata una di tali scelte, il numero delle scelte del contenuto delle rimanenti 4 posizioni è 4321=4!. La risposta al quesito è il prodotto di tali numeri.

Esercizio 3. Si può applicare il principio di induzione al predicato P(n)=”la somma dei primi n termini della successione è uguale a (n

+11n)/2”.

P(1) è vero perché a

=6=(1

+111)/2. Supponendo vero P(k), dimostriamo vero P(k+1)=”la somma dei primi k+1 termini della successione è uguale a [(k+1)

+11(k+1)]/2: ma la somma dei primi (k+1) termini della successione si ottiene sommando la somma dei primi k termini (che per ipotesi è uguale a (k

+11k)/2) al termine a

=(k+1)+5=k+6, ottenendo:

(k

+11k)/2 + (k+6) = (k

+11k+2k+12)/2 = (k

+2k+1+11k+11)/2 = [(k+1)

+11(k+1)]/2 come si voleva dimostrare.

Esercizio 4. Le scelte possibili per i fiori nei vasi con numero <5 sono in numero di 7654. Fissata una di tali scelte, le scelte possibili per i fiori nei vasi con numero >15 sono in numero di 6 54.

Fissata una scelta per i precedenti vasi, le scelte possibili per i rimanenti 11 vasi sono in numero di 11!.

La risposta al quesito, per il principio delle scelte multiple, si ottiene moltiplicando i tre numeri ottenuti.

Esercizio 5. I tre numeri coincidono tutti con 2

: basta applicare le formule che calcolano il numero di sottoinsiemi di un insieme finito, e il numero di funzioni fra insiemi finiti, tenendo conto che

AxB=67=42, C=2

, D=2

.