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

Compito di Matematica Discreta I (21 settembre 2007)

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

Esercizio 1. Dato un insieme A di cardinalità 8, si consideri il grafo semplice non orientato, in cui i vertici sono tutti i sottoinsiemi di A non vuoti e diversi da A, e in cui due vertici distinti x,y sono adiacenti se la cardinalità di x e quella di y sono numeri naturali consecutivi.

a) Calcolare il numero di componenti connesse del grafo (3 p.) b) Calcolare il numero cromatico del grafo (3 p.)

c) In ognuna delle componenti connesse, considerata come grafo a sé stante, verificare se esiste un cammino Euleriano (3 p.)

Esercizio 2. Si consideri la successione di numeri razionali:

1-1/2, 1-1/3, 1-1/4, 1-1/5,……… (il cui termine generico di posto n è 1-1/(n+1)) Dimostrare che per ogni naturale n, il prodotto dei primi n termini della successione è uguale a 1/(n+1) (4 p.)

Esercizio 3. Calcolare il numero delle matrici booleane con 3 righe e 4 colonne tali che nella prima colonna non vi sono due caselle adiacenti contenenti entrambe il valore 0 (6 p.)

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

in cui esattamente in 3 delle posizioni pari vi è una vocale (5 p.)

Esercizio 5. Sia dato l'insieme A={a,b,c,d,e,f,g,h}, e si consideri l'insieme B di tutte le combinazioni con ripetizione degli elementi di A di classe 10.

a) Calcolare quante sono le combinazioni in B in cui l’elemento a compare almeno una volta (3 p.)

b) Calcolare quante sono le combinazioni in B in cui il l’elemento f compare

esattamente 7 volte (3 p.)