Compito di Matematica Discreta I (3 marzo 2009) Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento Esercizio 1.

Compito di Matematica Discreta I (3 marzo 2009)

Avvertenza: il punteggio massimo alle risposte viene attribuito solo in caso di giustificazioni dettagliate del ragionamento

Esercizio 1. Dati l’insieme A di tutte le matrici booleane 2x2 e l’insieme B di tutti i sottoinsiemi dell’insieme {a,b,c,d,e}, dire qual è maggiore fra il numero delle funzioni f: AB e il numero delle funzioni f: BA.

Dire inoltre qual è maggiore fra il numero delle funzioni surgettive f: AB e il numero delle funzioni iniettive f: BA. ( 5 p.)

Esercizio 2. Calcolare il numero di parole di lunghezza 8 sull’alfabeto {a,b,c,d,e,f,i}

tali che il numero di vocali presenti nella parola sia il triplo del numero di consonanti presenti nella parola. ( 6 p.)

Esercizio 3. Dimostrare che la seguente affermazione è vera per ogni numero naturale n: il numero (4n

-4n+56)/28 è intero. (4 p.)

Esercizio 4. Si consideri il grafo semplice non orientato in cui i vertici sono i numeri naturali di 7 cifre (in base 10) con cifre scelte nell’insieme {2,3,5,7} e in cui due vertici distinti x,y sono adiacenti se la somma della seconda cifra di x e della seconda cifra di y è un multiplo di 5.

Quante componenti connesse ha il grafo ? (3 p.) Qual è il numero cromatico del grafo ? (3 p.)

In ogni componente (considerata come grafo a sé stante) esiste un cammino Euleriano ? (3 p.)

Esercizio 5. Calcolare il numero di parole di lunghezza 4 sull’alfabeto {a,b,c,d,e,f,i}

in cui almeno 2 lettere in posizioni consecutive siano vocali. (6 p.)