717  Compito di Matematica Discreta I(21 settembre 2007)Soluzioni

Compito di Matematica Discreta I (21 settembre 2007)

Soluzioni

Esercizio 1. I vertici di cardinalità 1 sono adiacenti a quelli di cardinalità 2, quelli di cardinalità 2 sono adiacenti a quelli di cardinalità 3, etc…, quelli di cardinalità 6 sono adiacenti a quelli di cardinalità 7: comunque dati due vertici distinti x,y (qualunque sia la loro cardinalità) è sempre possibile costruire un cammino che li unisce, quindi il grafo è connesso ed ha 1 sola componente. Il numero cromatico è 2: basta attribuire un colore a tutti i vertici di cardinalità 1,3,5,7 e un secondo colore a tutti i vertici di cardinalità 2,4,6. I vertici di cardinalità 1 hanno grado: ₂ ⁸   ^{ 28}

 



 ; quelli di cardinalità 2: ₁ ⁸ ₃ ⁸   ^{ 64}

 



 

 

 



 ; quelli di

cardinalità 3: ₂ ^{8 8} _{4 } ^{ 98}



 



 

 

 



 ; quelli di cardinalità 4: ₃ ⁸ ₅ ⁸ _ ^{ 112}



 



 

 

 



 , e così via. Proseguendo i calcoli si verifica che tutti i vertici hanno grado pari, e nel grafo (connesso) esiste un cammino Euleriano ciclico.

Esercizio 2. Principio di induzione: per n=1 l’affermazione è vera in quanto il primo termine della successione è 1-1/2=1/2=1/(1+1). Supponendola vera per n=k, dimostriamola per n=k+1: il prodotto dei primi k+1 termini si ottiene moltiplicando il prodotto dei primi k (che per ipotesi è 1/(k+1)) per il termine di posto k+1 (che è 1-1/(k+2)) ottenendo che l’affermazione è vera anche per n=k+1 in quanto

[1/(k+1)][1-1/(k+2)]=[1/(k+1)][(k+1)/(k+2)]=1/(k+2).

Esercizio 3. Principio inclusione-esclusione in forma negativa: se A è l’insieme delle matrici booleane 3x4, e se X,Y sono rispettivamente i sottoinsiemi di A formati dalle matrici in cui la 1

e la 2

casella, la 2

e la 3

casella della prima colonna contengono entrambe il valore 0, si calcola

A-XY, dove A=2

e dove

XY=X+Y-XY=2

+2

-2

.

Esercizio 4. Principio delle scelte multiple: la scelta di 3 posizioni pari fra le 6 a disposizione si può effettuare in  

 



 3

6 modi; delle 2 vocali da inserire in queste 3 posizioni in 2

modi; delle consonanti da inserire nelle restanti 3 posizioni pari in 3

modi; delle lettere da inserire nelle restanti 6 posizioni in 5

modi. Basta moltiplicare questi 4 numeri.

Esercizio 5. a) Basta sottrarre dal numero delle combinazioni con ripetizione degli elementi di A di classe 10 (che è  

 



 7

17 ) quello delle combinazioni con ripetizione degli elementi

{b,c,d,e,f,g,h} di classe 10 (che è  

 



 6 16 )

b) E’ il numero delle combinazioni con ripetizione degli elementi {a,b,c,d,e,g,h} di classe 3 (che è  

 





6

9 )