35 45  

Esercizi di Matematica Discreta I (22 gennaio 2010)

Soluzioni

Esercizio 1. Si può applicare il principio delle scelte multiple. Le possibilità per le prime 3 posizioni sono 765, e per le rimanenti 17 posizioni sono 17!, dunque le possibili classifiche sono 76517!

Esercizio 2. Fra 2 vertici distinti esiste un cammino se e solo se contengono lo stesso numero di a. Esistono dunque 4 componenti connesse: quella delle parole che contengono 1 lettera a (che sono 55

=3125), quella delle parole che contengono 2

lettere a (che sono 



 



 2 5

5

=1250), quella delle parole che contengono 3 lettere a (che

sono 



 



 3 5

5

=250), quella delle parole che contengono 4 lettere a (che sono 



 



 4 5

5

=25). In ogni componente tutti i vertici sono adiacenti fra loro, quindi il numero cromatico di ogni componente coincide con il numero dei vertici: il numero cromatico del grafo è dunque quello della prima componente, cioè 3125. Poichè il grado di un vertice in una componente è uguale al numero dei vertici meno 1, esistono cammini ciclici Euleriani nelle componenti con numero di vertici dispari.

Esercizio 3. Per costruire una delle funzioni cercate, si deve scegliere un sottoinsieme di B di cardinalità 3 e poi una funzione surgettiva da A in questo

sottoinsieme. La prima scelta si può fare in 



 



 3 7

diversi modi. Fissata tale scelta, la

seconda scelta si può fare in 3!S(5,3) modi possibili, dove S(5,3) è il numero di

Stirling. La risposta, per il principio delle scelte multiple è 



 



 3 7

3!S(5,3).

Esercizio 4. Usando il principio di inclusione-esclusione si tratta di calcolare la cardinalità dell'unione degli insiemi A

,A

,A

aventi rispettivamente come elementi i sottoinsiemi di A che sono contenuti in {a,b,c,d,e}, {a,c,d,f},{a,d,e,f}. Si ottiene:

A

A

A

=

A

+A

+A

-{A

A

+A

A

+A

A

}+A

A

A

=

= 2

+2

+2

-{2

+2

+2

}+2