Esercizi di Matematica Discreta
1) Calcolare, utilizzando il principio delle scelte multiple, quante sono parole di lunghezza 5 sull’alfabeto {a,b,c,d,e}, in cui la lettera a è ripetuta esattamente 3 volte (suggerimento: individuare le variabili da cui dipende ognuna di tali parole: la prima variabile è la scelta delle tre posizioni in cui inserire la lettera a …….).
2) Dimostrare che se a,b sono numeri naturali tali che mcd(a,b)=1, allora ogni numero naturale c è combinazione lineare di a,b con coefficienti interi relativi.
3) Dimostrare che, per ogni naturale n, la somma delle potenze di base 2 ed esponente che varia fra i numeri naturali consecutivi da 1 ad n:
21+22+…….+2n è uguale a 2n+1-2
4) Calcolare, utilizzando il principio di inclusione-esclusione in forma positiva, il numero delle parole di lunghezza 3 su un alfabeto di 8 lettere in cui almeno 2 lettere adiacenti nella parola sono uguali fra loro (suggerimento: ognuna di tali parole ha la prima e la seconda lettera uguali oppure la seconda e la terza uguali …….)
5) Calcolare, utilizzando il principio di inclusione-esclusione in forma negativa, il numero delle funzioni f: B={1,2,3,4} C={1,2,3,4,5,6,7,8,9,10,11,12} che non soddisfano nessuna delle seguenti proprietà:
a) le immagini degli elementi di B mediante f sono tutte <11 b) f è iniettiva
6) Si ha un dado a 6 facce (sulle quali vi sono i numeri naturali da 1 a 6, un numero per ogni faccia) e lo si lancia per 15 volte, registrando il numero uscito. Calcolare quante possibili successioni di numeri si ottengono se esattamente in 6 dei 15 lanci è uscito un numero pari (utilizzare il principio delle scelte multiple, notando che si devono scegliere i 6 lanci in cui è uscito un numero pari, per ognuno dei 6 lanci scegliere il numero uscito, e per i restanti 9 lanci scegliere il numero uscito) 7) Dato l’insieme A={1,2,3,4,5,6,7}, calcolare il numero dei sottoinsiemi di A che contengono i numeri 1,2 (suggerimento: ognuno di tali sottoinsiemi si ottiene fissando gli elementi 1,2 e aggiungendo………)
8) Si deve colorare una palizzata di 7 pali disposti in fila, utilizzando per ogni palo uno dei seguenti colori: giallo, verde, nero, rosso, bianco.
Poiché la quantità di rosso é scarsa, non si possono colorare in rosso più di 2 pali.
In quanti modi diversi si può colorare la palizzata ?
(suggerimento: applicare il principio delle scelte multiple, distinguendo i 3 casi: nessun palo è rosso; esattamente 1 palo è rosso; esattamente 2 pali sono rossi; poi sommare i risultati)
