Esercizi di Matematica Discreta (22 gennaio 2010)
Esercizio 1. Al termine di un torneo sportivo, a cui partecipano 7 squadre italiane, 8 francesi e 5 inglesi, viene stilata una classifica con 20 posizioni distinte per le squadre. Calcolare il numero delle possibili classifiche in cui le squadre nelle prime 3 posizioni sono tutte italiane.
Esercizio 2. Si consideri il grafo semplice non orientato, in cui i vertici sono tutte le parole di lunghezza 5 sull’alfabeto {a,b,c,d,e,f} che contengono almeno una volta la lettera a, e in cui due vertici distinti x,y sono collegati da un arco se la parola x e la parola y contengono lo stesso numero di a. Quante sono le componenti connesse del grafo (3 p.) ? Qual è il numero cromatico del grafo (2 p.) ? In quali componenti connesse, considerate come grafo a sé stante, esiste in essa un cammino Euleriano (ciclico o non ciclico)
Esercizio 3. Calcolare il numero delle funzioni f: A={a,,b,c,d,e}B={1,2,3,4,5,6,7}
tali che le immagini di tutti gli elementi di A formino un insieme di cardinalità 3.
(si deve prima scegliere un sottoinsieme di B di cardinalità 3 e poi…….)
Esercizio 4. Dato l’insieme A = {a,b,c,d,e,f,g,h,i}, calcolare il numero dei sottoinsiemi di A che sono contenuti in almeno uno dei seguenti insiemi: {a,b,c,d,e}, {a,c,d,f}, {a,d,e,f}
