COMBINATORIA

Claudia Malvenuto – Daniele A. Gewurz Scheda di esercizi n. 10

1. (a) Quanti sono gli anagrammi di “IL CONTE MAX” che non contengono le parole “IL”, “CONTE” o “MAX”? Non importano gli spazi: in realtà ci interessano le permutazioni della stringa

(I,L,C,O,N,T,E,M,A,X)

che non abbiano come sottostringa (I,L), (C,O,N,T,E) o (M,A,X).

(b) Come cambia questo numero se anziché “IL CONTE MAX” si considera “UN BEL MASCHIO” o “TRE PAVONI BLU”, chiedendo ogni volta che non compaiano le sottostringhe corrispondenti alle singole parole?

(c) E come cambia il corrispondente numero per “NEL MEZZO DEL CAMMIN”?

2. Se D_{n} è il numero delle permutazioni senza punti fissi su n elementi, si dimostri che si ha D_{n} = nD_{n−1} + (−1)^{n}.

3. Si scrivano le permutazioni di [n] come sequenze ordinate (a_{1}, a_{2}, …, a_{n}) (con {a_{1}, a_{2}, …, a_{n}} = {1, 2, …, n}). Sia Q_{n} il numero di permutazioni in cui non compaiono le sottostringhe 12, 23, … (n − 1)n, ovvero non compaiano consecutivamente i e i + 1 per i = 1, 2, …, n − 1. Cioè, per n = 4, vanno bene ad esempio 1324 o 4321 ma non 4312 o 2314.

(a) Si dia un’espressione per Q_{n}. (Sugg.: si pensi all’esercizio 1.)

(b) Si dimostri che Q_{n} = D_{n} +D_{n−1}, dove D_{n} è come nell’es. precedente.

4. In una pasticceria sono rimaste solo 8 paste alla crema, 7 crostatine con le fragole e 11 millefoglie. In quanti modi diversi si può comporre un vassoio da 12 paste?

5. Siano A, B e C insiemi con le seguenti proprietà:

• |A| = 100, |B| = 50 e |C| = 48;

• il numero di elementi che appartengono a esattamente uno dei tre insiemi è il doppio del numero di quelli che appartengono a esattamente due insiemi; • il numero di elementi che appartengono a esattamente uno dei tre

insiemi è il triplo del numero di quelli che appartengono a tutti e tre gli insiemi.

Quanti sono gli elementi che appartengono a tutti e tre gli insiemi?

6. Quanti triangoli equilateri hanno almeno due vertici tra i sette del reticolo esagonale della figura?

7. Due docenti pigri di un corso di Combinatoria cercano in rete con Google esercizi sul principio di Inclusione ed Esclusione da assegnare ai propri studenti. Si accorgono che, delle schede di esercizi che hanno trovato, in 22 compaiono esercizi in cui si parla di cibo, in 25 ci sono esercizi più astratti relativi ad insiemi e in 39 compaiono esercizi relativi al mondo scolastico o universitario (“Su n studenti… ”); in 9 di queste schede ci sono sia esercizi sul cibo che astratti, in 17 sia esercizi sul cibo che sull’università e in 20 sia esercizi astratti che sull’università; infine, 6 schede riportano esercizi di tutti e tre i tipi, mentre ci sono solo 4 schede con esercizi più originali, che non rientrano in nessuna di queste categorie.

Quante schede di esercizi hanno consultato i due docenti pigri?

8. Il signor Rossi colleziona ombrelli; ogni ombrello può essere da uomo o da donna, scuro o colorato, automatico o manuale. Dei suoi ombrelli, 4 sono scuri, da donna e automatici, 17 sono da donna, 14 sono automatici, 4 sono automatici da donna, 11 sono automatici scuri, 5 sono scuri e da donna, 3 sono ombrelli manuali colorati da uomo, 17 sono automatici o scuri. Quanti ombrelli possiede il signor Rossi?

9. (a) Quanti numeri con meno di cinque cifre non sono divisibili né per 4 né per 5 né per 6?

(b) Quanti sono i numeri primi fino a 100? (Si usi il P.I.E.)

10. Sia F (n, m) il numero di suriezioni di [n] in [m].

(a) Si osservi che F (n, m) è anche il numero delle partizioni ordinate dell’insieme [n] in m sottoinsiemi non vuoti.

(b) Usando il P.I.E., si trovi un’espressione per i numeri F (n, m).

(c) Si calcolino i numeri F (n, m) per n = 1, 2, 3, 4 ed m ≤ n.