ESERCITAZIONE DI MATEMATICA DISCRETA (21 DICEMBRE 2011) Esercizio 1. Si considerino gli insiemi A={1,2,3,4,5}, B={a,b,c} e il grafo semplice non orientato in cui i vertici sono le funzioni f: AB e in cui due vertici distinti f,g sono collegati da un arco se f(4)=g(4).Quante componenti connesse ha il grafo ? Qual è il numero cromatico del grafo ? In ogni componente connessa (considerata come grafo a sé stante) esiste un cammino Euleriano ?
Soluzione: Nel grafo vi sono 3 componenti connesse: la prima contenente le funzioni f tali che f(4)=1, la seconda quelle tali che f(4)=b, la terza quelle tali che f(4)=c. In ogni componente connessa vi sono 3
4vertici, tutti adiacenti fra loro: quindi 3
4è il numero cromatico di ogni componente, e quindi anche dell’intero grafo. Ogni vertice di una componente è adiacente a tutti gli altri 3
4-1 vertici, quindi il suo grado è 3
4-1 (pari): esiste in ogni componente un cammino (ciclico) Euleriano.
Esercizio 2. Considerati gli insiemi A={1,2,3,4,5,6,7,8}, B={1,2,3,4,5,6,7,8,9,10}, e tutte le possibili funzioni f: A B, si definisca una funzione di tipo a se tutte le immagini degli elementi di A coincidono, di tipo b se le immagini degli elementi di A sono <8, di tipo c se se le immagini degli elementi di A sono numeri dispari.
Calcolare il numero delle funzioni che appartengono ad almeno uno dei tipi precedenti.
Soluzione: Si può applicare il principio di inclusione esclusione in forma positiva: se X,Y,Z sono gli insiemi delle funzioni rispettivamente di tipo a,b,c, si deve calcolare
XYZ=X+Y+Z-[XY+XZ+YZ]+XYZ= 10+7
8+5
8- [7+5+4
8]+4 (dove i risultati numerici si ottengono applicando il Principio delle scelte multiple)
.Esercizio 3. Si consideri l’insieme A={1,2,3,4,5,6} e l’insieme B di tutti i possibili
sottoinsiemi di A. Calcolare il numero delle funzioni f: A B tali che f(1) sia un
sottoinsieme di cardinalità 4.
Soluzione: Per ognuna delle funzioni da contare, l’immagine di 1 si può scegliere in
4 6
modi diversi; fissata tale immagine, l’immagine di ognuno dei rimanenti 5
elementi si può scegliere in 2
6modi diversi. La risposta è il prodotto
4 6
(2
6)
5.
Esercizio 4. In una vasca vi sono moltissimi pesci, di 8 specie differenti: vi sono almeno 8 esemplari di ogni specie, e gli esemplari della stessa specie sono indistinguibili. Si immerge un retino nella vasca e si pescano 8 pesci. Quanti sono i possibili diversi risultati di questa pesca ?
Soluzione: Ogni pesca è una combinazione con ripetizione delle 8 specie prese ad 8
ad 8: il numero di tali combinazioni è
18 18 8
=
7 15
.
Esercizio 5. Calcolare quanti sono i numeri naturali di 12 cifre, con le cifre scelte fra 1,2,3,4,5,6,7,8,9, tali che il numero di cifre pari sia uguale al numero di cifre dispari.
Calcolare poi quelli tali che il numero di cifre pari sia diverso dal numero di cifre dispari.
Soluzione: Per rispondere al primo quesito si può usare il principio delle scelte multiple: le scelte per le 6 posizioni delle cifre pari sono in numero di
6
12
; fissata una di tali scelte, il contenuto (cifra pari) di queste 6 posizioni si può scegliere in 4
6modi diversi; fissate le cifre pari, la posizione delle cifre dispari è obbligata, e il contenuto (cifra dispari) di queste 6 posizioni si può scegliere in 5
6modi diversi. La risposta al primo quesito è
6
12
4
65
6.
La risposta al secondo quesito si ottiene sottraendo dal numero totale dei naturali di 12 cifre, con cifre 1,2,3,4,5,6,7,8,9, (che è 9
12), il numero di quelli in cui il numero di cifre pari è uguale al numero di cifre dispari : 9
12-
6
12
