+ 1)n(n1 o o

Compito di Matematica Discreta I (1 giugno 2007)

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

Esercizio 1. Si consideri il grafo semplice non orientato, in cui i vertici sono tutte le disposizioni semplici di classe 5 degli elementi {1,2,3,4,5,6,7} e in cui due vertici distinti x,y sono collegati da un arco se è pari la somma del primo elemento della disposizione x e del primo elemento della disposizione y.

Calcolare il numero di componenti connesse del grafo, e il numero di vertici di ogni componente. (3 p.)

Calcolare il numero cromatico del grafo (3 p.)

In ogni componente connessa (considerata come grafo a sé stante) dire se esiste un cammino Euleriano ciclico o non ciclico. (3 p.)

Esercizio 2. Si consideri l’insieme A delle parole di lunghezza 5 sull’alfabeto {a,b,c,d,e,f,g,h,i}.

Calcolare il numero di parole di A in cui almeno 2 delle lettere in posizione dispari sono vocali. (5 p.)

Esercizio 3.

Se A è l’insieme {2,4,6,8,10} e se B è l’insieme di tutti i possibili sottoinsiemi di A, calcolare il numero delle funzioni iniettive f : A → B tali f(6) ha cardinalità dispari.

(5 p.)

Esercizio 4.

Siano Z l’insieme degli interi relativi, A l’insieme delle matrici 2x2 ad elementi in Z, e si definiscano le funzioni:

f: Z → A g : A → Z

ponendo f(x)= ⎟⎟ , per ogni x∈Z, g( )=ab, per ogni ∈A.

⎠

⎜⎜ ⎞

⎝

⎛ + 1 0

1 2

x ⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛ d c

b

a ⎟⎟

⎠

⎜⎜ ⎞

⎝

⎛ d c

b a

Verificare se le funzioni composte g f, f o o g sono biunivoche. (4 p.)

Esercizio 5. Data la successione a

, dove a

=

1) n(n

1

+ per ogni naturale n, dimostrare che, per ogni naturale n, la somma dei primi n termini è uguale a

1 n

n

+ . (3 p.)

Esercizio 6. Calcolare il numero delle matrici booleane 3x5 (3 righe e 5 colonne) in

cui la somma degli elementi della prima riga è 2. (4 p.)