Matematica Discreta -...

Matematica Discreta

Giuseppe Lancia

Dipartimento di Matematica e InformaticaUniversita di Udine

A.A. 2003/2004

Indice

1 Preliminari matematici 1

1.1 Introduzione alla Matematica Discreta . . . . . . . . . . . . . 1

1.1.1 Permutazioni . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Logica e algebra booleana . . . . . . . . . . . . . . . . . . . . 2

1.3 Insiemi e funzioni . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Induzione matematica . . . . . . . . . . . . . . . . . . . . . . 7

1.5 Somme e loro manipolazioni . . . . . . . . . . . . . . . . . . . 9

1.5.1 Somme multiple . . . . . . . . . . . . . . . . . . . . . 12

1.6 Alcune somme importanti . . . . . . . . . . . . . . . . . . . . 14

1.6.1 La somma dei primi n naturali:∑n

i=1 i . . . . . . . . . 14

1.6.2 La somma dei primi n quadrati:∑n

i=1 i2 . . . . . . . . 16

1.6.3 La somma delle prime n + 1 potenze:∑n

i=0 ai . . . . . 18

1.6.4 Il metodo di perturbazione . . . . . . . . . . . . . . . 19

1.7 Sulla crescita delle funzioni . . . . . . . . . . . . . . . . . . . 20

2 Piccioni e buche 23

2.1 Il principio della piccionaia, forma semplice . . . . . . . . . . 23

2.2 Il principio della piccionaia, forma forte . . . . . . . . . . . . 25

3 Contiamo! 29

3.1 Principi fondamentali: somma e prodotto . . . . . . . . . . . 29

3.1.1 Il principio della somma . . . . . . . . . . . . . . . . . 29

3.1.2 Il principio del prodotto . . . . . . . . . . . . . . . . . 30

3.2 Combinazioni (sottoinsiemi) . . . . . . . . . . . . . . . . . . . 32

3.2.1 Triangolo di Pascal . . . . . . . . . . . . . . . . . . . . 34

3.3 Disposizioni (sottoinsiemi ordinati) . . . . . . . . . . . . . . . 36

3.4 Ripetizioni e multi-insiemi . . . . . . . . . . . . . . . . . . . . 37

3.4.1 Combinazioni con ripetizioni . . . . . . . . . . . . . . 38

3.5 I numeri di Fibonacci . . . . . . . . . . . . . . . . . . . . . . 40

i

ii INDICE

4 Il principio di inclusione-esclusione 43

4.1 Il principio base . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Spiazzamenti (derangements) . . . . . . . . . . . . . . . . . . 47

5 Probabilita combinatorie 51

5.1 Concetti elementari . . . . . . . . . . . . . . . . . . . . . . . . 51

5.1.1 Processi Bernoulliani . . . . . . . . . . . . . . . . . . . 53

5.2 Variabili casuali e valor medio . . . . . . . . . . . . . . . . . . 54

5.2.1 ♥ Ordinamento per inversione . . . . . . . . . . . . . 55

5.3 Generazione di strutture random . . . . . . . . . . . . . . . . 58

5.3.1 Insiemi . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.3.2 Permutazioni e disposizioni . . . . . . . . . . . . . . . 60

5.4 Enumerazione completa . . . . . . . . . . . . . . . . . . . . . 61

5.4.1 Generare tutti i sottoinsiemi . . . . . . . . . . . . . . 62

5.4.2 Generare tutte le permutazioni . . . . . . . . . . . . . 63

6 Teoria dei grafi 65

6.1 Grafi Non Orientati . . . . . . . . . . . . . . . . . . . . . . . 65

6.2 Cammini e cicli . . . . . . . . . . . . . . . . . . . . . . . . . . 69

6.3 Grafi bipartiti, hamiltoniani e euleriani . . . . . . . . . . . . . 70

6.4 Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.5 Grafi orientati . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

7 Ottimizzazione combinatoria 81

7.1 Il minimo albero di supporto . . . . . . . . . . . . . . . . . . 81

7.1.1 Strategie di Prim e Kruskal . . . . . . . . . . . . . . . 82

7.1.2 Casi speciali, facili e difficili . . . . . . . . . . . . . . . 83

7.2 Accoppiamenti . . . . . . . . . . . . . . . . . . . . . . . . . . 83

7.2.1 Il caso bipartito . . . . . . . . . . . . . . . . . . . . . . 84

7.2.2 Matching pesati . . . . . . . . . . . . . . . . . . . . . 84

7.3 Matrimoni stabili . . . . . . . . . . . . . . . . . . . . . . . . . 84

7.4 Minima copertura di vertici . . . . . . . . . . . . . . . . . . . 85

7.4.1 Il caso bipartito . . . . . . . . . . . . . . . . . . . . . . 85

7.4.2 Soluzioni approssimate . . . . . . . . . . . . . . . . . . 86

7.5 Clique e insieme indipendente . . . . . . . . . . . . . . . . . . 86

7.6 Colorazione di grafi . . . . . . . . . . . . . . . . . . . . . . . . 88

7.6.1 Le guardie del museo . . . . . . . . . . . . . . . . . . . 89

7.7 Il commesso viaggiatore . . . . . . . . . . . . . . . . . . . . . 89

7.7.1 TSP euclideo: algoritmi approssimati . . . . . . . . . 90

7.8 Set covering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

INDICE iii

8 Tracce di soluzioni 91

8.1 Capitolo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918.2 Capitolo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918.3 Capitolo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928.4 Capitolo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938.5 Capitolo 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948.6 Capitolo 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948.7 Capitolo 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

Capitolo 1

Preliminari matematici

1.1 Introduzione alla Matematica Discreta

Ad un party si presentano n persone, p uomini e q donne. Ci chiediamo cosedel tipo

• Quante strette di mano si possono dare?

• in quanti modi si possono sedere a tavola?

• quante coppie si possono formare per ballare?

• ecc.

Ragioniamo sul punto 1. Assumiamo ognuno stringa la mano a ognialtro. Ognuno stringe n− 1 mani per un totale di n(n− 1) strette. Pero, inquesto modo, ogni stretta di mano e contata due volte, per cui le strette dimano sono in tutto n(n − 1)/2.

Ora supponiamo si vogliano sedere a una tavola “rettangolare” (ossia,dove e chiaro il capotavola). Fissiamo il capotavola e l’ordine (es. orario). Ilcapotavola puo essere uno degli n. Alla sua sinistra, uno dei restanti n − 1.Alla sinistra di questo, uno dei restanti n − 2, ecc. In totale si hanno

n(n − 1)(n − 2) . . . 3 · 2 · 1

modi di sedersi. Questo numero e detto n!. Es 3! = 6, 4! = 24, 10! =3, 628, 800, 15! = 1, 307, 674, 368, 000 e 20! = 2, 432, 902, 008, 176, 640, 000.

Infine il punto 3. Assumiamo p = q. Ognuno dei p uomini puo ballarecon una delle p donne. Se il primo uomo balla con x, il secondo puo ballarecon una tra p − 1 donne (tutte tranne x). Sia y. Il terzo con p − 2 (tutte

1

2 CAPITOLO 1. PRELIMINARI MATEMATICI

tranne x e y). Alla fine ci sono p(p − 1) . . . 3 · 2 · 1 = p! modi di formarele coppie per un ballo. Se p > q ci sono p − q uomini che non balleranno.In questo caso e meglio ragionare sulle donne. La prima ha p scelte. Laseconda p − 1, la terza p − 2, ecc. In totale ci sono

p(p − 1)(p − 2)(p − q + 1) =p!

(p − q)!. (1.1)

Ad es. 15 uomini e 10 donne possono partecipare a un ballo in 15!/5! =10, 897, 286, 400 modi diversi.

1.1.1 Permutazioni

Avendo n oggetti distinti, in quanti modi li possiamo disporre in un elenco(in quanti modi li possiamo ordinare)? Ogni modo e detto una permutazione

degli n oggetti. Ci sono n! permutazioni. E importante che gli elementi sianodistinti (ad esempio, se tutti gli n elementi fossero indistinguibili, ci sarebbeuna sola permutazione e non n!.)

Esercizio 1.1. Elencare le 24 permutazioni di {A,B,C,D}.

Esempio. Quanti sono i modi di mescolare 40 carte di briscola: 40! Ecirca 1048. Questo e anche il numero di tutte le possibili partite distinte dibriscola (guardare all’ordine con cui le carte vengono girate sul tavolo). �

1.2 Logica e algebra booleana

L’algebra booleana riguarda principalmente lo studio di proposizioni (af-fermazioni, formule,...) che possono risultare vere o false. Questi due val-ori sono indicati come VERO e FALSO. Se P e un’affermazione e Q un’al-tra affermazione, possiamo creare nuove affermazioni tramite tre operazionifondamentali: or (∨), and (∧) e not (¬). Le regole sono

• P ∨Q e VERO se almeno una tra P e Q vale VERO, altrimenti P ∨Q =FALSO.

• P ∧ Q e VERO se entrambe P e Q valgono VERO, altrimenti P ∧ Q =FALSO.

• ¬P e VERO se P e FALSO e ¬P e FALSO se P e VERO.

1.2. LOGICA E ALGEBRA BOOLEANA 3

Si hanno le seguenti tabelle di verita:

P Q P ∨ Q P ∧ Q ¬P

FALSO FALSO FALSO FALSO VERO

FALSO VERO VERO FALSO VERO

VERO FALSO VERO FALSO FALSO

VERO VERO VERO VERO FALSO

Un’altra operazione logica e l’implicazione, indicata con →, che va’interpretata come

• P→Q e VERO se, tutte le volte in cui P e VERO, anche Q e VERO, equando P e FALSO Q puo essere indifferentemente VERO o FALSO. Incaso contrario (quando accade che P e VERO ma Q e FALSO), alloraP→Q = FALSO.

La tabella della verita e percio:

P Q P→Q

FALSO FALSO VERO

FALSO VERO VERO

VERO FALSO FALSO

VERO VERO VERO

Dall’analisi della tabella di verita dell’implicazione, si deduce che P→Qe la stessa cosa che ¬P ∨ Q. Inoltre, siccome ¬¬X = X sempre, abbiamoche ¬P ∨Q = ¬P ∨¬¬Q. Per cui invertendo il ruolo di P e di ¬Q si ha cheP→Q e la stessa cosa che ¬Q→¬P .

Si noti che se P = FALSO allora P→Q e sempre VERO! Proviamo ascegliere una frase Q qualsiasi e dimostrare che 1 = 0 implica Q. Sia alloraQ =“Le mucche sono verdi”; proviamo a dimostrarlo cosı. Ad ogni colorediamo un codice numerico, in modo che i vari possibili colori siano codificaticome 1, 2, . . . , k. Sia v il codice del colore verde. Presa una mucca qualsiasi,sia c il codice del suo colore. Allora c = c×1 = c×0 = 0 = v×0 = v×1 = vsicche il colore di quella mucca e proprio v: la mucca e verde!

Esercizio 1.2. Dimostrare che, se 1 = 0, allora tutti i numeri naturali sonoprimi.

Esercizio 1.3. Dimostrare che, se il mio cane ha 12 zampe, allora il papaha le ali.

Un esempio importante riguarda il sillogismo, che possiamo anche chia-mare deduzione:


se P e vero, ed e anche vero che P→Q, allora si puo concludere che ancheQ e vero.

Esercizio 1.4. Siano A= “chi ha piu’ di 21 anni puo guidare” e B=“Paoloha 18 anni”, C=“Gianni ha 24 anni”, D=“chi guida conosce il codice”. Qualitra queste deduzioni si possono fare?

• Gianni conosce il codice

• Gianni guida

• Paolo non puo guidare

• Gianni puo guidare

E importante saper calcolare la negazione di una proposizione. Se la propo-sizione e del tipo “per ogni x vale f(x)”, la sua negazione e: “esiste almenoun x per cui non vale f(x)”. Se la proposizione e del tipo “esiste un x percui vale g(x)”, la sua negazione e: “per ogni x non vale g(x)” ossia “pernessun x vale g(x)”.

Ad esempio, sapendo che Mario non guida, cosa possiamo dedurre? Quale la negazione di A? E di D? La negazione di D implica C?

Per dimostrazione di un’affermazione P (in particolare, ad es. di un teo-rema) si intende, fondamentalmente, l’utilizzo di una catena di deduzionivere D1→D2, D2→D3, ..., Dk−1→Dk e Dk→P , dove D1 e un fatto “noto-riamente” vero (un postulato, o il risultato di un’altra dimostrazione).

Bisogna fare attenzione a non confondere la conclusione con la premessa.Ad esempio, se sappiamo che

– Tutti gli udinesi amano il vino

e che

–Silvia ama il vino

non possiamo concludere che Silvia e di Udine. Se pero sappiamo che

– Paolo non ama il vino

possiamo concludere che Paolo non e di Udine. La conclusione si ottienetramite la “dimostrazione per assurdo”. Ossia, se supponessimo che Paolo

1.3. INSIEMI E FUNZIONI 5

fosse di Udine, arriveremmo a dover negare una cosa vera (ossia che nonama il vino, perche, in quanto udinese, deve amare il vino). In generaleuna dimostrazione per assurdo di una proposizione P , consiste nel trovareun’implicazione vera ¬P→A, e nel fare vedere che A e FALSO. Ma allora ¬Pdeve essere FALSO, e, quindi, P deve essere VERO.

Dimostrazioni per assurdo Come detto, le dimostrazioni per assurdoconsiste nel dimostrare implicazioni del tipo P→Q in cui Q e falso. In talmodo, ne consegue che anche P deve essere falso. In particolare, supponiamodi dimostrare l’implicazione P→¬P . Allora P deve essere falso. Allo stessomodo, se si dimostra che ¬P→P , P deve essere vero.

Come esempio, consideriamo l’enunciato P=“esistono infiniti numeriprimi” e dimostriamo per assurdo che ¬P→P , da cui P deve essere vero.Ossia dimostriamo che se i numeri primi fossero in numero finito, allora nonpotrebbero essere in numero finito. La dimostrazione e di Euclide. Supponi-amo pertanto che tutti i numeri primi siano p1, . . . , pn. Creiamo un nuovonumero a = p1 · p2 · · · pn + 1. Sia p un divisore primo di a. p /∈ {p1, . . . , pn},perche a non e divisibile per alcun pi (a diviso per pi da’ quoziente Πj 6=ipj

e resto 1). Quindi p e un nuovo numero primo e p1, . . . , pn non erano tutti inumeri primi.

Esercizio 1.5. Definiamo “numero magico” un numero che e pari allasomma delle sue cifre. Dimostrare per assurdo che non esistono numerimagici di 3 o piu cifre. Dimostrare che non esistono neppure di 2 cifre.

Esercizio 1.6. Dimostrare per assurdo che non puo esistere un numerointero che sia al contempo pari e dispari

1.3 Insiemi e funzioni

L’insieme e un concetto primitivo, che non puo essere definito se non conun sinonimo (collezione, gruppo...). Si possono elencare gli elementi (se l’in-sieme e finito e ha bassa cardinalita) o dare una proprieta’ che ne caratterizzagli elementi.

Tra gli insiemi abbiamo le principali operazioni di unione

A ∪ B = {x |x ∈ A ∨ x ∈ B} (1.2)

intersezione

A ∩ B = {x |x ∈ A ∧ x ∈ B} (1.3)


differenza

A − B = {x |x ∈ A ∧ x /∈ B} (1.4)

e differenza simmetrica

A∆B = (A − B) ∪ (B − A). (1.5)

Un sottoinsieme B di un insieme S, e tale che x ∈ B→x ∈ S. Il com-

plementare di B (indicato con B, quando il sovrainsieme S e implicito) el’insieme B = S − B.

Le leggi di De Morgan mettono in relazione le operazioni di unione eintersezione con il complementare:

A ∪ B = A ∩ B (1.6)

A ∩ B = A ∪ B (1.7)

Per la cardinalita si hanno le seguenti relazioni (lo si dimostri per eser-cizio):

0 ≤ |A ∩ B| ≤ max{|A|, |B|} (1.8)

min{|A|, |B|} ≤ |A ∪ B| ≤ |A| + |B| (1.9)

|A ∪ B| = |A| + |B| − |A ∩ B| (1.10)

Esercizio 1.7. Sapendo che |A| = 4 e |B| = 8, quali tra i seguenti valoripossono essere |A∪B| : 3, 4, 7, 10, 13? Quali tra i precedenti valori possonoessere |A ∩ B|?

Le funzioni associano agli elementi di un insieme (dominio) elementi diun altro insieme (codominio). Una funzione puo essere iniettiva (x 6= yimplica f(x) 6= f(y)), suriettiva (per ogni y del codominio esiste un x deldominio con y = f(x)) o biettiva (sia iniettiva che suriettiva). Due insiemihanno lo stesso numero di elementi se (e solo se) tra i due insiemi c’e unafunzione biettiva. La composizione di due funzioni f e g e una funzione hdefinita da h(x) = f(g(x)).

Esercizio 1.8. Sia f una funzione di A in B e sia C ⊆ B tale che per ognic ∈ C esiste almeno un x ∈ A con c = f(x). Che relazione c’e fra |C| e |A|?

1.4. INDUZIONE MATEMATICA 7

1.4 Induzione matematica

Il principio di induzione, consiste nel dimostrare che una certa proprieta Pvale per tutti i numeri naturali dimostrando che

1. P e vera per il numero 0

2. se P e vera per il numero k − 1, allora e vera anche per il numero k

Per evidenziare la dipendenza di P dal numero, si scrive P (n). Per cui,si puo dimostrare che P (n) = VERO per ogni n dimostrando che

1. P (0) = VERO

2. P (k − 1)→P (k) per ogni k > 0

Il caso P (0) si dice caso base dell’induzione, mentre il passaggio da k− 1a k e detto passo induttivo. In alcuni casi si puo sostituire un certo numeroK a 0, e allora si dimostra che la proprieta P vale per tutti gli n ≥ K.

Esempio. Come esempio, dimostriamo che la somma dei primi n numeridispari vale n2.

Indichiamo tale somma con S(n). Si noti che l’n-esimo numero dispari(per n = 1, 2, . . .) e 2n − 1. Caso base:

S(1) = 1 = 12

Passo induttivo. Sia S(k) = k2. Allora

S(k) = S(k − 1) + 2k − 1 = k2 − 2k + 1 + 2k − 1 = k2.

�

Esempio. Dimostriamo che la somma dei primi n numeri naturali positivie n(n+1)

2 .Indichiamo tale somma con S(n). Caso base:

S(1) = 1 =1 · 22

Passo induttivo. Sia S(k − 1) = (k−1)k2 . Allora

S(k) = S(k − 1) + k =(k − 1)k

2+ 2

k

2=


k

2(k − 1 + 2) =

k(k + 1)

2�

Esempio. Dimostriamo che∑n

i=0 2i = 2n+1 − 1. Indichiamo tale sommacon S(n). Caso base:

S(0) = 1 = 21 − 1.

Passo induttivo. Sia S(k − 1) = 2k − 1. Allora

S(k) = S(k − 1) + 2k = 2k − 1 + 2k = 2k+1 − 1.

�

Sebbene il passo induttivo e di solito presentato come il modo di di-mostrare P (k) a partire da P (k − 1), sarebbe perfettamente analogo (eporterebbe ancora a concludere che P (n) e vera per ogni n) un passo indut-tivo che dimostrasse che P (k) consegue da P (q) per qualche q < k (ossianon necessariamente q = k−1). Infatti, in tale modo si potrebbe dimostrareP (1) da P (0), dopodiche seguirebbe P (2) da P (0) o P (1), e a quel puntoseguirebbe P (3) da P (0) o P (1) o P (2), e cosı via...

I seguenti esempi mostrano come l’induzione possa essere usata in manieraerrata e portare a “dimostrare” proposizioni false. Si trovino gli errori negliesempi seguenti.

Esempio. Si consideri la dimostrazione per induzione della proposizioneP (n): n linee, a 2 a 2 non parallele, si incontrano tutte in uno stesso punto.

P (2) e chiramente vera. Supponiamo ora di avere k linee e che P (k − 1)sia vero. Siano a, b, c, d, . . . le linee. Tolta la linea c, le rimanenti si incon-trano (per induzione) in un punto, diciamo X. In particolare a e b passanoper X. Ora, rimettiamo c e togliamo d. Sempre per indizione, le k − 1 linee(comprese a, b e c) si incontrano in un punto, che deve essere X (questosiccome sappiamo gia che a e b si incontrano in X). Si conclude che c passaper X, e quindi tutte le linee passano per X. �

Esempio. Si consideri la dimostrazione per induzione della proposizioneP (n): per ogni n ≥ 0, si ha n = 2n.

P (0) e vero siccome 0 = 2 ·0. Dato k > 0, si supponga vero P (q) per 0 ≤q < k. Per un 0 < q < k, si spezzi k in (k − q) + q. Per ipotesi di induzione,k−q = 2(k−q) e q = 2q. Ne consegue k = (k−q)+q = 2(k−q)+2q = 2k. �

1.5. SOMME E LORO MANIPOLAZIONI 9

1.5 Somme e loro manipolazioni

La somma(toria) e un’espressione del tipo

n∑

k=1

ak

dove k e detto l’indice e ak il termine generico. Il valore di tale sommae

a1 + a2 + a3 + · · · + an−1 + an.

Questo secondo tipo di scrittura lascia un po’ troppa liberta, nello sceglierequanti e quali “· · ·” mettere. Ad esempio, la somma sopra si poteva proba-bilmente scrivere a1 +a2 + · · ·+an. Se pero ai = 2i−1 si avrebbe la scrittura1 + 2 + · · · + 2n−1 che puo essere confusa con

∑n−1i=1 i. Sarebbe quindi sta-

to meglio scriverla come 20 + 21 + · · · + 2n−1. Con l’espressione∑

questoproblema non si pone.

Gli indici di una somma sono numeri interi. La variabilita di un indicenon deve necessariamente essere tra un limite inferiore e uno superiore, mal’indice puo essere preso su un qualsiasi insieme K di interi. In questo casola scrittura migliore e quella che spiega la variabilita dell’indice sotto alsimbolo di somma

∑

:∑

k∈K

ak

Alcuni esempi:∑

0≤k≤n

ak,∑

k primo,k<20

ak,∑

1≤k≤100, k dispari

ak

Ad esempio, la somma dei quadrati dei numeri dispari tra 1 e 100 epreferibile scritta come

∑

1 ≤ k ≤ 100k dispari

k2

che come50∑

k=1

(2k − 1)2

per quanto sia la stessa somma. Allo stesso modo “risparmiare” termini nonserve e puo rendere piu difficile capire una somma. Ad esempio scrivere

n−1∑

k=2

k(k − 1)(n − k)


e peggio che scriveren∑

k=0

k(k − 1)(n − k)

per quanto il valore sia lo stesso. Anche la somma sull’insieme vuoto edefinita, e vale sempre 0:

∑

k∈∅

ak = 0.

Le seguenti regole permettono di manipolare le somme, per crearne dinuove, per aggregazione o disgregazione:

1. Legge distributiva: Da una somma si possono “portare fuori” lecostanti, ossia le espressioni che non dipendono dall’indice:

∑

k∈K

cak = c∑

k∈K

ak

2. Legge associativa: permette di spezzare una somma in due o diriunire due somme in una:

∑

k∈K

(ak + bk) =∑

k∈K

ak +∑

k∈K

bk

3. Legge commutativa: L’ordine con cui si sommano i termini puoessere cambiato e la somma resta la stessa. Sia p una permutazionedefinita su tutti i numeri interi (ossia una funzione p di Z in Z taleche p e sia iniettiva che suriettiva). Allora

∑

k∈K

ak =∑

p(k)∈K

ap(k)

Consideriamo il caso semplice K = {1, 2, 3, 4} presa una permutazionenel senso classico di un ordinamento dei 4 numeri (ad esempio 3, 1,2, 4) questa puo anche essere vista come una funzione permutazione,ossia, p(1) = 3, p(2) = 1, p(3) = 2, e p(4) = 4. Si puo poi estendere pagli altri interi (che tanto non entrano nella somma) definendo p(i) = iper i < 1 e i > 4. In pratica stiamo dicendo che a1 + a2 + a3 + a4 =a3 + a1 + a2 + a4.

Consideriamo un caso piu interessante (il cambio di indice): per ognicostante c e numero intero b 6= 0, la funzione

p(i) = bi + c


e una permutazione degli interi (per esercizio, lo si dimostri). Per cui∑

k∈K

ak = c∑

(bk+c)∈K

abk+c

Ad esempio, calcoliamo

S =∑

0≤k≤n

(a + bk) (1.11)

sfruttando solo le 3 leggi qui sopra. Applichiamo la legge commutativa erimpiazziamo k con n − k, ottenendo

S =∑

0≤n−k≤n

(a + b(n − k)) =∑

0≤k≤n

(a + bn − bk) (1.12)

Dalla legge associativa sommiamo (1.11) e (1.12) e otteniamo

2S =∑

0≤k≤n

((a + bk) + (a + bn − bk)) =∑

0≤k≤n

(2a + bn)

Per la legge distributiva (si noti che (2a + bn) non dipende da k) si ha

2S = (2a + bn)∑

0≤k≤n

1 = (2a + bn)(n + 1)

da cui, dividendo per 2

S = (a +1

2bn)(n + 1).

Una formula generale che permette di fondere e spezzare le somme e laseguente:

∑

k∈K

ak +∑

k∈K′

ak =∑

k∈K∩K′

ak +∑

k∈K∪K′

ak (1.13)

Esempio.

• fondere le somme: sia 1 ≤ m ≤ n. Alloram∑

k=1

ak +n∑

k=m

ak = am +n∑

k=1

ak

• spezzare le somme: sia 1 ≤ m ≤ n. Alloran∑

k=1

ak =m∑

k=1

ak +n∑

k=m+1

ak

�


1.5.1 Somme multiple

Un vettore di dimensione n e una sequenza di n numeri, detti le componenti

del vettore. Ad esempio, i seguenti a, b e c sono vettori di dimensione 4:

a = (3, 2, 5,−1) b = (6, π,−3, 0) c = (0, 0, 0, 0)

Se a e un vettore, le sue componenti si indicano tramite indici, come in

a = (a1, a2, . . . , an)

Supponiamo, dati due vettori a e b di voler calcolare la somma dei prodot-ti fra ogni componente di a e di b. Ad esempio, se n = 3, tale sommae

a2b3 + a1b2 + a2b1 + a3b1 + a2b2 + a1b3 + a1b2 + a3b2 + a3b3 (1.14)

Questa somma puo essere scritta come una somma doppia, ossia su dueindici:

∑

1≤i,j≤3

aibj (1.15)

Riscriviamo la somma (1.14) in un modo piu organizzato, mettendo tuttigli addendi in una tabella:

a1b1 + a1b2 + a1b3 +a2b1 + a2b2 + a2b3 +a3b1 + a3b2 + a3b3

(1.16)

Si dice anche che gli addendi sono stati messi in una matrice 3 per 3,ossia con 3 righe e 3 colonne (in generale, una matrice m×n ha mn numeridisposti su m righe e n colonne). La somma puo essere calcolata facendole somme di ogni riga e poi sommando tali valori. Si noti che la riga i hatermini in cui ai e costante e varia solo bj . Scriviamo

∑

1≤i≤3

∑

1≤j≤3

aibj

Si sarebbe pero potuto anche calcolare tale somma “per colonne”, ossiasommando il valore su ogni colonna (in cui bj e costante) e facendo infine lasomma dei totali. Questa somma si sarebbe dovuta scrivere

∑

1≤j≤3

∑

1≤i≤3

aibj


C’e stato quindi uno scambio di indici. Vediamo ora formalmente perchequesto e giustificato:

∑

1≤i≤3

∑

1≤j≤3

aibj =∑

1≤i≤3

(ai

∑

1≤j≤3

bj) = (∑

1≤j≤3

bj) (∑

1≤i≤3

ai) (1.17)

dove il primo passaggio e giustificato dal fatto che nell’espressione∑3

j=1 aibj

il valore ai e una costante (non dipende da j) e puo quindi (legge distributi-va) essere portato fuori dalla somma. Allo stesso modo, il secondo passaggiosegue dal fatto che l’intera somma

∑3j=1 bj e una costante nell’espressione

∑3i=1 (ai

∑3j=1 bj).

In modo perfettamente analogo, si puo dimostrare che anche∑

1≤j≤3

∑

1≤i≤3

aibj = (∑

1≤i≤3

ai) (∑

1≤j≤3

bj) (1.18)

In particolare, le formule (1.17) e (1.18) ci danno anche un modo imme-diato per calcolare il valore finale. Basta sommare tutte le componenti di ae moltiplicare il valore ottenuto con la somma di tutte le componenti di b.

La regola di scambio degli indici in una somma puo essere riassuntacosı: quando in una somma doppia il primo indice i varia su un insiemeI e il secondo indice j varia su un insieme J , in maniera indipendente dalvalore di i (ossia, J e sempre lo stesso, per ogni valore di i), allora gli indicipossono essere scambiati:

∑

i∈I

∑

j∈J

sij =∑

j∈J

∑

i∈J

sij (1.19)

dove con sij abbiamo indicato il generico termine della somma (chedipende da i e j. Nell’esempio precedente, era sij = aibj)

Se pero la variabilita del secondo indice dipende dal valore del primoindice, allora bisogna fare attenzione. Si consideri il seguente esempio:

n∑

i=0

n∑

j=i

sij (1.20)

Questa somma non si puo riscrivere come

n∑

j=i

n∑

i=0

sij (1.21)

in quanto, leggendo da sinistra a destra, la variabilita del primo indice (j)non e definita chiaramente. Infatti si suppone che j parta da i, ma i e un


simbolo “indefinito” (o, come si dice, non quantificato) la prima volta che losi incontra.

La situazione di indici dipendenti si puo descrivere in questo modo: ilprimo indice, i, varia su un insieme I, mentre il secondo j, varia su un insiemeJ(i) che dipende, di volta in volta, dal valore corrente di i. In questo caso,per poter scambiare gli indici, dobbiamo vedere, per ogni valore del secondoindice, j, quali sono i valori di i per i quali j apparteneva a J(i). Sia Jl’unione di tutti i J(i) per i ∈ I (ossia J e l’insieme di tutti i possibili valoridel secondo indice). Definiamo, per ogni j ∈ J ,

I(j) := {i ∈ I | j ∈ J(i)}

Allora, possiamo effettuare lo scambio degli indici in questo modo:

∑

i∈I

∑

j∈J(i)

sij =∑

j∈J

∑

i∈I(j)

sij (1.22)

Nel caso dell’esempio (1.20) si ha J = {0, . . . , n} e I(j) = {0, 1, . . . , j}per ogni j. Pertanto, (1.20) puo essere riscritta come

n∑

j=0

j∑

i=0

sij (1.23)

Esercizio 1.9. Siano a = (3, 23 , 5, 1

3 ,−2,−6, 3, 9,−1) e b = (− 13 , 1

4 , 2, 3,−1, 12 , 1

2).Si calcoli

9∑

i=1

7∑

j=1

ai

bj.

1.6 Alcune somme importanti

1.6.1 La somma dei primi n naturali:∑n

i=1 i

Approccio “geniale”

Il primo approccio e quello utilizzato da Gauss a 6 anni! Per sommare iprimi 100 numeri, ha ragionato cosı. Il primo (1) piu l’ultimo (100) danno101. Il secondo (2) piu il penultimo (99) danno ancora 101. E cosı via,3 + 98 = 101,..., 50 + 51 = 101. In totale si hanno 50 coppie di valore 101 equindi

∑100i=1 i = 5050.

1.6. ALCUNE SOMME IMPORTANTI 15

Il ragionamento si puo generalizzare cosı. Supponendo n pari, si hannon/2 coppie di valore n + 1 e quindi

n∑

i=1

i =n(n + 1)

2(1.24)

Se n e dispari, si puo aggiungere 0 alla somma, come primo termine. Inquesto modo si ottengono n + 1 termini e (n + 1)/2 coppie. Ogni coppiasomma n (0 + n, 1 + (n − 1),...), per cui la somma e ancora n(n + 1)/2.

Approccio “geometrico”

*

* *

* * *

* * * *

* * * * *

Sia B la base e H l’altezza del disegno qui sopra. Vogliamo calcolarel’area coperta dagli “*”. Si ha

B = n e H = n + 1.

L’area totale e H · B = n(n + 1). L’area scura (quella che cerchiamo) e∑n

i=1 i ed e anche uguale all’area chiara. Siccome area chiara + area scura= area totale, si ha

2 ·n∑

i=1

i = n(n + 1) (1.25)

per cuin∑

i=1

i =n(n + 1)

2. (1.26)

Approccio “analitico”

Si intuisce che la somma cresce “come” n2 (ci sono n addendi dal valore finoa n). Per cui si ipotizza

C(n) =n∑

i=1

i = an2 + bn + c


Si prova per sostituzione.

C(0) = 0 per cui c = 0

C(1) = a + b = 1

C(2) = 4a + 2b = 3

Si ricava un sistema di 2 equazioni in 2 incognite:{

a + b = 14a + 2b = 3

Risolviamo il sistema. Rimpiazziamo la II con (4I − II), ottenendo{

a + b = 12b = 1

Da cui, b = 1/2 e a = 1/2. Quindi

C(n) =1

2n2 +

1

2n

che, raggruppando n al numeratore, diventa

C(n) =n(n + 1)

2

1.6.2 La somma dei primi n quadrati:∑n

i=1 i2

Calcoliamo∑n

i=1 i2. Usiamo 2 approcci diversi.

Approccio “geometrico”

* * * * *

* * * * * * * * *

* * * * * * * * * * * *

* * * * * * * * * * * * * *

* * * * * * * * * * * * * * *

Sia B la base e H l’altezza del disegno qui sopra. Vogliamo calcolarel’area coperta dagli “*”. Si ha

B =n∑

i=1

i =n(n + 1)

2e H = n + 1.


L’area totale e H · B = n(n+1)2

2 . L’area scura (quella che cerchiamo) e∑n

i=1 i2. L’area chiara e∑n

i=1

∑ij=1 j. Si ha:

n∑

i=1

i∑

j=1

j =n∑

i=1

i(i + 1)

2=

1

2

n∑

i=1

i2 +1

2

n∑

i=1

i =1

2

n∑

i=1

i2 +1

2

n(n + 1)

2(1.27)

Siccome area chiara + area scura = area totale, si ha

1

2

n∑

i=1

i2 +n(n + 1)

4+

n∑

i=1

i2 =n(n + 1)2

2(1.28)

3

2

n∑

i=1

i2 =n(n + 1)2

2− n(n + 1)

4=

n(n + 1)

4(2(n + 1) − 1) (1.29)

da cuin∑

i=1

i2 =2

3

n(n + 1)(2n + 1)

4=

n(n + 1)(2n + 1)

6. (1.30)

Approccio “analitico”

Si intuisce che la somma cresce “come” n3 (ci sono n addendi dal valore finoa n2). Per cui si ipotizza

C(n) =n∑

i=1

i2 = an3 + bn2 + cn + d

Si prova per sostituzione.

C(0) = 0 per cui d = 0

C(1) = a + b + c = 1

C(2) = 8a + 4b + 2c = 1 + 4 = 5

C(3) = 27a + 9b + 3c = 1 + 4 + 9 = 14

Si ricava un sistema di 3 equazioni in 3 incognite:

a + b + c = 18a + 4b + 2c = 527a + 9b + 3c = 14

Risolviamo il sistema. Rimpiazziamo la II con (8I − II) e la III con(27I − III). Otteniamo


a + b + c = 14b + 6c = 318b + 24c = 13

Continuando, si rimpiazza la III con (18II − 4III) ottenendo

a + b + c = 14b + 6c = 3

12c = 2

A questo punto si risolve e si ha c = 1/6, b = 1/2 e a = 1/3. Ossia

C(n) =1

3n3 +

1

2n2 +

1

6n

che, fissando il denominatore a 6 e raggruppando n al numeratore, diventa

C(n) =n(n + 1)(2n + 1)

6

Esercizio 1.10. Quanti quadrati contiene una griglia di lato n (ossia conn + 1 punti su ogni lato)?

1.6.3 La somma delle prime n + 1 potenze:∑n

i=0 ai

Calcoliamo S(n) :=∑n

i=0 ai, dove a > 1. Abbiamo (induttivamente, pern ≥ 0)

S(n + 1) = an+1 + S(n). (1.31)

Inoltre, moltiplicando S(n) per a si ottiene

a(1 + a + a2 + . . . + an) = a + a2 + . . . + an+1 =n+1∑

i=0

ai − 1

ossiaaS(n) = S(n + 1) − 1 (1.32)

Da (1.31) e (1.35) si ricava un sistema che possiamo risolvere rispet-to a S(n). Sostituendo il valore di S(n + 1) dato dall’equazione (1.31)nell’equazione (1.35), si ottiene

aS(n) = an+1 + S(n) − 1 (1.33)


da cui

S(n) =an+1 − 1

a − 1. (1.34)

Esempio. Calcoliamo∑40

i=12 7i. Abbiamo∑40

i=12 7i =∑40

i=0 7i −∑11i=0 7i =

(741 − 1)/6 − (712 − 1)/6 = 712(729 − 1)/6. �

♥ Esercizio 1.11. Quante sono le possibili sequenze di DNA lunghe alpiu 10 nucleotidi?

Esercizio 1.12. Quanto vale∑n

i=0 a3i?

1.6.4 Il metodo di perturbazione

Dagli esempi precedenti (specialmente l’ultimo) possiamo evincere un meto-do generale per (tentare di) risolvere le somme del tipo Sn =

∑nk=0 ak.

Il metodo si chiama “perturbazione” e consiste nel cercare di creare un’e-quazione che abbia Sn sia a destra che a sinistra, ma non con lo stessocoefficiente, in modo che non si cancellino a vicenda. Questa equazioneviene creata passando a Sn+1 e mettendo di volta in volta in evidenza an+1

e a0.

Aggiungendo an+1 a Sn, si ha Sn+1, ossia

Sn + an+1 =∑

0≤k≤n+1

ak

Mettiamo ora in evidenza a0 a destra. Inoltre, siccome (legge commu-tativa)

∑

1≤k≤n+1 ak e lo stesso che∑

0≤k≤n ak+1, otteniamo la relazionefondamentale

Sn + an+1 = a0 +∑

0≤k≤n

ak+1

Il trucco ora sta nel cercare di sviluppare∑

0≤k≤n ak+1 in modo ricavarne(se possibile) Sn. In tal modo avremmo Sn sia a sinistra che a destra, epotremo risolvere rispetto a Sn.

Come esempio di questa tecnica calcoliamo il valore di

Sn =∑

0≤k≤n

k2k


Abbiamo

Sn + (n + 1)2n+1 = 0 +∑

0≤k≤n

(k + 1)2k+1 (1.35)

Studiamo∑

0≤k≤n(k+1)2k+1 cercando di mettere in evidenza Sn. Spezzi-amo la somma in due con la legge associativa.

∑

0≤k≤n

(k + 1)2k+1 =∑

0≤k≤n

k2k+1 +∑

0≤k≤n

2k+1 = 2∑

0≤k≤n

k2k + 2∑

0≤k≤n

2k

e, ricordando che∑

0≤k≤n 2k = 2n+1 − 1, si ha

∑

0≤k≤n(k + 1)2k+1 =∑

0≤k≤n k2k+1 +∑

0≤k≤n 2k+1

= 2∑

0≤k≤n k2k + 2∑

0≤k≤n 2k

= 2Sn + 2n+2 − 2

Sostituendo questo valore in (1.35) si ottiene

Sn + (n + 1)2n+1 = 2Sn + 2n+2 − 2

da cui

Sn = (n + 1)2n+1 − 2n+2 + 2 = 2n+1(n − 1) + 2.

Esercizio 1.13. Si usi il metodo di perturbazione per (ri)calcolare∑n

i=0 ci,con c > 1.

1.7 Sulla crescita delle funzioni

Consideriamo funzioni come n, n2, 2n, n!, log n. Ci chiediamo come varianoal variare di n.

Partiamo dalla funzione esponenziale, del tipo an. Ad esempio conside-riamo il caso a = 2. Prendiamo una scacchiera e mettiamo una moneta da1 euro sulla prima casella, 2 sulla seconda, 4 sulla terza e cosı via. Quantosara alta la torre di monete sull’ultima casella?

Si tratta di una pila di 263 monete. 263 e il prodotto

2 · 2 · 2 · · · 2 · 2

1.7. SULLA CRESCITA DELLE FUNZIONI 21

con 63 fattori. Per farne una stima grossolana, rimpiazziamo ogni 10 fattori(210) con 1000, ossia 103 (in realta 210 = 1024, per cui stiamo sottostimandoil valore). Ne consegue che 263 > (103)6 · 23, ossia

263 > 8 · 1018.

Ora, assumendo che una pila di 8 euro abbia spessore di 1 cm (in realta’ne bastano di meno per fare 1 cm, per cui stiamo ancora sottostimando),abbiamo che la pila e alta almeno 1018 centimetri. Siccome 105cm = 1km,la pila e alta almeno 1013 km. La distanza della Terra dalla Luna e di circa4 · 105 km. Per cui questa pila va ben oltre la Luna! Quanto oltre? Ladistanza della Terra dal Sole e di circa 2 · 107 km. Per cui la nostra pilasarebbe (almeno) 500’000 volte piu lunga che la distanza da qui al Sole!

Da questo esempio si e visto che, per avere approssimazioni inferiori alvalore di 2n si possono rimpiazzare i gruppi di dieci “2” con gruppi di tre“10”. Oppure, siccome 24 = 16 < 10, possiamo rimpiazzare ogni quattro“2” con un “10”. Per avere approssimazioni superiori, siccome 23 = 8 < 10,possiamo rimpiazzare ogni tre “2” con un “10”. Per cui

8 · 1018 < 263 < 1021 (1.36)

Per ottenere esattamente l’esponente y tale che 10y = 2x bisognerebbedividere x per circa 3.32 (o meglio per il log2 10).

Il fattoriale cresce almeno come 2n e al massimo come nn. Questi sonolimiti molto lontani l’uno dall’altro. Si puo migliorare un po’ il limite infe-riore notando che tutti i fattori da 10 in su in n! valgono almeno 10, per cuin! > 10n−9. La miglior stima per la crescita di n! e la seguente, che diamosenza dimostrazione. Per n grande, n! vale circa

(n

e)n√

2πn (1.37)

dove e = 2.718.. e la costante di Nepero. In prima approssimazione, possi-amo dire che n! cresce (almeno) come (n/3)n.

Sia dato un gruppo di n persone (sul come si sono trovati i valori cheseguono verra data spiegazione piu avanti. Per ora li si prenda per buoni).Se fanno un torneo di tennis, definiamo A(n) il numero di partite che ilvincitore dovra avere giocato alla fine del torneo. A(n) e (almeno) log2 n.Esattamente, A(n) e il minimo intero non inferiore a log2 n (ossia, l’arroton-damento, per eccesso, di log2 n ad intero, indicato con dlog2 ne). Vengonoestratti 2 premi fra le persone. Avere vinto il primo premio non impediscedi partecipare alla seconda estrazione. Sia B(n) il numero di possibili coppie


(vincitori del primo premio, vinciore del secondo premio). B(n) e n2. Suc-cessivamente, viene tirata una moneta per n volte, e ogni persona per cuiesce “testa” riceve un premio. Sia C(n) il numero di modi in cui la suddettapremiazione puo avere luogo. Si ha C(n) = 2n. Infine, le n persone esconouna alla volta da una stanza. Sia D(n) il numero di modi in cui cio puoavvenire. C(n) = n!. Per esercizio, si completi (anche con valori approssi-mati) la seguente tabella

n A(n) B(n) C(n) D(n)

1 0 1 2 12 1 4 4 23 2 9 8 64 2 16 16 248 3 64 256 40320

10 4 100 1024 36288001620305064

100

Capitolo 2

Piccioni e buche

In questo capitolo studiamo un principio elementare ma molto importante, ilprincipio della piccionaia. In pratica, il principio dice che, se molti piccionivolano in una piccionaia con poche buche, in almeno una buca finiranno dueo piu piccioni.

2.1 Il principio della piccionaia, forma semplice

La forma piu semplice del teorema e la seguente:

Teorema 1: Se n+1 oggetti vengono posti in n contenitori, allora almenoun contenitore conterra due o piu oggetti.

Dim: Per assurdo, se ogni contenitore contenesse al piu un oggetto, siavrebbe che il numero totale di oggetti e al piu n. Ma noi abbiamo suppostoche tale numero e n + 1. ♣

Esercizio 2.1. Si dimostri il principio della piccionaia per induzione.

Si noti che ne il teorema ne la sua dimostrazione danno indicazioni suquale contenitore abbia piu di un oggetto. L’unica cosa che possiamo af-fermare con certezza e l’esistenza di un tale contenitore. Si noti inoltre cheil principio vale solo se si hanno almeno n + 1 oggetti. Infatti, si possonomettere n oggetti in n contenitori senza che due oggetti vadano nello stessocontenitore.

Esempio. In un gruppo di 367 persone ce ne sono almeno due con lo stessocompleanno. �

23

24 CAPITOLO 2. PICCIONI E BUCHE

Esempio. Una persona possiede n paia di scarpe, ogni paio di un colorediverso. Quante scarpe deve prendere come minimo, al buio, per esseresicuro di aver selezionato almeno un paio di scarpe dello stesso colore?

Prendendo n scarpe, non puo avere la certezza di un paio completo(potrebbero essere tutte di colore diverso). Con n + 1 scarpe, ce ne devonoessere due dello stesso colore.

Si supponga ora che tutte le paia di scarpe siano identiche (stesso coloree forma). Quante scarpe vanno prese al buio per essere sicuri di selezionareun paio sinistra/destra con cui poter uscire? �

Dal principio della piccionaia seguono due altri semplici principii:

1. Se n oggetti vengono posti in n scatole, e nessuna scatola e vuota,allora ogni scatola contiene esattamente un oggetto.

2. Se n oggetti vengono posti in n scatole, e nessuna scatola contiene piudi un oggetto, allora ogni scatola contiene esattamente un oggetto.

Per esercizio li si dimostri.

Esempio. Un campione di tennis ha 9 settimane per prepararsi a ungrande torneo. Decide allora di giocare almeno una partita di allenamentoal giorno, ma, per non stancarsi troppo, non piu di 10 partite alla settimana.Si dimostri che esiste una successione di giorni durante i quali il campionegioca esattamente 35 partite.Sia p1 il numero di partite giocate fino al primo giorno, p2 il numero dipartite giocate fino al secondo (ossia giocate il primo e il secondo giorno)e cosı via fino a p63. Si ha p1 < p2 < . . . < p63. Inoltre, siccome in ognisettimana non gioca piu di 10 partite, p63 ≤ 9 × 10 = 90. Quindi

1 ≤ p1 < p2 < . . . < p63 ≤ 90.

Sommando 35 a ogni numero p1, . . . , p63 abbiamo ancora una sequanzacrescente:

36 ≤ p1 + 35 < p2 + 35 < . . . < p63 + 35 ≤ 125.

Quindi, ciascuno dei 126 numeri

p1, p2, . . . , p63, p1 + 35, p2 + 35, . . . < p63 + 35

e un numero compreso tra 1 e 125. Ne consegue che almeno due numeri sonouguali. Questi non possono essere del tipo pi, pj ne del tipo pi + 35, pj + 35,

2.2. IL PRINCIPIO DELLA PICCIONAIA, FORMA FORTE 25

quindi esistono i e j tali che pi = pj + 35. Ne consegue che nei giornij + 1, j + 2, . . . , i il tennista ha giocato esattamente 35 partite. �

Esempio. Si scelgano 101 interi compresi tra 1 e 200. Si dimostri che tra gliinteri scelti, ce ne sono almeno due tali che uno di essi e divisibile per l’altro.

Nella fattorizzazione di ogni intero, possiamo raggruppare tutti i fattori2, in modo che l’intero risulti una potenza di 2 per un numero dispari, ossiadel tipo 2k × d con d dispari. Siccome i nostri numeri sono compresi tra 1 e200, d deve essere uno tra 1, 3, 5, . . . , 199. Ci sono 100 tali numeri dispari eabbiamo preso 101 interi, per cui (almeno) due di questi hanno lo stesso d,ossia sono del tipo a = 2n × d e b = 2m × d. Per cui, se a ≤ b, a divide b,altrimenti b divide a. �

Esercizio 2.2. * Dimostrare che, scelti 100 numeri compresi tra 1 e 200,di cui almeno uno sia < 16, allora fra i numeri scelti ci sono due numeri taliche l’uno divide l’altro.

2.2 Il principio della piccionaia, forma forte

Il seguente teorema generalizza il Teorema 1:

Teorema 2: Siano r1, r2, . . . , rn interi positivi. Se

r1 + r2 + · · · + rn − n + 1

oggetti vengono posti in n scatole, allora, o la prima scatola contiene almenor1 oggetti, o la seconda ne contiene almeno r2, . . . , o la n-sima ne contienealmeno rn.

Dim: Per assurdo. Supponiamo che per ogni 1 ≤ i ≤ n la scatola icontenga meno di ri oggetti. In particolare, ne contiene al massimo ri − 1.Allora, il numero totale di oggetti sarebbe al massimo di (r1 − 1) + (r2 −1)+ · · ·+(rn − 1), ossia, al massimo r1+ r2+ · · ·+ rn−n. Ma noi abbiamosupposto che fossero r1 + r2 + · · · + rn − n + 1. ♣

Si noti che sarebbe possibile distribuire r1+r2+ · · ·+rn−n gli oggetti inn contenitori senza mettere due oggetti nello stesso contenitore (mettendoner1 − 1 nel primo, r2 − 1 nel secondo, ecc.).

Questo teorema generalizza il precedente, in quanto, se r1 = r2 = . . . =rn = 2 si ottiene esattamente il Teorema 1.


Come importanti conseguenze del Teorema 2 studiamo il caso in cuir1 = r2 = . . . = rn = q. In questo caso si ha

• Se n(q−1)+1 oggetti sono messi in n scatole, allora almeno una dellescatole contiene q o piu oggetti, o, allo stesso modo

• Se la media di n interi non-negativi a1, a2, . . . , an e maggiore di q − 1

a1 + a2 + · · · + an

n> q − 1

allora almeno uno dei numeri a1, . . . an e maggiore o uguale a q.

Quest’ultimo risultato e particolarmente importante e va ricordato, percui lo ripetiamo, anche se cambiandolo un po’:

Il massimo di n numeri naturali non puo essere piu piccolo della loro media

Chiaramente, se prendiamo n numeri tutti piu piccoli di q, anche lamedia sara piu piccola di q. Per cui, se si sa che la media e almeno pari a q,anche uno dei numeri deve essere almeno pari a q. In particolare, siccomela media e almeno pari alla media (in effetti, e proprio pari alla media!),almeno uno dei numeri (e tantopiu il massimo) deve valere almeno quantola media.

Esercizio 2.3. Si vuole comporre un mazzo di fiori che abbia almeno10 rose, o almeno 5 margherite, o almeno 8 tulipani. Quanti fiori devecontenere, come minimo, un tale mazzo?

Esercizio 2.4. John, Mary e Paul sono tre attori che appaiono in esatta-mente 10 film. Nessuno di loro ha pero girato tutti i film. In particolare,John e presente in 8 dei 10 film, Mary in 7 e anche Paul in 7. In quanti dei10 film, come minimo, appaiono tutti e 3 gli attori insieme? In quanti comemassimo?

Esempio. Un bambino ha 3 album nuovi di figurine, uno da 100 uno da80 e uno da 60 figurine. In strada trova un venditore che vende bustine difigurine dei 3 album. Ogni bustina contiene 2 figurine, non necessariamentedello stesso album. Nessuna bustina contiene due figurine uguali ne unamedesima figurina puo trovarsi in due bustine diverse. Quante bustine deveacquistare come minimo il bambino per essere sicuro di completare almenoun album?Ci sono 3 scatole (i 3 album). Per essere sicuro di completare uno dei tre

2.2. IL PRINCIPIO DELLA PICCIONAIA, FORMA FORTE 27

album, il bambino ha bisogno di (100 − 1) + (80 − 1) + (60 − 1) + 1 = 238figurine. Siccome le figurine vengono in pacchetti da 2, dovra acquistarnecome minimo 119 pacchetti. �

Esempio. Supponiamo di avere due dischi concentrici, entrambi divisi in200 settori uguali fra loro. Nel disco esterno, si dipingano arbitrariamente100 settori rossi e gli altri 100 blu. Nel disco interno, si dipingano a piacerei settori con i colori rosso e blu, ma senza alcun vincolo (ossia non devononecessariamente esserci 100 settori rossi e 100 blu). Si dimostri che e possi-bile ruotare il disco interno in modo che ci siano almeno 100 settori sul discointerno che vengono a combaciare con settori dello stesso colore sul discoesterno.Cominciamo con l’osservare che, tenendo fermo il disco esterno, ci sono 200possibili rotazioni del disco interno rispetto al disco esterno (una per perogni possibile settore j del disco interno, che viene allineato al settore 1 deldisco esterno). Contiamo tutte le volte che due settori dello stesso colorevengono allineati, su tutte le le 200 possibili rotazioni. Siccome il disco es-terno ha 100 settori di ognuno dei due colori, ogni settore del disco internosara (al girare del disco interno) allineato con esattamente 100 settori deldisco esterno dello suo colore. Per cui, il numero totale di volte che due set-tori dello stesso colore sono allineati sara di 200 (numero dei settori interni)volte 100 (numero di volte che ogni settore si allinea a un settore dello stessocolore), ossia 20000. Quindi, il numero medio di coppie di settori dello stessocolore per ogni possibile rotazione e 20000/200 = 100. Per cui c’e almenouna rotazione che porta ad avere questo numero medio o piu ossia almeno100 settori che combaciano con settori dello stesso colore. �Quest’ultimo esempio e particolarmente importante, e merita una riflessione.E un’esempio del metodo probabilistico. Supponiamo che il cerchio internosia imperniato (come il tamburo della roulette) in maniera tale da potergliimprimere una forza che lo fa ruotare, in maniera casuale, fino a fermarsiin una delle 200 rotazioni possibili. A questo evento casuale (la rotazionedel tamburo) associamo un valore (detto variabile casuale, si veda, nel se-guito, la sezione 5.2) pari al numero di coppie allineate dello stesso colore.Il calcolo che abbiamo svolto sopra ci dice, fondamentalmente, che il valormedio della variabile in questione (cioe il numero di coppie di colore ugualeche in media l’esperimento determinera) e pari a 100. E questo ci portaa concludere che l’esito dell’esperimento deve poter essere di 100 o piu inalmeno qualche caso.


Esercizio 2.5. Ad una festa si presentano 100 persone. Ogni persona eamico di un numero pari di altre persone (al limite 0). Dimostrare che cisono almeno 3 persone con lo stesso numero di amici.

Capitolo 3

Contiamo!

3.1 Principi fondamentali: somma e prodotto

In questa sezione studiamo i seguenti problemi:

• Ci sono elementi di k tipi diversi, dei quali n1 del primo tipo, n2 delsecondo tipo, ..., nk dell’ultimo tipo. In quanti modi si puo scegliereun elemento del primo tipo o del secondo tipo . . . o dell’ultimo tipo?

• Come prima, ci sono elementi di k tipi diversi, dei quali n1 del primotipo, n2 del secondo tipo, ..., nk dell’ultimo tipo. In quanti modi si puoscegliere un elemento del primo tipo e uno del secondo tipo . . . e unodell’ultimo tipo?

3.1.1 Il principio della somma

Dato un insieme S, una partizione di S e una collezione di sottoinsiemi diS, S1, . . . , Sk tali che

S = S1 ∪ S2 ∪ . . . Sk

eSi ∩ Sj = ∅ (i 6= j)

Data una tale partizione, il principio della somma afferma che:

|S| = |S1| + |S2| + · · · + |Sn|. (3.1)

Esempio. Per contare il numero di iscritti all’universita di Udine, si pos-sono sommare gli iscritti di Ingegneria agli iscritti di Scienze, a quelli diLingue, ecc (tutte le facolta). Oppure, si possono sommare gli iscritti prove-nienti da Udine, a quelli provenienti da Gorizia, da Trieste, da Padova, da

29

30 CAPITOLO 3. CONTIAMO!

... (tutte le possibili provenienze) �

Esempio. Per un ruolo di comparsa si presentano 3 giovani uomini, 2giovani donne, e 5 anziani. In quanti modi puo essere scelta la comparsa?In 3+2+5 = 10 modi. �

Alle volte, per contare la cardinalita di S puo convenire non tanto par-tizionare S in sottoinsiemi, ma considerare un sovrainsieme A di S e il com-plementare C di S rispetto ad A, a patto che le cardinalita di A e di C sianofacili da calcolare. In tal caso infatti, il principio della somma applicato aA da’

|A| = |S| + |C| (3.2)

da cui

|S| = |A| − |C| (3.3)

Esempio. Quanti sono i numeri di 2 cifre che non contengono la cifra 0e che hanno cifre diverse fra loro? Possiamo considerare come sovrainsiemel’insieme A di tutti i numeri di 2 cifre. |A| = 100. Il complementare C diS in questo esempio e dato dall’insieme dei numeri che hanno almeno unacifra 0, o hanno entrambe le cifre uguali. Ripartiamo C come C1 (l’insiemedei numeri che hanno la prima cifra uguale a 0), C2 (l’insieme dei numeriche hanno la seconda, ma non la prima, cifra uguale a 0) e C3 (l’insiemedei numeri che hanno entrambe le cifre uguali, ma diverse da 0). Abbi-amo C1 = {00, 01, . . . , 09}, e quindi |C1| = 10; C2 = {10, 20, . . . , 90}, equindi |C2| = 9; C3 = {11, 22, . . . , 99}, e quindi |C3| = 9. Ne consegue|S| = |A| − (|C1| + |C2| + |C3|) = 100 − (10 + 9 + 9) = 72. �

3.1.2 Il principio del prodotto

Sia S l’insieme di tutte le coppie ordinate del tipo (a, b), dove il primoelemento puo essere scelto in p modi, e, per ogni scelta del primo, si puoscegliere il secondo in q modi. Allora

|S| = p × q. (3.4)

Possiamo dimostrare questo principio tramite il principio della somma. Siano{a1, . . . , ap} le p scelte possibili per a. Ripartiamo S in questo modo: tuttele coppie che cominciano per a1 (ossia del tipo (a1, b), con q scelte per b),

3.1. PRINCIPI FONDAMENTALI: SOMMA E PRODOTTO 31

quelle che cominciano per a2 (ossia del tipo (a2, b)), . . ., quelle che com-inciano per ap (ossia del tipo (ap, b)). Ognuno di questi sottoinsiemi ha qelementi e ci sono p sottoinsiemi, per cui S = p × q.

Esempio. Riconsideriamo l’esempio precedente. Per creare un numero di2 cifre, in cui nessuna cifra e 0, e le cifre sono diverse, possiamo sceglierela prima cifra in 9 modi (tutte tranne la 0) e la seconda in 8 modi (tuttetranne la 0 e la prima). Per cui, ci sono 9 × 8 = 72 possibilita. �

Il principio precedente si estende immediatamente al caso piu generaledi piu di due scelte in sequenza. Ad esempio, supponendo di dover scegliereuna sequenza di n elementi (a1, . . . , an) (ossia una n-pla, che generalizza ilconcetto di coppia), in cui ci sono p1 modi di scegliere a1, p2 modi (indipen-dentemente da a1) di scegliere a2, p3 modi (indipendentemente da a1 e a2)di scegliere a3, ecc fino a an, il numero totale di possibili n-ple diverse e

p1 × p2 × · · · × pn. (3.5)

Esempio. Riconsideriamo l’esempio delle comparse. Supponendo ser-vano esattamente 1 giovane uomo, 1 giovane donna e 1 anziano, ci sono2 × 3 × 5 = 30 modi di scegliere queste 3 comparse. �

♥ Esercizio 3.1. Quante sono le possibili sequenze di DNA diverse dilunghezza n?

♥ Esercizio 3.2. Una sequenza proteica e una sequenza di amino acidi.Esistono 20 amino acidi, numerati da 1 a 20. Quante sono le possibili se-quenze proteiche di lunghezza n che terminano con l’amino acido 10 e noncontengono l’amino acido 10 in alcuna altra posizione?

♥ Esercizio 3.3. Ogni persona ha 23 coppie di cromosomi. Nel fare unfiglio, ogni genitore contribuisce con un cromosoma di ogni sua coppia, ossiacon 23 cromosomi singoli. La fusione di 23 cromosomi del padre con 23cromosomi della madre forma di nuovo un individuo completo, ossia con 23coppie. In quanti modi diversi questa ricombinazione puo avvenire?

Esercizio 3.4. In serie A ci sono 20 squadre. Ogni squadra ha una rosadi 2 portieri, 6 difensori, 5 centrocampisti e 5 attaccanti. Una squadra devescendere in campo con 1 portiere, 4 difensori, 4 centrocampisti e 2 attaccanti.In quanti modi ogni allenatore puo scegliere la formazione da mandare in


prendo a2?prendo a2?

prendo a1?

prendo a3? prendo a3? prendo a3?prendo a3?

SI

SI

SI SI SI

SI

SI

NO

NO

NO NO NO

NO

NO

{a1,a2,a3} {a1,a2} {a1,a3} {a1} {a2,a3} {a2} {a3} { }

Figura 3.1: Albero binario di tutti i sottoinsiemi

campo? In quanti modi il selezionatore della nazionale puo convocare ungruppo di 3 portieri, 7 difensori, 6 centrocampisti e 6 attaccanti attingendoda tutte le squadre?

3.2 Combinazioni (sottoinsiemi)

Studiamo il problema di determinare il numero di sottoinsiemi di un insieme.

Siano n gli elementi di un insieme A = {a1, . . . , an}. Un sottoinsieme sipuo creare rispondendo alle domande: contiene a1? contiene a2? ... contienean? Ogni domanda ha due possibili risposte. Ci sono in tutto

2 · 2 · 2 . . . 2 · 2 = 2n (3.6)

possibili risposte, ossia 2n possibili sottoinsiemi. Il sottoinsieme vuotocorrisponde a tutte risposte “no”, A stesso corrisponde a tutte risposte “sı”.

In Figura 3.1 e descritto un diagramma (detto albero) in cui si puo vederecome, dopo k decisioni ci siano 2k possibilita. In fondo al diagramma (nellefoglie dell’albero) si trovano tutti i possibili sottoinsiemi.

Un sottoinsieme ha cardinalita k solo se ci sono state k risposte “sı”e n−krisposte “no”. Vediamo in quanti modi questo puo avvenire. Per definizioneil numero di modi di scegliere k oggetti da n (ad esempio, scegliere a qualidelle n domande si e risposto “sı”), e detto n su k (scritto

(nk

)

) ed e dettoanche coefficiente binomiale. Per vedere quanto vale

(nk

)

si puo ragionarecosi’. Supponiamo di rendere diversi tra loro i k “sı” (ad esempio colorandolirosso, blu, verde - con k colori diversi). Allo stesso modo, si rendano diversigli n − k “no”. A questo punto, ci sono n! modi diversi di rispondere alle n

3.2. COMBINAZIONI (SOTTOINSIEMI) 33

domande, in cui ci sono i k “sı” mescolati con gli n − k “no”. Ora si fissiuno di questi modi (una tra le n! permutazioni). Scambiando fra loro i vari“sı”in uno qualsiasi dei k! modi, restano identificati gli stessi k elementi. Eanche scambiando fra loro (permutando) gli n − k “no”. Per cui, la stessascelta di elementi e identificata da k!(n−k)! permutazioni diverse (quelle incui restano fisse le posizioni dei “sı” e dei “no”. Ne consegue che il numerodi scelte di elementi e

(

n

k

)

=n!

k!(n − k)!(3.7)

Un modo pratico di ricordare la formula, e di mettere k numeri, inmaniera decrescente a partire da n al numeratore, e a partire da k aldenominatore, e calcolare la frazione. Ad es:

(

14

5

)

=14 · 13 · 12 · 11 · 10

5 · 4 · 3 · 2 · 1 = 14 · 13 · 11 = 2002. (3.8)

Esempio. Quante sono le possibili cinquine su una ruota fissa? Sono(90

5

)

= 43′949′268. �.

Vediamo ora alcune formule importanti sul coefficiente binomiale:

Teorema 3:(nk

)

=(n−1

k

)

+(n−1k−1

)

Dim: Fissato un elemento, ci sono 2 possibilita per fare un sottoinsiemedi k elementi: o l’elemento non e nel sottoinsieme (e quindi ci sono

(n−1k

)

sottoinsiemi possibili di questo tipo), oppure e nel sottoinsieme (e quindibisogna scegliere k − 1 altri elementi fra i rimanenti n-1). ♣

Esercizio 3.5. Dimostrare il teorema 3 algebricamente, a partire dallaformula per il coefficiente binomiale.

Il ragionamento precedente puo essere generalizzato in questo modo.Dovendo scegliere un sottoinsieme di dimensione k, si supponga di fissare pelementi, con 1 ≤ p ≤ k. Allora, o l’insieme non contiene alcuno di questi pelementi, o ne contiene uno, o ne contiene due, . . ., o li contiene tutti. Inognuna di queste situazioni, supponendo che il sottoinsieme ne contenga itra i p fissati, i rimanenti k − i vanno scelti dagli n − p non fissati. Inoltre,gli i possono essere presi in

(pi

)

modi. Ne consegue:(

n

k

)

=p∑

i=0

(

p

i

)(

n − p

k − i

)

. (3.9)


Teorema 4:(nk

)

=( nn−k

)

Dim: Si puo dimostrare dalla formula. Oppure, pensando al significato:scegliere i k elementi da tenere equivale a scegliere gli n − k da scartare. ♣

Altre formule importanti:

(

n

n

)

=

(

n

0

)

= 1

(

n

1

)

= n

(

n

2

)

= n(n − 1)/2 (il numero di coppie distinte di 2 elementi)

(

n

p

)

= 0,per p > n

Esercizio 3.6. Quanto vale∑n

i=0

(ni

)

?

Esempio. Quanti sono i sistemi al totocalcio da 10 triple e 3 fisse? Ci sono13 partite. Le triple possono essere scelte in

(139

)

= 715 modi. Per ognunodi tali modi, si possono completare le rimanenti 4 parite in 34 = 729 modi(ossia ogni fissa puo essere scelta tra 1, 2 e X, e se ne devono scegliere 4).In totale abbiamo 715 × 729 = 521235 possibilita. �

Esercizio 3.7. Dati a, b e c tali che a + b + c = 13, quanti sono i sistemida a fisse, b doppie e c triple?

Esercizio 3.8. Quattro giocatori fanno una mano di poker, usando unintero mazzo da 52 carte. In quanti modi diversi possono essere distribuitele carte, sapendo che a ogni giocatore vengono date 5 carte?

3.2.1 Triangolo di Pascal

Il triangolo di Pascal e ottenuto in questo modo: si creano delle righe (nu-merate da 0 in poi) e in ogni riga i ci sono i + 1 elementi (numerati da 0 ai). L’elemento k della riga n vale

(nk

)

. Disponendoli in triangolo si ottienelo schema

3.2. COMBINAZIONI (SOTTOINSIEMI) 35

11 1

1 2 11 3 3 1

1 4 6 4 11 5 10 10 5 1

Si noti che per via del teorema 3 un elemento e ottenuto dalla sommadei due elementi sopra a lui (a sin e dx).

Supponiamo di volere calcolare lo sviluppo di (a + b)n. Ossia

Π = (a + b)(a + b) · · · (a + b)

Lo sviluppo sara del tipo∑

c(i, j)aibj, dove la somma e estesa a tutte lecoppie di i e j tali che i + j = n. Scegliendo a da i termini in Π e b dairimanenti n − i si ottiene un termine aibn−i. Questo puo essere fatto in

(ni

)

modi (per cui c(i, j) =(n

i

)

=(nj

)

nell’espressione precedente). Si ottiene

(a + b)n =n∑

i=0

(

n

i

)

aibn−i (3.10)

Ad es. dalla riga 5 del triangolo di Pascal, si ottiene

(a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5 (3.11)

♥ Esempio. L’allineamento di 2 sequenze di DNA, una di lunghezza n el’altra di lunghezza m ≥ n consiste nel disporle una sopra l’altra, inserendospazi (detti gap, e indicati con “-”) nelle due in modo che diventino dellastessa lunghezza, ma senza mai mettere due spazi “-” uno sopra l’altro.

Ad esempio, questo e un possibile allineamento delle sequenze ATCCGA eTCAAAGA:

ATCC---GA

-T-CAAAGA

Mentre il seguente allineamento non risulta valido:

A-TCC---GA

--TCAA-AGA

Quanti sono i possibili diversi allineamenti validi di due sequenze?


Si puo ragionare cosı: la lunghezza l delle due sequenze allineate va’ daun minimo di m a un massimo di n + m. Per ognuna di tali lunghezze, sipuo piazzare la sequenza piu piccola (la prima) in

( ln

)

modi, occupando ndelle l posizioni con lettere, e le rimanenti l−n con gaps. Siccome a ognunodei gap deve corrispondere una lettera vera della seconda sequenza, restanom− (l−n) lettere da mettere nelle n posizioni corrispondenti a lettere dellaprima sequenza. Otteniamo che gli allineamenti sono

n+m∑

l=m

(

l

n

)(

n

m − l + n

)

�

3.3 Disposizioni (sottoinsiemi ordinati)

Supponiamo di voler selezionare una sequenza di k oggetti da un insiemedi n, e che quindi l’ordine degli oggetti abbia importanza (come insiemi,{3, 1, 2} = {1, 2, 3}, ma come sequenze, ossia insiemi ordinati, (3, 1, 2) 6=(1, 2, 3)).

Il numero di sottoinsiemi ordinati di dimensione k si dice anche dispo-

sizioni di n oggetti a k a k e si indica con D(n, k). Siccome ogni sottoinsiemedi dimensione k puo essere ordinato in k! modi, abbiamo

D(n, k) =

(

n

k

)

k! (3.12)

Mnemonicamente, D(n, k) e il prodotto dei primi k numeri decrescenti,a partire da n:

D(n, k) =n!

(n − k)!= n(n − 1) · · · (n − k + 1).

Casi speciali: D(n, 0) = 1, D(n, 1) = n, D(n, n) = n! e D(n,m) = 0 perm > n.

Esempio. Quante sono le possibili estrazioni al lotto sulla ruota di Venezia?Sono 90 · 89 · 88 · 87 · 86. �

Esercizio 3.9. Quanti codici di 4 lettere diverse si possono formare sceglien-do le lettere dall’insieme {A, B, K, L, M, P}?

3.4. RIPETIZIONI E MULTI-INSIEMI 37

Esercizio 3.10. In quanti modi p ragazzi possono essere assegnati a qfamiglie disposte a ospitarli, al piu uno per famiglia, per una vacanza all’es-tero, con p ≤ q?

3.4 Ripetizioni e multi-insiemi

Un multi-insieme e costituito da un insieme S = {a1, . . . , ak} in cui glielementi possono essere ripetuti piu volte. Il numero di volte che ai e presentein S si indica con ni ed e detto numero di ripetizioni. La scrittura concisadi un multi-insieme e

{n1 · a1, n2 · a2, . . . , nk · ak} (3.13)

Ad esempio, un multi-insieme con tre A, quattro B e due C si indicacome

{3 · A, 4 · B, 2 · C}Una possibile permutazione di questi elementi e AABCABBCB. Un’altra

e BBACCABAB. Vogliamo contare quente sono le permutazioni di un multi-insieme.

Esempio. Quanti sono gli anagrammi della parola MISSISSIPPI?Si puo guardare alla parola come al multi-insieme {1 ·M, 4 ·I, 4 ·S, 2 ·P}.

Supponiamo di considerare tutte le 11! permutazioni delle lettere (anagram-mi). Per ognuna di tali permutazioni, possiamo scambiare fra di loro le I (ole S, o le P,...) e l’anagramma rimane lo stesso. Le 4 I si possono riordinarein 4! modi, e similmente per le altre lettere. Si ottiene un totale di 11!

1!·4!·4!·2!possibilita. �

Generalizziamo il risultato dell’esercizio precedente:

Teorema 5 : Sia S un multi-insieme con oggetti di k tipi e numeri diripetizione n1, n2, . . . , nk. Sia n la dimensione di S, dove n = n1 +n2 + · · ·+nk. Allora il numero di permutazioni di S e pari a

n!

n1!n2! · · ·nk!

Dim: Siano a1, a2, . . . , ak gli elementi di S, con ai ripetuto ni volte, peri = 1, . . . , k. Possiamo costruire una permutazione di S in questo modo.Dobbiamo riempire n posizioni con i nostri oggetti. Prima piazziamo gli n1

elementi di tipo a1. Questo puo essere fatto in( nn1

)

modi. Tra le rimanenti


n− n1 posizioni, piazziamo gli n2 elementi di tipo a2. Questo si puo fare in(n−n1

n2

)

modi. Proseguiamo in questo modo fino alla fine, ossia fino a piazzaregli nk oggetti di tipo ak nelle n − n1 − n2 − · · · − nk−1 posizioni rimaste (sinoti che nk = n − n1 − n2 − · · · − nk−1 e quindi questo puo essere fatto inun unico modo). Si ottiene che il numero di permutazioni e

(

n

n1

)(

n − n1

n2

)(

n − n1 − n2

n3

)

· · ·(

n − n1 − n2 − · · ·nk−1

nk

)

Dalla definizione di coefficiente binomiale, si ottiene che il numero euguale a

n!

n1!(n − n1)!· (n − n1)!

n2!(n − n1 − n2)!· (n − n1 − n2)!

n3!(n − n1 − n2 − n3)!· · ·

Semplificando numeratori e denominatori, si ottiene

n!

n1!n2! · · · nk!

♣

3.4.1 Combinazioni con ripetizioni

Supponiamo dato un multi-insieme S = {n1 · a1, n2 · a2, . . . , nk · ak}. Sup-poniamo di voler prendere r elementi di S. Ogni sottoinsieme di r elementidi S si chiama una r-combinazione di S.

Esempio. Sia S = {2 · a, 1 · b, 3 · c}. Allora le 3-combinazioni di S sono:{2 · a, 1 · b}, {2 · a, 1 · c}, {1 · a, 1 · b, 1 · c}, {1 · a, 2 · c}, {1 · b, 2 · c} e {3 · c}.�

Supponiamo ni ≥ r per ogni i (in modo tale che ci sia una quantitasufficiente di elementi di tipo ai per poter, al limite, prendere gli r elementitutti dello stesso tipo). Per calcolare quante sono le r permutazioni di S,dobbiamo scegliere quanti prenderne per ognuno dei k tipi, in modo daprenderne esattamente r in totale.

Questo problema corrisponde al problema di ripartire r elementi in kgruppi, che a sua volta corrisponde a risolvere l’equazione

x1 + x2 + . . . + xk = r (3.14)

dove ogni xi e un numero intero, 0 ≤ xi ≤ r. Ci chiediamo quante sonole soluzioni diverse. Consideriamo r simboli uguali (ad es. A) e aggiungiamo

3.4. RIPETIZIONI E MULTI-INSIEMI 39

k− 1 simboli che serviranno da separatori (ad es il simbolo “|”). Piazzandoi separatori all’interno delle A, le ripartiamo in k blocchi, delimitati daiseparatori. La dimensione del blocco i e il valore xi, che soddisfa l’equazione(3.14).

Ad esempio, se r = 8 e k = 4, scrivendo

AA|A|AAA|AA

identifichiamo la soluzione x1 = 2, x2 = 1, x3 = 3, x4 = 2. Invece, lascrittura

A|||AAAAAAA

identifica la soluzione x1 = 1, x2 = 0, x3 = 0, x4 = 7.In quanti modi si possono mescolare k − 1 “|” con r “A”? Abbiamo un

totale di r + k − 1 posizioni. Dobbiamo scegliere le k − 1 posizioni occupatedai separatori (le rimanenti sono occupate da A). Si ottengono

(

r + k − 1

k − 1

)

(3.15)

possibilita. Abbiamo percio dimostrato il seguente teorema:

Teorema 6: Il numero di r-combinazioni di un multi-insieme S = {n1 ·a1, n2 · a2, . . . , nk · ak}, con ni ≥ r per ogni i = 1, . . . , k, e

(

r + k − 1

k − 1

)

.

Esercizio 3.11. Ho 8 caramelle dello stesso tipo. In quanti modi diversiposso darle a 10 bambini?

Esempio. Ogni persona ha nel portafoglio al piu 15 banconote, in taglida 5, 10, 20, 50 e 100 euro. Qual’e la probabilita che a Udine non ci siano2 persone con gli stessi tagli nello stesso numero?

Sia l il numero di banconote. Ci sono 5 tagli, per cui(l+4

4

)

portafoglidiversi con l banconote. Il massimo di possibilita si ha per l = 15 in cui sono(19

4

)

= 3876. Anche ammettendo che per ogni altro l ci fossero altrettantepossibilita ci sarebbero al piu 16 × 3876 = 62016 portafogli diversi. Per ilprincipio della piccionaia, ci sono almeno due persone con gli stessi tagli,nelle stesse quantita. �


Esercizio 3.12. Avendo a disposizione 100 mele, 80 pere, 100 arance e 40banane, quanti diversi cesti di frutta si possono comporre che contenganoesattamente 30 frutti?

3.5 I numeri di Fibonacci

Si consideri il seguente esempio. Supponiamo che una coppia di conigli possariprodursi a partire dall’eta di 2 mesi. A partire da quell’eta, la coppia siriproduce ogni mese, dando luogo a una nuova coppia di conigli. Supponendodi partire con una coppia appena nata, ci si chiede quante coppie si avrannodopo n mesi. Chiamiamo Fn il numero di coppie dopo n mesi. AbbiamoF0 = 1 e F1 = 1. All’eta di 2 mesi la coppia ne genera una nuova, per cuiF2 = 2. Al mese successivo, la coppia si riproduce di nuovo e quindi F3 = 3.Si puo continuare ottenendo F4 = 5, F5 = 8, F6 = 13, ecc. La legge generalerisulta

Fn = Fn−1 + Fn−2 (3.16)

in quanto, al tempo n saranno vive tutte le coppie del tempo n−1 (ossiaFn−1), piu tutte le coppie neonate. Queste ultime sono pari al numero dicoppie che al tempo n hanno almeno 2 mesi, ossia le coppie che erano viveal tempo n − 2 (i.e., Fn−2).

La successione (3.16) e nota come successione dei numeri di Fibonacci inonore del loro scopritore, il matematico pisano Leonardo Fibonacci, vissutonel 1200 circa. E una successione molto importante, in quanto i numeri diFibonacci si ritrovano in innumerevoli situazioni, ed esistono anche pubbli-cazioni scientifiche periodiche dedicate alle loro applicazioni. Vediamo oraalcuni semplici esempi.

Esempio. Si supponga di voler parcheggiare delle limousine e delle util-itarie sul lato di una strada rettilinea. Ogni limousine occupa 2 spazi diparcheggio, mentre un’utilitaria ne occupa uno solo. Ci chiediamo in quantimodi diversi si possono parcheggiare questi due tipi di macchina in mododa riempire tutti gli spazi a disposizione.

Chiamiamo Mn il numero di modi di riempire n spazi. Supponiamo glispazi numerati da 1 a n. Possiamo distinguere due situazioni. O lo spazio 1e occupato da un’utilitaria, e quindi restano gli altri n− 1 spazi da riempire(in Mn−1 modi) o lo lo spazio 1 e occupato da una limousine. In questocaso, la limousine occupa anche lo spazio 2, e restano gli altri n− 2 spazi dariempire (in Mn−2 modi). Si deduce Mn = Mn−1 + Mn−2. Siccome M1 = 1e M2 = 2, si ricava che la sequenza Mn e esattamente la sequenza dei numeri

3.5. I NUMERI DI FIBONACCI 41

di Fibonacci. �

Esempio. Si consideri una scacchiera 2 × n. Un pezzo del domino copreesattamente 2 caselle di tale scacchiera. Ci si chiede in quanti modi sipossono disporre n pezzi del domino in modo da coprire tutte le caselledella scacchiera. Chiamiamo Dn il numero di tali modi.

Consideriamo la scacchiera come composta da 2 righe e n colonne, nu-merate da 1 a n. Possiamo distinguere due situazioni. O la colonna 1 ecoperta da un domino posizionato verticalmente, e quindi restano le altren − 1 colonne da coprire (in Dn−1 modi) o la colonna 1 e coperta da duedomino posizionati orizzontalmente. In questo caso, i due pezzi coprono an-che la colonna 2, e restano le altre n− 2 colonne da coprire (in Dn−2 modi).Si deduce Dn = Dn−1 + Dn−2. Siccome D1 = 1 e D2 = 2, si ricava che lasequenza Dn e esattamente la sequenza dei numeri di Fibonacci. �

La formula (3.16) che definisce la successione dei numeri di Fibonacci euna formula ricorsiva. Esiste anche una formula chiusa (ossia una funzionedi n) che permette di calcolare direttamente l’n-simo numero di Fibonacci.Tale formula risulta un po’ particolare, in quanto, pur contenendo il numeroirrazionale

√5, fornisce valori interi per ogni valore di n. La riportiamo,

senza dimostrarne la validita:

Fn =1√5(1 +

√5

2)n+1 − 1√

5(1 −

√5

2)n+1. (3.17)

La formula (3.17) da’ anche un’idea della crescita esponenziale dellafunzione Fn.

Capitolo 4

Il principio diinclusione-esclusione

4.1 Il principio base

Supponiamo di avere un insieme S e alcune proprieta P1, P2, . . . , Pm. Ognielemento di S puo possedere o meno la proprieta Pi, per i = 1, . . . ,m. Adesempio, se S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} e P1 e la proprieta “essere dispari”,e P2 e la proprieta “essere divisibile per 3”, allora

• 9 possiede sia la P1 che la P2

• 5 possiede la P1 ma non la P2

• 6 possiede la P2 ma non la P1

• 8 non possiede ne la P1 ne la P2

Denotiamo con Ai l’insieme degli elementi di S che possiedono la propri-eta Pi, per i = 1, . . . ,m. Indichiamo inoltre con Ai il complementare di Ai

in S, ossia l’insieme degli elementi di S che non possiedono la proprieta Pi.L’insieme degli elementi di S che non possiede alcuna delle proprieta sarapertanto

A1 ∩ A2 ∩ · · · ∩ Am.

Il seguente teorema e noto come principio di inclusione-esclusione:

Teorema 7 : Il numero di elementi di S che non possiede alcuna delle

43

44 CAPITOLO 4. IL PRINCIPIO DI INCLUSIONE-ESCLUSIONE

proprieta P1, . . . , Pm e

|A1 ∩ A2 ∩ · · · ∩ Am| = |S|−∑{i1} |Ai1 |+∑

{i1,i2} |Ai1 ∩ Ai2 |−∑{i1,i2,i3} |Ai1 ∩ Ai2 ∩ Ai3 |· · ·+(−1)d∑

{i1,...,id}|Ai1 ∩ Ai2 ∩ · · · ∩ Aid |

· · ·+(−1)m|A1 ∩ A2 ∩ · · · ∩ Am|

(4.1)

dove gli indici della generica somma∑

{i1,...,id}sono tutti i sottoinsiemi di

{1, . . . ,m} di cardinalita d.

Ad esempio, se m = 3 il teorema afferma che

|A1 ∩ A2 ∩ A3| = |S| − (|A1| + |A2| + |A3|)+(|A1 ∩ A2| + |A1 ∩ A3| + |A2 ∩ A3|)−|A1 ∩ A2 ∩ A3|

Dimostriamo il teorema.Dim: Facciamo vedere che ogni elemento di S che non ha alcuna delleproprieta contribuisce 1 al valore della somma a destra nell’equazione (4.1),mentre un elemento che ha n > 0 delle proprieta contribuisce 0 al valore ditale somma. Pertanto, il valore di tale somma e esattamente pari al numerodi elementi che non hanno nessuna delle proprieta.

Consideriamo allora un elemento x che non ha alcuna delle proprieta. Siha che x ∈ S ma x /∈ Ai per i = 1, . . . ,m. Pertanto il contributo di x allasomma in questione e

1 − 0 + 0 − 0 + · · · + (−1)m0 = 1.

Supponiamo ora che y sia un elemento che ha esattamente n ≥ 1 delleproprieta. Il contributo di y a |S| e 1. Il contributo di y a

∑

{i1} |Ai1 | e n =(n1

)

, perche y possiede esattamente n proprieta, e pertanto e in esattamenten degli insiemi A1, . . . , Am. Il contributo di y a

∑

{i1,i2} |Ai1 ∩ Ai2 | e(n2

)

,perche ci sono

(n2

)

modi di scegliere 2 proprieta possedute da y, ossia dueinsiemi Ai1 e Ai2 ai quali y appartiene. Analogamente, il contributo di y a∑

{i1,i2,i3} |Ai1 ∩Ai2 ∩Ai3 | e(n3

)

. Proseguendo in questo modo, il contributonetto di y alla somma in (4.1) e

(

n

0

)

−(

n

1

)

+

(

n

2

)

−(

n

3

)

+ · · · + (−1)m

(

n

m

)

4.1. IL PRINCIPIO BASE 45

che, essendo n ≤ m, e uguale a

(

n

0

)

−(

n

1

)

+

(

n

2

)

−(

n

3

)

+ · · · + (−1)m

(

n

n

)

. (4.2)

Ma, sviluppando il valore dell’espressione (1− 1)n secondo il il triangolodi Pascal, si nota che tale espressione e esattamente uguale a (4.2), chepertanto deve valere 0. Quindi il contributo di y alla somma (4.1) e 0, e ilteorema e dimostrato. ♣

Esempio. Quanti sono i numeri compresi tra 1 e 1000 che non sonodivisibili per 5, ne per 6, ne per 8?

Usiamo il principio di inclusione-esclusione. Identifichiamo S come l’in-sieme {1, 2, . . . , 1000}. La proprieta P1 e quella di essere divisibile per 5. Laproprieta P2 e quella di essere divisibile per 6. La proprieta P3 e quella diessere divisibile per 8. Abbiamo che

|A1| = b1000

5c = 200

|A2| = b1000

6c = 166

|A3| = b1000

8c = 125.

Un numero e in A1 ∩ A2 se e divisibile per il minimo comune multiplo di5 e 6, ossia per mcm{5, 6} = 30. Analogamente si ragiona per i numeri inA1 ∩A3 (divisibili per mcm{5, 8} = 40) e i numeri in A2 ∩A3 (divisibili permcm{6, 8} = 24). Abbiamo

|A1 ∩ A2| = b1000

33c = 200

|A1 ∩ A3| = b1000

40c = 25

|A2 ∩ A3| = b1000

24c = 41.

Infine, un numero e in A1 ∩A2 ∩A3 se e divisibile per il minimo comunemultiplo di 5, 6 e 8, ossia per mcm{5, 6, 8} = 120. Si ha

|A1 ∩ A2 ∩ A3| = b1000

120c = 8.


In conclusione, si hanno 1000−(200+166+125)+(200+25+41)−8 = 767numeri del tipo desiderato. �

Esempio. Quante sono le permutazioni delle lettere

C,A,N,E,D,I,U,G,O

in cui non si legge ne la parola “CANE”, ne la parola “DI”, ne la parola“UGO”? Ad esempio, la permutazione NEDUOICAG va bene, cosı comeUIDEACGON, mentre non vanno bene OGCANEIDU ne EIDCUGOAN.

Usiamo il principio di inclusione-esclusione. Identifichiamo S come l’in-sieme di tutte le permutazioni delle 9 lettere date. La proprieta P1 e quella dicontenere la parola “CANE”. La proprieta P2 e quella di contenere la parola“DI”. La proprieta P3 e quella di contenere la parola “UGO”. L’insieme A1

corrisponde a tuttte le permutazioni dei 6 simboli

{CANE, D, I, U,G,O}

e pertanto |A1| = 6!. Similmente, A2 sono le permutazioni degli 8 simboli{C,A,N,E,DI, U,G,O} e |A2| = 8!. Infine, A3 corrisponde alle permu-tazioni dei 7 simboli {C,A,N,E,D, I,UGO} e |A3| = 7!. L’insieme A1 ∩A2

corrisponde a tutte le permutazioni dei simboli {CANE,DI, U,G,O}, e per-tanto |A1 ∩ A2| = 5!. Analogamente |A1 ∩ A3| = 4! e |A2 ∩ A3| = 6!. Infine,A1 ∩ A2 ∩ A3 corrisponde a tutte le permutazioni di {CANE,DI,UGO} e|A1 ∩ A2 ∩ A3| = 3!. Per il principio di inclusione esclusione, il numerodi permutazioni cercato e 9! − (6! + 8! + 7!) + (5! + 4! + 6!) − 3! ossia362880 − 720 − 40320 − 5040 + 120 + 24 + 720 − 6 = 317658. �

Esercizio 4.1. Quante sono le permutazioni delle 10 lettere

V, I, V, A, L, A, V, I, T, A

in cui non si legge ne “VIVA”, ne “LA” ne “VITA”?

Esercizio 4.2. Quante sono le permutazioni delle 6 lettere

V, I, A, V, A, I

in cui non si legge ne “VIA” ne “VAI”? (Risp: 46)

4.2. SPIAZZAMENTI (DERANGEMENTS) 47

Esercizio 4.3. Quanti interi compresi tra 0 e 99999 hanno fra le loro cifresia 2 che 5 che 8?

Esercizio 4.4. In quanti modi si possono piazzare 8 torri su una scacchiera8 × 8 in modo che nessuna attacchi alcuna delle altre. In quanti modi sesupponiamo di avere 3 torri di colore rosso tre blu, e 2 nere (con le torridello stesso colore indistinguibili fra loro)? In quanti modi infine se tutte letorri sono distinguibili fra loro?

4.2 Spiazzamenti (derangements)

Un gruppo di amici, in occasione del Natale, decide di scambiarsi i regali inmodo anomalo. Ogni persona, anziche fare un regalo a tutte le altre (troppocostoso) scrive il suo nome su un foglio di carta e lo mette in un vaso. Ilvaso viene poi mescolato ed ognuno estrae un biglietto. Ogni persona dovrafare un solo regalo, alla persona il cui nome e scritto sul biglietto che haestratto. Sfortunatamente, qualcuno puo estrarre il suo stesso nome, nelqual caso non avra regali (a meno che non se lo compri da solo, ma allora,addio sorpresa). Ci chiediamo qual e la probabilita che cio non accada.

Una permutazione π = (π1, . . . , πn) si dice spiazzamento se πi 6= i per i =1, . . . , n. Ad esempio, (2, 1, 4, 5, 3) e (3, 4, 1, 5, 2) sono spiazzamenti, mentre(5, 2, 1, 3, 4) e (4, 1, 3, 2, 5) non lo sono. Il problema degli amici corrisponde adeterminare quanti sono gli spiazzamenti di n elementi. Chiamiamo questonumero Zn.

Teorema 8: Per n ≥ 1 si ha

Zn = n!(1 − 1

1!+

1

2!− 1

3!+ · · · + (−1)n 1

n!) (4.3)

Dim: Sia S l’insieme di tutte le permutazioni di {1, . . . , n}. Per i =1, . . . , n sia Pi la proprieta che, in una permutazione, i e nella sua posizioneoriginale (ossia, πi = i). Quindi, una permutazione e uno spiazzamento senon ha alcuna delle proprita P1, . . . , Pn. Se Ai e l’insieme di permutazioniche hanno la proprieta Pi, abbiamo

Zn = |A1 ∩ A2 ∩ · · · ∩ An|.

Usiamo il principio di inclusione-esclusione. Le permutazioni in A1 sonotutte quelle che cominciano per “1”, da cui |A1| = (n − 1)!. Allo stessomodo, |Ai| = (n − 1)! per ogni i, in quanto, una volta piazzato i nellaposizione i, restano (n − 1)! modi di piazzare i rimanenti n − 1 elementi


nelle n − 1 rimanenti posizioni. Le permutazioni in A1 ∩ A2 sono quelle incui 1 e al primo posto e 2 e al secondo. I rimanenti n − 2 elemnti possonoessere ordinati in tutti i modi. Si ottiene |A1 ∩A2| = (n−2)!, e, similmente,|Ai ∩Aj | = (n− 2)!, per ogni 1 ≤ i < j ≤ n. Proseguendo allo stesso modo,si ha, in generale

|Ai1 ∩ Ai2 ∩ . . . ∩ Aik | = (n − k)!

per ogni 1 ≤ i1 < i2 · · · < ik ≤ n. Siccome ci sono(nk

)

scelte di k indici1 ≤ i1 < i2 · · · < ik ≤ n, dal principio di inclusione-esclusione abbiamo

Zn = n!−(

n

1

)

(n−1)!+

(

n

2

)

(n−2)!−(

n

3

)

(n−3)!+ · · ·+(−1)n

(

n

n

)

(n−n)!

Dalla definizione di coefficiente binomiale segue che, per ogni 1 ≤ k ≤ n,(nk

)

(n − k)! = n!k! , per cui si ottiene

Zn = n! − n!

1!+

n!

2!− n!

3!. + · · · + (−1)n n!

n!

Raggruppando n! si ha

Zn = n!(1 − 1

1!+

1

2!− 1

3!+ · · · + (−1)n 1

n!).

♣Ricordando dall’analisi che l’espansione in serie di e−1 e

e−1 = 1 − 1

1!+

1

2!− 1

3!+

1

4!+ · · · (4.4)

abbiamo che

Zn ' n!

e. (4.5)

Questo risultato e tanto piu accurato quanto piu grande e n, ma non enecessario che n sia molto grande per avere gia una buona approssimazione.Infatti, troncando lo sviluppo di 1

e in (4.4) al termine n, si ottiene un’ap-prossimazione di 1

e molto vicina al valore corretto (corretta in almeno 3 cifredecimali) gia per n = 7. Da un punto di vista pratico, possiamo concludereche la frazione di permutazioni che sono spiazzamenti e 1

e del totale. Quindila probabilita che uno degli amici dell’esempio estragga il suo stesso nome e(circa) 1

e . E curioso il fatto che questa probabilita non dipenda da n e restisostanzialmente la stessa sia che gli amici siano 10, sia che siano 100000.

4.2. SPIAZZAMENTI (DERANGEMENTS) 49

Esercizio 4.5. Ad una festa ci sono n uomini e n donne. In quanti modigli uomini possono scegliere una compagna per il primo ballo? In quantimodi per il secondo ballo, nell’ipotesi che ognuno debba cambiare partner?

Esercizio 4.6. Uno studente viene a sapere che in un test a scelta multipla,la risposta esatta ad ogni domanda ha un numero sempre diverso. Ci sono 6domande, ognuna con 6 risposte a scelta, e lo studente non ha studiato nulla,per cui risponde sostanzialmente a caso. Qual e la sua strategia migliore (chemassimizza il numero di risposte esatte) tra (i) rispondere sempre “1” (ii)tirare un dado ad ogni domanda e dare la risposta relativa al numero cheesce (iii) scegliere a caso una permutazione dei numeri {1, . . . 6} e rispondereseguendo tale permutazione. Si generalizzi tale problema al caso generico din domande, con n scelte per risposta.

Capitolo 5

Probabilita combinatorie

In questo capitolo consideriamo alcune applicazioni al campo della teoriadelle probabilita delle nozioni combinatoriche fin qui acquisite. In partico-lare, supponendo di trovarci in uno spazio in cui tutti i possibili risultati

sono equiprobabili, la probabilita di un evento (visto come un sottoinsiemedi risultati) dipende unicamente dalla cardinalita di tale evento.

5.1 Concetti elementari

Sia S l’insieme universo di tutti i possibili risultati (o punti dello spazio diprobabilita). In questo capitolo, assumiamo sempre che S sia un insiemefinito. Una misura di probabilita e una funzione P che soddisfa:

P (S) = 1 (5.1)

0 ≤ P (A) ≤ 1 ∀A ⊆ S (5.2)

P (A ∪ B) = P (A) + P (B) ∀A,B ⊆ S tali che A ∩ B = ∅. (5.3)

La probabilita si dice distribuita uniformemente se P ({a}) = 1/|S| perogni a ∈ S, ossia se tutti gli eventi elementari sono equiprobabili. Adesempio, i risultati del lancio di un dado danno luogo all’universo S ={1, 2, 3, 4, 5, 6} e ogni risultato e equiprobabile (con probabilita 1/6).

Si noti che, detta p = 1/|S|, se la distribuzione e uniforme, ogni eventoA ha probabilita P (A) = p|A| e quindi la probabilita dipende unicamentedalla cardinatita di A. In questo caso, calcolare la probabilita di un’evento

51

52 CAPITOLO 5. PROBABILITA COMBINATORIE

(un insieme) coincide con il contarne il numero di elementi, per cui ritornanoutili le tecniche acquisite nei capitoli precedenti.

Alle volte la probabilita di un evento puo essere condizionata dal ver-ificarsi di un secondo evento. Ad esempio, la probabilita che in un lanciodi dado sia uscito un numero maggiore di 3 e 1/2. Se pero sappiamo che ilnumero uscito e pari, la probabilita che sia maggiore di 3 diventa 2/3.

Si definisce probabilita condizionata di A dato il verificarsi di B il numero

P (A|B) =P (A ∩ B)

P (B). (5.4)

In pratica, sapendo che B si e verificato, la probabilita che anche A si siaverificato e data dalla frazione di elementi di A che sono anche elementi diB, rispetto a tutti gli elementi di B (che diventa, implicitamente, il nuovouniverso). Si noti che dalla definizione segue P (B|B) = 1 e P (A|B) = 0 seA ∩ B = ∅, o, come si dice in questo caso, A e B sono eventi incompatibili.

Si dice che due eventi A e B sono indipendenti se

P (A ∩ B) = P (A)P (B)

Si noti che, per due eventi indipendenti, si ha P (A|B) = P (A) (ossia, ilverificarsi di A non dipende in alcun modo dal verificarsi di B, visto che laprobabilita di A resta la stessa).

Esempio. Qual e la probabilita che a briscola, l’asso di briscola vengapescato come ultima carta?

La briscola e una carta diversa da un asso (36 possibilita.) Per tale carta,ne restano 39 di cui una sola e l’asso giusto. Per cui ci sono 38! permutazioniche terminano con l’asso giusto. Quindi il totale e 36·38!

40 ossia 3640·39 = 3

130 . �

Esercizio 5.1. Sapendo che briscola e “Spade”, qual e la probabilita chel’asso di briscola sia pescato come ultima carta?

Esempio. Nel gioco del poker, qualora ci siano n giocatori, la carta piupiccola utilizzata vale 11 − n. Ad esempio, 4 giocatori utilizzano un mazzoche consiste delle seguenti carte: A, K, Q, J, 10, 9, 8, 7 (un totale di 4×8 = 32carte). Ci chiediamo qual e la probabilita che 5 carte prese a caso da questomazzo realizzino un full e qual e la probabilita che realizzino “colore”.

Un full e formato da un tris piu una coppia. Il tris puo essere sceltoin 8 × (4

3

)

= 32 modi. Infatti, ci sono 8 possibilita di scegliere se il tris ed’assi, di re, ecc. e, una volta scelto questo, ci sono 4 carte di quel tipo (ad

5.1. CONCETTI ELEMENTARI 53

es. 4 assi) nel mazzo, da cui ne dobbiamo scegliere 3. La coppia puo esserescelta in 7 × (4

2

)

= 42 modi. Infatti, il ragionamento e lo stesso di prima,ma, siccome la coppia deve essere diversa dal tris, si hanno solo 7 possibilitaper scegliere il tipo di coppia. In totale abbiamo 32 × 42 = 1344 modi (su(32

5

)

) di formare un full con 5 carte.

Un colore e dato da 5 carte dello stesso seme. Il seme puo essere sceltoin 4 modi. Una volta scelto il seme, ci sono 8 carte di quel seme nel mazzo,da cui ne dobbiamo scegliere 5 (in

(85

)

= 56 modi). Quindi, in totale ci sono4 × 56 = 224 mani che realizzano il colore. In conclusione, se ci sono 4giocatori, e 6 volte piu probabile realizzare full che colore, e quindi il colorebatte il full nella scala dei valori.

Diversa e la situazione qualora ci fossero piu giocatori. Si consideri uncaso limite di 9 giocatori. Il mazzo consiste delle seguenti carte: A, K, Q,J, 10, 9, 8, 7, 6, 5, 4, 3, 2 (un totale di 4 × 13 = 52 carte).

Un full puo essere scelto in 13 × (43)× 12 × (42

)

= 3744 modi diversi. Un

colore puo essere scelto in 4 × (135

)

= 15444 modi. Per cui, in questo caso,un colore e circa 4 volte piu probabile di un full, per cui il full batte il colorenella scala dei valori. �

Esercizio 5.2. Si determini il numero massimo di giocatori al poker per ilquale il full e piu probabile del colore.

5.1.1 Processi Bernoulliani

Si consideri un esperimento che puo terminare in due modi, denominati“successo” e “fallimento”. Denotiamo con p e con q = 1−p la probabilita disuccesso e fallimento rispettivamente. Ad esempio, se l’esperimento consistenel lancio di una moneta e se definiamo l’uscita di testa come successo equella di croce come fallimento, abbiamo p = q = 1/2. Se invece l’esperi-mento consiste nel lancio di un dado e se chiamiamo successo l’uscita di unnumero maggiore di 2, abbiamo p = 2/3 e q = 1/3.

Si supponga di ripetere piu volte l’esperimento. Se le probabilita di suc-cesso e fallimento sono costanti, cioe non dipendono dai risultati precedenti,si parla di un processo bernoulliano. Esempi includono, oltre al lancio didadi e/o monete, le uscite di numeri alla roulette, lotterie, ecc. Supponiamodi ripetere un processo bernoulliano per n volte. Ci chiediamo qual e laprobabilita di ottenere esattamente k successi. Denotiamo tale probabilita


come P (n, k). Abbiamo

P (n, k) =

(

n

k

)

pkqn−k. (5.5)

Infatti, si possono scegliere i k successi (e, implicitamente, anche gli n − kfallimenti) in

(nk

)

modi, e la probabilita che si verifichino esattamente queisuccessi e pkqn−k, in quanto gli eventi sono indipendenti.

Infine la probabilita di avere almeno k successi in n tentativi e

n∑

i=k

(

n

i

)

piqn−i.

5.2 Variabili casuali e valor medio

Una variabile casuale X, definita su uno spazio di probabilita S, e unafunzione X : S 7→ R a valori reali. Per ogni numero reale v che la variabilepuo assumere, la probabilita che cio avvenga e indicata con

P (X = v)

ed e definita come P (X = v) := P (A) dove A ⊂ S e l’insieme dei puntia tali che X(a) = v. Ad esempio, consideriamo il lancio di 2 dadi e siaX la variabile casuale che denota il valore della somma dei due numeriusciti. Lo spazio S ha 36 eventi elementari (coppie del tipo (a, b) con a, b ∈{1, 2, . . . , 6}). Allora, si ha P (X = v) = 0 per v < 2 o v > 12. Inoltre,P (X = 2) = 1/36 = P (X = 12); P (X = 5) = 4/36, eccetera.

Il valor medio (o valore atteso) di una variabile casuale e definito come

E(X) :=∑

v

v · P (X = v). (5.6)

Ad esempio, nel caso del lancio dei due dadi si ha, per v ∈ 2, 3 . . . , 12,P (X = v) = min{v− 1, 13− v}/36 (si rifletta sul perche di questa formula),da cui segue

E(X) =1

36(2 ·1+3 ·2+4 ·3+5 ·4+6 ·5+7 ·6+8 ·5+9 ·4+10 ·3+11 ·2+12 ·1)

e quindi E(X) = 7.Dal punto di vista degli elementi di S, il valore medio puo essere anche

scritto comeE(X) :=

∑

a∈S

X(a) · P ({a}) (5.7)

5.2. VARIABILI CASUALI E VALOR MEDIO 55

e, nel caso in cui P ({a}) = p per ogni a, si ottiene E(X) := p∑

a∈S X(a).Per il valor medio vale la linearita: dati qualsiasi numeri α e β e variabili

casuali X e Y , si ha

E(αX + βY ) = αE(X) + βE(Y ). (5.8)

5.2.1 ♥ Ordinamento per inversione

Si consideri il seguente puzzle combinatorico. E data una permutazione qual-siasi e bisogna metterla in ordine crescente tramite una serie di operazionidette inversioni (reversals in inglese). Un’inversione consiste nel prendereun blocco di elementi consecutivi della permutazione, ed invertirne l’ordine.Ad esempio per ordinare la permutazione

3 5 1 4 7 8 9 6 2 10

si potrebbe procedere come segue:(3 5 1) 4 7 8 9 6 2 10

1 5 (3 4) 7 8 9 6 2 10

1 (5 4 3 7 8 9 6 2) 10

1 2 6 (9 8 7 3 4 5) 10

1 2 (6 5 4 3) 7 8 9 10

1 2 3 4 5 6 7 8 9 10

e la permutazione viene ordinata con 5 inversioni. Si noti che questoesempio non dimostra che e impossibile ordinare la permutazione con menodi 5 inversioni. Sia π la permutazione di partenza

π = (π1, π2, . . . , πn)

Indichiamo con d(π) il numero minimo di inversioni necessario e sufficienteper ordinare π. Tale numero e detto le distanza di inversione di π. Dall’e-sempio sopra, si ricava che d(3, 5, 1, 4, 7, 8, 9, 6, 2, 10) ≤ 5.

Il problema di determinare d(π) si chiama ordinamento per inversione

(sorting by reversals). Si tratta di un problema motivato soprattutto dal suoutilizzo nello studio dell’evoluzione di genomi da antenati comuni. Infatti,uno dei principali eventi evolutivi che possono mutare un genoma in unonuovo (ossia dare luogo ad una nuova specie o una sottospecie) e l’inversionedi un lungo pezzo di DNA all’interno di un cromosoma. Dopo un siffattoevento, i geni sono ancora gli stessi, ma si ribalta l’ordine dei geni contenutinel pezzo che si e invertito. Dopo milioni di anni, e numerosi eventi diquesto tipo, si possono presentare due genomi (ad esempio quello dell’uomoe quello del topo) che contengono gli stessi geni, ma in un ordine diverso.Supponendo per convenzione i geni siano numerati da 1 a n, che il loro


ordine nell’uomo sia (1, 2, . . . , n) mentre nel topo l’ordine sia dato da unapermutazione π, la minima distanza evolutiva per inversione fra uomo e topoe stimata dal numero d(π).

Analisi dei breakpoints

Il calcolo di d(π) risulta molto difficile e non esistono formule semplici egenerali per la soluzione di questo problema. Un parametro correlato a d(π)risulta molto piu facile da calcolare, e riguarda i breakpoints.

Per ragioni tecniche, cominciamo con estendere π in modo che includal’elemento 0 e n + 1 in posizione 0 e n + 1 ripettivamente, ossia ridefiniamoπ come

π := (π0 = 0, π1, π2, . . . , πn, πn+1 = n + 1)

I numeri 0 e n+1 non vengono mai coinvolti in nessuna inversione, ossiale inversioni possono solo coinvolgere le posizioni fra 1 e n. Un breakpoint

consiste in una coppia di elementi adiacenti in π che pero non sono adiacen-ti nella permutazione ordinata. Altrimenti detto, si ha un breakpoint allaposizione i |πi − πi−1| > 1. Evidenziamo i breakpoints nella permutazioneπ dell’esempio

0 ↑ 3 ↑ 5 ↑ 1 ↑ 4 ↑ 7 8 9 ↑ 6 ↑ 2 ↑ 10 11

Il numero di breakpoints si indica con b(π) e, come si e visto, e moltofacile da calcolare. In questo esempio b(π) = 8. Si noti che la permu-tazione ordinata (0, 1, . . . , n, n + 1) ha 0 breakpoints 1 per cui si puo vedereil problema dell’ordinamento per inversione come un processo che rimuovebreakpoints. Un’inversione puo rimuovere al piu 2 breakpoints (quelli defini-ti dagli estremi del blocco che viene invertito – all’interno del blocco o nellezone non a contatto con il blocco i breakpoint restano gli stessi) per cui sideduce che

d(π) ≥ db(π)

2e. (5.9)

Siccome il calcolo di b(π) e piu facile che quello di d(π), si e studiatol’andamento statistico di b(π) per dedurre qualcosa sulle statistiche di d(π).Ci occupiamo pertanto di determinare il numero atteso di breakpoints inuna permutazione casuale.

1Si spiega quindi il motivo dell’aggiunta degli elementi π0 = 0 e πn+1 = n + 1. Infatti,seza questi ultimi, sia la permutazione (1, 2, . . . , n) che la permutazione (n, n− 1, . . . , 2, 1)avrebbero 0 breakpoints, ma la seconda richiede ancora un’inversione per essere ordinata.

5.2. VARIABILI CASUALI E VALOR MEDIO 57

Teorema 9: Si denoti con X il numero di breakpoints in una permutazioneπ casuale (cioe una permutazione presa uniformemente fra le n! possibili).Allora

E(X) = n − 1. (5.10)

Dim: Per i = 0, . . . , n, sia Zi una variabile casuale che vale 1 se si verifical’evento “i numeri i e i+1 non sono adiacenti in π” e 0 altrimenti. Pertanto,X =

∑ni=0 Zi. Dalla linearita del valor medio, segue E(X) =

∑ni=0 E(Zi) =

∑ni=0 P (Zi = 1).

Calcoliamo prima E(Z0) and E(Zn) perche sono speciali, in quanto coin-volgono i numeri 0 e n + 1 che non possono essere spostati da nessun’in-versione. E(Z0) e la frazione di permutazioni che non cominciano per 1,ossia

n! − (n − 1)!

n!=

n − 1

n.

Analogamente, E(Zn) = (n − 1)/n e la frazione di permutazioni che nonterminano per n.

Per i = 1, . . . , n− 1, ci sono 2((n2

)− (n− 1))(n − 2)! permutazioni in cuii e i+1 sono separati. Infatti, si possono scegliere le posizioni per mettere ie i + 1 in

(n2

)

modi, di cui pero n − 1 scelte coinvolgono posizioni adiacenti.Inoltre ci sono 2 modi di riempire queste posizioni, ossia mettendo prima ie poi i + 1 o viceversa. Quindi, per 1 ≤ i ≤ n − 1 si ha

E(Zi) =2((n2

)− (n − 1))(n − 2)!

n!=

n − 2

n.

Dalla linearita del valor medio si ottiene

E(X) =n − 1

n+

n−1∑

i=1

n − 2

n+

n − 1

n= n − 1. (5.11)

♣

Concludiamo questa sezione con un risultato di cui non riportiamo ladimostrazione. Il risultato e piu adatto del precedente alle applicazioni delproblema alla genomica. Consideriamo infatti una permutazione ottenutadall’evoluzione, che agisce come un processo casuale. Partendo da un geno-ma (di una specie antenata), viene effettuata un’inversione casuale (una frale(n2

)

possibili, scelta in modo uniforme), ottenendo cosı un nuovo genoma.Il processo viene ripetuto k volte, fino ad ottenere il genoma finale, π.


Teorema 10: Sia Xk il numero di breakpoint in una permutazione ot-tenuta applicando k inversioni casuali alla permutazione ordinata. Allora

E(Xk) = (n − 1)

(

1 −(

n − 3

n − 1

)k)

. (5.12)

Si noti che limk→∞ E(Xk) = E(X), a conferma del fatto intuitivo cheapplicare un numero sufficientemente grande di inversioni casuali ad unapermutazione, produce come risultato una permutazione sostanzialmenterandom (ossia con distribuzione uniforme).

5.3 Generazione di strutture random

In questa sezione consideriamo il problema di generare un oggetto combi-natorio (quale un sottoinsieme, o una disposizione, ecc.) secondo una dis-tribuzione uniforme. Ossia, se esistono N di tali oggetti, la probabilita diselezionarne uno in particolare deve risultare 1/N . Nel descrivere gli algo-ritmi useremo uno pseudo-linguaggio di programmazione. Assumiamo chela procedura

rndint(a, b)

sia disponibile nel linguaggio e che, dati due numeri interi a e b, restituiscaun intero x, con a ≤ x ≤ b, casuale (ossia distribuito uniformeme fra a e b).

5.3.1 Insiemi

Dato l’insieme S = {1, 2, . . . , n}, consideriamo il problema di generare unsottoinsieme casuale A di S. Questo puo essere ottenuto lanciando in ariauna moneta n volte, e, ad ogni lancio i in cui esce “testa”, includendo i nelsottoinsieme casuale.

Algorithm 1 RandomSubset

1. A := ∅;2. for i := 1 to n do

3. if rndint(0,1) = 1 then

4. A := A ∪ {i};5. endfor

Per dimostrare che A e effettivamente casuale, consideriamo un qualsiasisottoinsieme B di S e facciamo vedere che la probabilita che A = B e 1/2n.

5.3. GENERAZIONE DI STRUTTURE RANDOM 59

Sia ad esempio B = {3, 5, 6} (per esercizio lo studente generalizzi l’esempioad un caso qualsiasi). Allora A = B se il lancio della moneta ha dato “testa”ai tentativi 3, 5 e 6, e “croce” ai rimanenti n − 3 tentativi. Siccome ognilancio e indipendente dagli altri, la probabilita che cio avvenga e

Prob(testa)3 × Prob(croce)n−3

che, essendo Prob(testa) = Prob(croce) = 1/2, e pari a 1/2n.

Consideriamo ora il problema di generare un sottoinsieme di una datacardinalita k prefissata. Analizziamo prima una soluzione errata. L’ideapotrebbe essere quella di procedere come nell’esempio precedente, ossia lan-ciando la moneta (virtuale) e interrompendo il processo non appena sianostate ottenute k “teste”. Esiste anche la possibilita che al termine di un ci-clo sugli n elementi non siano state ottenute k teste, nel qual caso bisogneraritentare l’intero processo una nuova volta:

Algorithm 2 Randomk-SubsetWrong

1. repeat

2. A := ∅;3. for i := 1 to n do

4. if rndint(0,1) = 1 then

5. A := A ∪ {i};6. if |A| = k then exit for loop7. endif;8. endfor;9. until |A| = k.

E facile riconoscere il problema dell’algoritmo 2: i sottoinsiemi generatinon seguono la distribuzione uniforme. Per accorgersene, basta considerareil caso k = 1 e chiedersi qual’e la probabilita di generare il sottoinsieme{n}. Questa probabilita e pari a 1/2n (e quindi bassissima), in quanto talesottoinsieme viene creato solo quando i primi n − 1 lanci della moneta for-niscono “croce” e l’ultimo fornisce “testa”. D’altro canto, la probabilita digenerare il sottoinsieme {1} e 1/2. Si vede quindi che questi insiemi nonsono generati con la stessa probabilita come invece dovrebbe avvenire. Nonsolo: entrambe le probabilita sono sbagliate, in quanto la probabilita di ognisiffatto sottoinsieme dovrebbe risultare pari a 1/n. Nella sezione 5.3.2 de-scriveremo il modo corretto di generare un k-sottoinsieme con distribuzioneuniforme.


Esercizio 5.3. Si consideri un numero in base 2 di n bit come rappresen-tante un insieme (l’insieme delle posizioni in cui i bit valgono “1”). Si discutapertanto un modo di generare sottoinsiemi casuali di {1, . . . , n} tramite lagenerazione di numeri casuali da interpretarsi poi in base 2.

5.3.2 Permutazioni e disposizioni

Consideriamo il problema di generare una k-disposizione, ossia un ordina-mento di k numeri diversi presi fra 1 e n, in modo casuale. L’idea e quella dicominciare generando un numero casuale d1, compreso tra 1 e n. Poi, si gen-era un numero casuale d2, compreso tra 1 e n, ma diverso da d1. Al genericopasso i-esimo, si genera un numero di con 1 ≤ di ≤ n e di 6= d1, d2, . . . , di−1.Per essere sicuri di non generare un numero gia generato in precedenza,utilizziamo un vettore v[] e un contatore left, facendo in modo che gli ele-menti v[1], v[2],. . . , v[left] siano, in ogni momento, tutti e soli i numeriche non sono ancora stati utilizzati, e quindi sono disponibili. Chiamiamopoi p[1,...,k] il vettore che costruiamo, e che, al termine, conterra ladisposizione casuale.

Algorithm 3 Randomk-Perm

1. for i:=1 to n do v[i] :=i; /* inizializzazione */2. left:= n;3. for i:=1 to k do

4. pos:= rndint( 1, left );5. p[i]:=v[pos];6. v[pos]:=v[left];7. left:= left-1;8. endfor

Al passo 4 viene generata la posizione di un elemento di v[] compresotra 1 e left. Siccome questi elementi sono tutti e soli i numeri disponibili,viene in pratica generato un numero casuale (vale a dire v[pos]) tra quellidisponibili. Tale numero viene copiato in p[] al passo 5. Ai passi 6 e 7 sifa poi in modo da mantenere in v[1..left] sempre e soli i numeri ancoradisponibili, sovrascrivendo v[pos] (gia usato) con v[left] e decrementandoleft.

Per quel che riguarda la distribuzione di probabilita, consideriamo unaspecifica disposizione, ad esempio (b1, b2, . . . , bk) e chiediamoci qual e laprobabilita di generarla. Si avra p[1] = b1 con probabilita 1/n. Una volta

5.4. ENUMERAZIONE COMPLETA 61

posto p[1] := b1, la probabilita che p[2] = b2 e 1/(n−1) in quanto p[2] vienescelto fra n − 1 elementi, che comprendono b2. Continuando, la probabilitache p[3] = b3, dati p[1] = b1 e p[2] = b2 e 1/(n − 2). Dal prodotto di questeprobabilita si ottiene

Prob(generare (b1, b2, . . . , bk)) =1

n× 1

n − 1× · · · × 1

n − k + 1=

1

D(n, k)

e quindi la distribuzione e uniforme.

Rispondiamo ora al quesito su come generare un sottoinsieme di cardi-nalita k in maniera uniforme. Per fare cio basta utilizzare l’algoritmo 3, econsiderare l’insieme dei k elementi nella disposizione generata (ossia, pren-dere la disposizione, ma ignorando l’ordine). Ad esempio, se la disposizionecasuale generata risulta (3, 1, 5), questa verra interpretata come l’insieme{1, 3, 5}. Lo stesso insieme si avrebbe anche nel caso fosse stata generata ladisposizione (5, 3, 1), eccetera. Per vedere che gli insiemi vengono generaticon distribuzione uniforme, chiediamoci qual e la probabilita di generareuno specifico k-insieme {b1, b2, . . . , bk}. Questo insieme viene indotto dallek! permutazioni possibili dei suoi elementi, ossia da k! disposizioni, ognunadi probabilita 1/D(n, k). Otteniamo che

Prob(generare {b1, b2, . . . , bk}) = k! × 1

D(n, k)=

1(nk

)

e quindi la distribuzione e uniforme.

Infine, consideriamo il problema di generare una permutazione casuale,in maniera uniforme. Banalmente, essendo ogni permutazione anche unan-disposizione, bastere utilizzare l’algoritmo 3 con k = n.

5.4 Enumerazione completa

Consideriamo ora il problema di enumerare tutte le strutture combinatorie diun certo tipo (ad esempio sottoinsiemi e permutazioni). Per questo problemaesistono tipicamente due soluzioni, la soluzione ricorsiva e la soluzione itera-

tiva. La soluzione ricorsiva genera tutte le strutture di dimensione n a partireda tutte le strutture di dimensione n−1. Se realizzato con un programma suun calcolatore, questo modo di procedere implica la necessita di una enormequantita di memoria, in quanto tutte le strutture devono essere memorizzatecontemporaneamente. Quindi, servira una memoria proporzionale a 2n per


contenere tutti i sottoinsiemi di un insieme e proporzionale a n! per con-tenere tutte le permutazioni degli elementi. Anche per valori modesti di n,queste quantita risultano proibitive.

Nella soluzione iterativa, invece, le strutture vengono implicitamente or-dinate, sicche ne esiste una prima e una ultima. Se siamo in grado, datal’i–esima struttura dell’ordine, di creare a partire da essa la (i + 1)-esima,la i-esima puo poi essere cancellata. Pertanto, la memoria necessaria e soloquella che basta per contenere 2 strutture (quella corrente e la successiva) equindi proporzionale a n.

5.4.1 Generare tutti i sottoinsiemi

Sia S = {1, . . . , n}. Vogliamo elencare tutti i suoi sottoinsiemi. Consideri-amo prima la soluzione ricorsiva:

1. Si generino tutti i sottoinsiemi di {1, . . . , n − 1}. Sia A l’insieme diquesti sottoinsiemi.

2. Si crei un insieme A′ di sottoinsiemi, ottenuti aggiungendo l’elementon a ogni insieme di A (ossia, A′ := {B ∪ {n} |B ∈ A}).

3. I sottoinsiemi di S sono allora dati da A ∪ A′.

Il passo 1 puo essere eseguito ricorsivamente, e corrisponde al passaggioinduttivo nelle dimostrazioni per induzione. Se n−1 > 0 il passo implica chesi deve utilizzare lo stesso procedimento per calcolare A. Se invece n−1 = 0,allora basta porre A = ∅.

Consideriamo ora la soluzione iterativa. Si identifichi un sottoinsieme Bdi S con una sequenza di valori booleani:

(b1, b2, . . . , bn)

dove bi = VERO se i ∈ B e bi = FALSO altrimenti.Definiamo bα = (FALSO, FALSO, . . . , FALSO) come il primo sottoinsieme, e

bω = (VERO, VERO, . . . , VERO) come l’ultimo. Dato un sottoinsieme (b1, b2, . . . , bn)che non sia l’ultimo, per calcolarne il successivo, chiamiamolo (b′1, b

′2, . . . , b

′n),

si proceda come segue:

1. Si trovi 1 ≤ j ≤ n tale che bj = FALSO e bi = VERO per i = j + 1, . . . , n.

2. Si ponga b′k := bk per k = 1, . . . , j − 1 e b′k := ¬bk per k = j, . . . , n.

Esercizio 5.4. Si rifletta sul fatto che il procedimento iterativo descrittocorrisponde a generare i numeri da 0 a 2n − 1 in base 2.

5.4. ENUMERAZIONE COMPLETA 63

5.4.2 Generare tutte le permutazioni

Sia S = {1, . . . , n}. Vogliamo elencare tutte le permutazioni dei suoi ele-menti. Consideriamo prima la soluzione ricorsiva:

1. Si generino tutte le permutazioni di {1, . . . , n − 1}. Sia A l’insieme diqueste permutazioni.

2. Per ogni permutazione π = (π1, π2, . . . , πn−1) ∈ A (una permutazionedei numeri {1, . . . , n−1}) si crei un insieme A(π), contenente n permu-tazioni dei numeri {1, . . . , n}, in questo modo: si introduce n in tuttele posizioni possibili fra due elementi di π, ossia A(π) =

{(n, π1, π2, . . . , πn), (π1, n, π2, . . . , πn), (π1, π2, . . . , n, πn), (π1, π2, . . . , πn, n)}

3. Tutte le permutazioni di S sono allora date dall’unione degli A(π) pertutti i π ∈ A.

Il passo 1 puo essere eseguito ricorsivamente. Se n − 1 > 1 il passoimplica che si deve utilizzare lo stesso procedimento per calcolare A. Seinvece n − 1 = 1, allora basta porre A = {(1)}.

Consideriamo ora la soluzione iterativa. Questa soluzione e basata sul-l’ordine alfabetico. Se ad esempio S fosse {A,B,C}, le permutazioni inordine alfabetico sarebbero

{(A,B,C), (A,B,C), (B,A,C), (B,C,A), (C, A,B), (C, B,A)}.

Siccome le permutazioni riguardano in generale oggetti generici (nel nos-tro caso i numeri 1, . . . , n) l’ordine alfabetico non e necessariamente definito,ma al suo posto abbiamo l’ordine lessicografico. Quest’ordine si basa sul fat-to che i singoli oggetti siano a due a due confrontabili (e i numeri, ad esempio,lo sono). Si dice che una sequenza σ = (σ1, σ2, . . . , σs) precede nell’ordinelessicografico una sequenza τ = (τ1, τ2, . . . , τr), con σ 6= τ , se esiste 1 ≤ j ≤ stale che σi = τi per 1 ≤ i < j e σj < τj. In caso contrario, τ precede σ.

Ad esempio (3, 5, 1, 6, 4) precede (3, 5, 11, 0) e (B,C, F ) precede (B,F,A,A).Le permutazioni di {1, 2, 3}, in ordine lessicografico sono

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Siano πα = (1, 2, . . . , n) la prima permutazione, e πω = (n, n−1, . . . , 2, 1)l’ultima. Data una permutazione (π1, π2, . . . , πn) che non sia l’ultima, percalcolarne la successiva, chiamiamola (π ′

1, π′2, . . . , π

′n), si proceda come segue:


1. Si trovi 1 ≤ r ≤ n tale che πr+1 > πr+2 > · · · > πn e πr < πr+1

(i.e., si determini la sequenza massimale decrescente al termine dellapermutazione)

2. Si determini un indice l, con r+1 ≤ l ≤ n, tale che πl > πr e πl+1 < πr

(i.e., πl e il piu piccolo numero maggiore di πr all’interno della sequenzadecrescente)

3. Si ponga π′k := πk per k = 1, . . . , r−1 e π′

r := πl. Per i = n, n−1, . . . , r+1, con i 6= l, si ponga π′

r+1+(n−i) := πi. Infine, si ponga π′l := πr (in

pratica, si scambiano πr e πl e si riordinano tutti gli elementi dal postor + 1 in poi).

Ad esempio, la permutazione immediatamente successiva a

(2, 9, 5, 10, 4, 8, 7, 6, 3, 1)

e(2, 9, 5, 10, 6, 1, 3, 4, 7, 8).

In questo esempio, r = 5 (πr = 4) e l = 8 (πl = 6).

Esercizio 5.5. Si dimostri formalmente che π ′ ottenuta con il procedi-mento descritto e la permutazine che immediatamente segue π nell’ordinelessicografico, ossia che non esiste una permutazione σ che segue π maprecede π′.

Capitolo 6

Teoria dei grafi

Un grafo e un oggetto matematico che serve a rappresentare una relazionebinaria su un insieme di elementi. Tale relazione puo essere simmetrica(dando origine a un grafo non orientato), o asimmetrica (dando origine aun grafo orientato). Come esempio del primo caso, si pensi alla relazione“i ha un genitore in comune con j”, definita su un insieme di persone,oppure “i e amico di j” (anche se quest’ultima, piu realisticamente, non enecessariamente una relazione simmetrica). Nel secondo caso, gli elementipossono essere alcuni incroci di una citta, e la relazione del tipo “esisteuna strada cha va dall’incrocio a all’incrocio b”. Oppure, su un insiemedi persone, la relazione “q e figlio di p”. La Teoria dei Grafi e la scienzache studia i grafi e loro proprieta fondamentali. Grazie ad essa, esistonoalgoritmi e teoremi che ci permettono di rispondere a domande quali “esisteun percorso (sequenza di vie) per andare da un incrocio x a un incrocio y inuna citta senza mai violare un senso unico?” o “la persona x e un antenatodella persona y?” o “qual e il gruppo piu numeroso di persone che sono tuttiamici fra loro?” ed altre simili.

6.1 Grafi Non Orientati

Un grafo non orientato (o semplicemente grafo, qualora non ci sia pericolodi confusione) e definito da una coppia G = (V,E) di insiemi finiti, dove V edetto l’insieme dei vertici (o nodi) e E l’insieme dei lati (o archi) Le inizialisono dovute ai termini inglesi Vertex e Edge. Un lato e una coppia nonordinata di vertici, che indicheremo con ij (= ji), dove i e j appartengonoa V e i 6= j.

Due vertici i, j ∈ V si dicono adiacenti se il lato e = ij appartiene ad E.

65

66 CAPITOLO 6. TEORIA DEI GRAFI

E

F

I J

H

A

B D

C

G

abc

de

fg

h

i

j

k

l

Figura 6.1: Il grafo G∗, con 10 vertici e 12 lati.

In tal caso si dice che e e incidente in i e in j (o che e collega i e j), e questiultimi si dicono anche gli estremi di e. Due lati si dicono adiacenti se sonoincidenti su un medesimo vertice.

Il grado di un vertice v ∈ G, denotato con dG(v) (o, piu semplicementecon d(v) qualora non ci sia pericolo di confusione) e il numero di archiincidenti in v. Un grafo si dice regolare se d(i) = d(j) per ogni i, j ∈ V . Inparticolare, il grafo si dice k-regolare se d(i) = d(j) = k per ogni i, j ∈ V .Un vertice di grado 0 si dice isolato. In figura 6.1 vediamo rappresentato ungrafo che chiameremo G∗ e che useremo nel resto del capitolo per illustrarealcuni dei concetti introdotti. In G∗ il vertice F e isolato, il vertice E hagrado 4, e i lati a e b sono adiacenti.

La matrice di incidenza nodi-archi di un grafo e una matrice M con |V |righe e |E| colonne. Ogni riga v corrisponde a un vertice v ∈ V e ognicolonna e = vw corrisponde a un lato vw ∈ E. Il generico elemento Mve

della matrice vale 1 se e ∈ E e incidente in v ∈ V , altrimenti vale 0.La matrice di incidenza nodi-archi del grafo G∗ e visualizzata in figura

6.2.Si noti che nella matrice M ci sono esattamente due “1” in ogni colonna,

e che la somma degli elementi di una qualsiasi riga v e pari a d(v). Abbiamoil seguente

Teorema 11: Sia G = (V,E). Allora∑

v∈V d(v) = 2|E|.

Dim: Sommando gli elementi di M riga per riga, otteniamo∑

v∈V d(v).Sommandoli colonna per colonna, otteniamo |E| × 2. Siccome i due modidevono dare lo stesso risultato, il teorema e dimostrato. ♣

6.1. GRAFI NON ORIENTATI 67

a b c d e f g h i j k l

A 1 0 1 1 0 1 0 0 0 0 0 0B 0 0 0 1 1 0 0 1 0 0 0 0C 1 1 0 0 0 0 0 0 0 0 0 0D 0 0 0 0 1 1 1 0 0 0 0 0E 0 1 1 0 0 0 1 1 0 0 0 0F 0 0 0 0 0 0 0 0 0 0 0 0G 0 0 0 0 0 0 0 0 1 1 0 1H 0 0 0 0 0 0 0 0 1 0 0 0I 0 0 0 0 0 0 0 0 0 1 1 0J 0 0 0 0 0 0 0 0 0 0 1 1

Figura 6.2: La matrice di incidenza nodi-archi di G∗.

Quindi, in ogni grafo, la somma dei gradi dei vertici e un numero pari.Da questo fatto, consegue un importante risultato:

Teorema 12: In ogni grafo c’e un numero pari di vertici di grado dispari.

Dim: Sia D ⊂ V l’insieme dei vertici di grado dispari e P = V − Dl’insieme dei vertici di grado pari. Abbiamo

∑

v

d(v) =∑

v∈D

d(v) +∑

v∈P

d(v) = 2|E|

da cui, essendo sia∑

v∈P d(v) che 2|E| dei numeri pari, consegue che∑

v∈D d(v)deve anch’esso essere un numero pari. Ma allora |D| e pari, in quantosommando una quantita dispari di numeri dispari, il risultato e un numerodispari. ♣

Una sequenza (d1, . . . , dn) di numeri si dice grafica se esiste un grafo Gdi n vertici tale che la sequenza corrisponde ai gradi dei vertici di G. Nontutte le sequenze sono grafiche, come e facile vedere. Ad esempio

• una sequenza grafica non puo contenere alcun numero ≥ n

• se una sequenza contiene sia il numero 0 che il numero n − 1, nonpuo essere grafica, perche implicherebbe che esiste un nodo che non eadiacente ad alcun altro nodo, ed uno che e adiacente a tutti gli altri.

• la sequenza deve contenere un numero pari di numeri dispari. Ad es.la sequenza (2, 3, 0, 1, 1) non e grafica


• ecc.

Esercizio 6.1. Dimostrare che, dato un gruppo di n persone, ve ne sonosempre almeno due con lo stesso numero di amici (supponendo che l’amiciziasia una relazione simmetrica).

Esercizio 6.2. Siano dati n arbitrari punti nel piano p1, . . . , pn. Dimostrareche esistono al piu 3n coppie di punti {pi, pj} tali che la distanza fra pi e pj

e esattamente 1 cm.

Due grafi G = (V,E) e G′ = (V ′, E′) si dicono isomorfi se esiste unafunzione f : V 7→ V ′ tale che f(v)f(w) ∈ E ′ se e solo se vw ∈ E. In pratica,due grafi sono isomorfi se e possibile rinominare i nodi del primo usando inomi dei nodi del secondo, e ottenere esattamente il secondo grafo. Si notiche in un grafo non e importante il modo in cui il grafo e disegnato, ma soloquali sono le relazioni tra i nodi.

Dato un grafo G = (V,E), un grafo G′ = (V ′, E′) si dice sottografo diG se V ′ ⊆ V e E′ ⊆ E. Se inoltre V ′ = V , allora G′ si dice un sottografodi supporto (spanning) di G. Dato un sottoinsieme di vertici S ⊆ V , si dicesottografo indotto da S, indicato con G[S] il grafo che ha S come insieme divertici e come lati ha tutti i lati ij ∈ E tali che i ∈ S e j ∈ S.

Un grafo si dice completo se ogni coppia di vertici e collegata da un lato.Il generico grafo completo di n nodi (unico, a meno di isomorfismi) si indicacon Kn. In Kn ci sono n vertici e n(n−1)/2 lati. Un sottografo completo diun grafo, si chiama anche una clique. Se in un grafo i lati indicano relazionidi compatibilita fra gli elementi, una clique e un insieme di elementi tuttimutualmente compatibili. Ad esempio, il sottografo indotto da {G, I, J} inG∗ e una clique di 3 nodi, detta anche un triangolo.

Dato un grafo G = (V,E) si definisce grafo complementare di G il grafoG = (V,E) definito da E = {vw|vw /∈ E}. Se G e un grafo completo, il suocomplementare e un grafo di soli nodi isolati. Un insieme di vertici S ⊆ Ve detto un insieme indipendente o stabile, se ij /∈ E per ogni i, j ∈ S. Sinoti che S e un insieme indipendente se e solo se il grafo indotto da S in Ge una clique.

Esercizio 6.3. Dato un insieme V di 20 elementi, quanti grafi diversi(non necessariamente non isomorfi) esistono, che abbiano V come insiemedi vertici?

6.2. CAMMINI E CICLI 69

6.2 Cammini e cicli

Un cammino dal vertice v0 al vertice vk in un grafo G = (V,E) e unasequenza di vertici v0, v1, . . . , vk−1, vk tali che, per 0 ≤ i ≤ k − 1, si havivi+1 ∈ E. Si dice anche che il cammino usa (o attraversa) i k lati vivi+1,per 0 ≤ i ≤ k − 1, e che visita (o attraversa) i k + 1 vertici v0, . . . , vk. Sidice anche che un tale cammino ha lunghezza k (cioe la lunghezza e parial numero di lati usati) e che connette (o collega) v0 e vk. Un cammino sidice elementare se non usa mai lo stesso arco piu di una volta, e semplice senon visita mai lo stesso vertice piu di una volta. Nell’esempio di figura 6.1i seguenti cammini collegano C ad A:

P1 : C,E,D,B,E,D,A

P2 : C,E,B,D,E,A

P3 : C,E,D,A

P1 non e un cammino elementare. P2 e elementare ma non semplice. P3

e un cammino semplice. Nel seguito, qualora non specificato diversamente,per “cammino” intenderemo sempre, implicitamente, cammino semplice.

Il diametro di un grafo e la lunghezza massima di un cammino fra unaqualsiasi coppia di suoi nodi. In G∗ il diametro e 4 ed e realizzato, adesempio, dalla coppia di nodi B ed E, tramite il cammino B,D,A,C,E (si notiche il diametro puo essere realizzato in piu modi. Ad esempio, il camminoC,A,D,E,B).

Un ciclo, o circuito, e un cammino chiuso, ossia in cui v0 = vk. Adesempio, A,B,D,E,C,A e G,I,J,G sono circuiti in G∗. Un grafo G si diceaciclico se non contiene alcun ciclo. Un circuito semplice (i.e., senza verticiripetuti – a parte il primo e l’ultimo) che attraversa tutti i nodi di G si chiamacircuito hamiltoniano. Un circuito elementare (i.e., senza lati ripetuti) cheattraversa tutti i lati di G si chiama circuito euleriano. Circuiti hamiltonianied euleriani saranno trattati nel prossimo paragrafo.

Un grafo G si dice connesso se ogni coppia di vertici e collegata da (al-meno) un cammino in G. Dato un grafo G = (V,E), i vertici possono esserepartizionati in k sottoinsiemi V1, . . . , Vk tali che G[Vi] e un grafo connessoper ogni i, mentre non lo e il grafo G[Vi ∪{v}] per alcun v /∈ Vi. I sottografiG[Vi] si chiamano le componenti connesse di G. Un grafo e connesso se e solose ha un’unica componente connessa. Il grafo G∗ ha 3 componenti connesse.

Un insieme E ′ ⊆ E di lati si dice un taglio se la sua rimozione da Eaumenta il numero di componenti connesse. In particolare, a partire da uninsieme S di vertici, S 6= E, ∅, si puo definire il seguente insieme δ(S) di lati


δ(S) := {ij : (i ∈ S, j ∈ V − S) ∨ (i ∈ V − S, j ∈ S)}

che risulta un taglio non appena esista almeno una coppia di nodi (unoin S e l’altro in V − S) collegati in G (in caso contrario, δ(S) = ∅).Esercizio 6.4. Dimostrare che in un grafo G aciclico, esiste sempre almenoun vertice v con dG(v) ≤ 1.

Esercizio 6.5. Dimostrare che, dato un grafo G = (V,E), si ha che {e} eun taglio per ogni e ∈ E se e solo se G e aciclico.

Esercizio 6.6. Dimostrare che un grafo con n nodi e (n − 1)(n − 2)/2 + 1lati e necessariamente connesso.

Esercizio 6.7. Sia G = (V,E) un grafo con esattamente due vertici, a e bdi grado dispari. Sia G′ il grafo ottenuto da G aggiungendo a V un nodoc /∈ V e ad E i due lati ac e bc. Dimostrare che G e connesso se e solo se G′

e connesso.

6.3 Grafi bipartiti, hamiltoniani e euleriani

Per introdurre i concetti di questa sezione, ci serviremo di un quesito diintelligenza, stile “Settimana Enigmistica”. Un gruppo di amici si trovanoper una cena a casa di uno di loro. Le relazioni di amicizia fra gli stes-si sono rappresentate, in modo ovvio, dal grafo in Figura 6.3. Il padronedi casa desidera farli sedere in modo tale che ognuno abbia come due im-mediati commensali, a destra e sinistra, degli amici. E possibile una taledisposizione? Un modo per verificarlo, sarebbe quello di andare per tenta-tivi, provando tutte le possibili permutazioni circolari (sono (n − 1)!/2 pern elementi) e vedendo se ce ne e una del tipo desiderato. Abbiamo gia vistoin sezione 1.7 come questa sia, in generale, una strategia da evitare. Bastinotare che, per soli 9 elementi, si dovrebbero esaminare potenzialmente ben20160 disposizioni!

Dato un grafo G, una permutazione circolare dei vertici in cui ogni nodoe preceduto e seguito da un nodo che gli e adiacente in G, e detta circuito (ociclo) hamiltoniano. Detto altrimenti, un ciclo hamiltoniano e un ciclo chepassa per ogni nodo, una e una sola volta. Un grafo si dice hamiltoniano secontiene un circuito hamiltoniano. Quindi, il nostro problema, corrispondea verificare se il grafo di Figura 6.3 e hamiltoniano. Questo problema e un

6.3. GRAFI BIPARTITI, HAMILTONIANI E EULERIANI 71

Mario

Anna

Tania

Carlo Gianni

Luigi

CristinaFranca

Silvia

Figura 6.3: Un gruppo di amici invitati a cena

problema che puo risultare molto difficile, e per il quale non esistono con-dizioni necessarie e sufficienti che siano facili da verificare. Da un punto divista algoritmico, il problema e dei piu difficili in assoluto, e non sono noteprocedure piu efficienti che –implicitamente o esplicitamente– provare tuttele possibilita. Nel nostro esempio pero (a parte la piccola dimensione delproblema) possiamo sfruttare una caratteristica del problema per rispondereimmediatamente che no, non ci sono soluzioni possibili. Infatti, si noti cheogni persona ha come amici solo persone del sesso opposto. Quindi, essendo-ci 5 femmine, se ogni femmina avesse alla sua destra un maschio, dovrebberoesserci esattamente 5 maschi (piu in generale, a k femmine dovrebbero cor-rispondere k maschi, dando, in totale, un numero pari pari di persone). Maci sono 9 invitati e percio una tale disposizione e impossibile.

Un grafo in cui i nodi possono essere ripartiti in due insiemi, V1 e V2

tale che ogni arco collega un estremo in V1 e uno in V2 si dice bipartito.In figura 6.4(a) si e ridisegnato il grafo iniziale, mettendo in evidenza labi-partizione. Il ragionamento di poco fa si ritrova in questo teorema, checaratterizza i grafi bipartiti:

Teorema 13: G e un grafo bipartito se e solo se ogni ciclo in G ha unnumero pari di nodi.

Dim: La necessita e molto semplice: Un qualsiasi ciclo che parta, adesempio, da un nodo in V1, deve alternare nodi di V1 e V2 e terminare in un


Gianni

Mario

Luigi

CarloSilvia

Franca

Tania

Anna

Cristina

K 32

K 22

(a)

(b)

Figura 6.4: (a) Un grafo bipartito. (b) Grafi bipartiti completi

nodo di V1. Quindi, deve attraversare un numero pari di lati, o finirebbe inun nodo di V2.

Per la sufficienza, ragioniamo cosı. Intanto, supponiamo il grafo connes-so (in caso contrario, si ripeta questo procedimento sulle varie componenticonnesse). Si fissi un nodo v, e si definisca V1 come l’insieme dei nodi peri quali esiste un cammino di lunghezza pari da v, e V2 = V − V1. Se, perassurdo, esistesse un arco ij con i e j entrambi in V1 (o in V2), allora cisarebbe anche un un ciclo dispari, contenuto nell’unione del cammino da va i col cammino da v a j e con l’arco ij. Siccome abbiamo supposto che nonci siano cicli dispari, V1 e V2 sono una partizione di V . ♣

Un grafo bipartito si denota anche con G = (V1, V2, E). Un grafo si dicebipartito completo se e tale che ij ∈ E per ogni i ∈ V1 e j ∈ V2. Un talegrafo si indica anche (a meno di isomorfismi) con Kn,m (dove n = |V1| em = |V2|).

Un corollario del teorema 13 e: un grafo bipartito con un numero disparidi nodi non puo essere hamiltoniano. Siccome esiste un modo molto efficienteper determinare se un grafo e bipartito, si e potuto risolvere il problemainiziale in modo molto piu efficiente dell’enumerazione completa di tutte ledisposizioni. Si noti pero che la condizione di essere bipartito con n disparie solo una condizione sufficiente, e molto debole, per verificare che un grafonon e hamiltoniano.


♥ Esempio. Il processo detto sequenziamento del genoma consiste in (1)replicare (clonare) il DNA in oggetto in molte copie (almeno una decina)(2) spezzare, casualmente, ogni copia in frammenti di circa 1000 basi l’uno(3) con un’apposita macchina (detta sequenziatore) ricavare la sequenzadi basi di ognuno di questi frammenti (4) con un computer, determinarela sovrapposizione dei frammenti in modo da poter ricostruire la sequenzaoriginale, s.

Al termine del processo, si ha una sequenza s ricostruita, che contiene lasequenza fi di ogni frammento i. Inoltre, ogni frammento ha anche associ-ata una posizione pi, che specifica il suo inizio all’interno della sequenza s.Uno dei maggiori problemi in questo processo e dato dal fatto che di ognicromosoma esistono, in realta due copie (una paterna e una maternza) equindi il processo dovrebbe ricostruire non una, ma due sequenze (sp e sm)e per ogni frammento, oltre alla posizione d’inizio, dovrebbe anche deter-minare l’appartenenza ai (con, ad esempio, ai = 1 se il frammento provienedalla copia paterna e a0 = 1 se il frammento proviene dalla copia mater-na). Sia F l’insieme di tutti i frammenti. Dati due frammenti i e j consovrapposizione non nulla (ossia tale che pi ≤ pj < pi + lungh(fi), diciamoche i due frammenti sono in conflitto se, nelle posizioni coperte da entram-bi, esiste almeno una posizione k tale che il nucleotide fi[k] e diverso dalnucleotide fj[k]. Chiaramente, due tali frammenti non possono provenireentrambi dalla copia paterna o dalla copia materna. Sia E l’insieme dellecoppie di frammenti in conflitto. Allora, il grafo G = (F,E) deve essereun grafo bipartito (se cosı non fosse, vuol dire che ci sono stati errori disequenziamento e/o di piazzamento dei frammenti). Se G e bipartito, i nodiF possono partizionarsi in nodi Fp (provenienti dalla copia paterna) e Fm,provenienti dalla copia materna. �

Un grafo si dice planare se puo essere disegnato in modo che due archinon si incrocino mai in alcun punto. Un grafo G′ si dice un minore di G seG′ puo essere ottenuto da G tramite la seguente operazione:

• Contrazione di un arco: Si rimuove un arco e = ij (inclusi i vertici i ej) e al suo posto si inserisce un nuovo nodo, e′. Ogni lato che incidevain i o in j diventa ora un lato che incide in e′ (si cancellano eventualilati duplicati).

Abbiamo il seguente teorema, la cui dimostrazione e troppo complessaper essere riportata qui:

Teorema 14: Un grafo G e planare se e solo se non ha ne K5 ne K3,3 frai suoi minori.


Analogamente al problema di determinare se un grafo abbia o meno uncircuito che attraversa tutti i vertici una e una sola volta, possiamo chieder-ci se esista un circuito che attraversi tutti i lati una e una sola volta. Untale circuito si dice euleriano ed un grafo che possiede un circuito euleri-ano si dice grafo euleriano. Il nome deriva da quello di Eulero, il famosomatematico che puo considerarsi il padre della teoria dei grafi. La teoriadei grafi e infatti nata, almeno storicamente, con il problema dei ponti dellacitta di Konisberg: ci si chiedeva se fosse possibile partire da un punto dellacitta, attraversare i suoi 7 ponti una e una sola volta, e ritornare al puntodi partenza. Eulero dimostro come questo non fosse possibile, e diede con-dizioni necessarie e sufficienti all’esistenza di un circuito del tipo desideratonel caso generale.

Teorema 15: Un grafo G = (V,E) connesso e euleriano se e solo se d(v)e pari per ogni v ∈ V .

Dim: Che la condizione sia necessaria e banale. Sia C un circuito euleri-ano. Seguendo C, rimuoviamo gli archi dal grafo. Ogni volta che entriamoin un nodo, e poi ne usciamo, diminuiamo di 2 il grado del nodo. Alla fineil grado di ogni nodo deve essere 0, e quindi, all’inizio, doveva essere unnumero pari.

Per la sufficienza, si consideri il procedimento descritto nell’algoritmo6.3. L’algoritmo costruisce una sequenza di lati α0, α1, . . . , αm che definis-cono un circuito euleriano. Al passo 4, un lato, non appena utilizzato, vienerimosso dal grafo. E importante il fatto che al passo 3 non si utilizzi mai unlato la cui rimozione disconnetterebbe il grafo, a meno che questo non siaassolutamente necessario. Infatti, in caso contrario, si creerebbero due com-ponenti connesse, il circuito proseguirebbe su una di queste e non avrebbepiu modo di tornare sull’altra.

Per dimostrare la correttezza dell’algoritmo, facciamo vedere che tuttigli archi vengono rimossi. Infatti, si supponga che cio non avvenga. Questoe possibile solo se ad un certo punto il nodo corrente vi e isolato ma c’ealmeno un arco uw da qualche parte del grafo. Siccome all’inizio il grafo eraconnesso, c’e stata un’iterazione tale che prima dell’iterazione i nodi vi e uerano connessi (da un cammino P = vi, . . . , u) mentre dopo non lo eranopiu. Quindi, l’iterazione ha rimosso un arco di P creando una componenteconnessa contenente vi, sulla quale ha proseguito, ed un’altra contenente ued w. Ma questo e vietato dal passo 3 (l’unica componente connessa che puoessere abbandonata per proseguire su un’altra e un nodo isolato, qualora siverifichi il caso 3’).


Figura 6.5: Quanti tratti sono necessari?

Algorithm 4 Euler

1. Si scelga un nodo v0 ∈ V e sia i := 0;2. while vi non e un nodo isolato do

3. Si scelga un vertice vi+1 tale che il lato vivi+1

non sia un taglio in G;3’. Se tutti i lati uscenti da vi sono tagli, si scelga

vi+1 arbitrariamente tra i nodi adiacenti a vi.4. Si ponga αi := vivi+1 e E := E − αi;5. i := i + 1;2. endwhile

♣Un cammino euleriano e un cammino che attraversa tutti gli archi, una

e una sola volta. Dal teorema 15 segue il

Corollario 16: Un grafo connesso ha un cammino euleriano se e solo seha al piu due vertici di grado dispari.

Infatti, se non ci sono vertici di grado dispari il grafo e euleriano e quindic’e un circuito (che e anche un cammino) euleriano. Altrimenti, detti a eb i vertici di grado dispari, l’algoritmo precedente inizializzato con v0 = adetermina un cammino euleriano da a a b. Si noti che il famoso giocodi disegnare una certa figura geometrica senza mai staccare la penna dalfoglio ne ripassare due volte su un stessa linea puo essere interpretato comeil problema di determinare se un certo grafo ha un cammino euleriano omeno.


Esercizio 6.8. Quante volte, come minimo, bisogna staccare la penna dalfoglio per disegnare (senza mai passare due volte su una stessa linea) lafigura 6.5?

Esercizio 6.9. Sia V = {1, 2, . . . , 20} e G = (V,E) un grafo in cui Ee definito dalle regole seguenti. Si dica, per ogni caso, se G e connesso,bipartito, euleriano, hamiltoniano:

1. ab ∈ E se a + b e pari.

2. ab ∈ E se a + b e dispari.

3. ab ∈ E se a × b e dispari.

4. ab ∈ E se a × b e dispari.

5. ab ∈ E se a × b e un quadrato.

6. ab ∈ E se a − b e un multiplo 3.

6.4 Alberi

Un albero e un grafo

1. aciclico

2. connesso.

Un generico grafo aciclico si chiama anche foresta, perche ogni sua com-ponente connessa e un albero.

L’albero e il grafo minimale (rispetto al numero di lati) necessario esufficiente per connettere un insieme di nodi. Infatti, in un albero l’aggiuntadi un qualsiasi lato non aumenta il numero di coppie di nodi connesse, mentresi puo dimostrare che la rimozione di un qualsiasi lato riduce il numero dicoppie connesse.

Un albero di n nodi ha sempre esattamente n − 1 archi. Per vedere ciodimostriamo che

1. Un grafo con n ≥ 3 nodi e |E| ≥ n non puo essere aciclico.

2. Un grafo con n ≥ 2 nodi e |E| < n − 1 non puo essere connesso.

Dim: Entrambi i punti possono essere dimostrati, ad esempio, per in-duzione. Per quel che riguarda il punto 1., l’asserzione e sicuramente veraper n = 3. Consideriamo ora il caso di n > 3. Se ogni nodo ha grado≥ 2 il grafo ha sicuramente almeno un ciclo (vedi anche esercizio in sezione6.2). Altrimenti, sia v un nodo di grado ≤ 1. Togliendo v e l’eventuale arco

6.4. ALBERI 77

incidente in v, otteniamo un grafo con n− 1 nodi e almeno n− 1 archi, che,per induzione, deve avere almeno un ciclo.

Per quel che riguarda il punto 2., il caso base n = 2, e certamente vero.Per n > 2, se esiste un nodo di grado 0, il grafo non e connesso. Altrimenti,sia v un nodo di grado 1 (deve esistere, perche, diversamente, si avrebbe∑

u∈V d(u) ≥ 2n. Ma 2n > 2|E|, mentre la somma dei gradi deve dare2|E|). Come prima, togliendo v e l’arco incidente in v, otteniamo un grafoG′ con n − 1 nodi e al piu n − 2 archi, che, per induzione, non puo essereconnesso. Siccome una qualsiasi coppia di vertici non connessa in G′ none connessa neppure in G (perche il nodo v non puo essere usato in nessuncammino –se non come nodo inziale/finale del cammino), anche G non econnesso. ♣Le seguenti proprieta caratterizzano gli alberi, ossia sono tutte definizionialternative di un albero G = (V,E):

1. G e connesso e aciclico

2. G e connesso e |E| = |V | − 1

3. G e aciclico e |E| = |V | − 1

4. G e connesso e, per ogni coppia di nodi i e j esiste un unico camminofra i e j

5. G e connesso e la rimozione di un qualsiasi arco disconnette G.

6. G e aciclico e, per ogni coppia di nodi i e j tali che ij /∈ E, aggiungendol’arco ij, G conterrebbe esattamente un ciclo.

Per esercizio, si dimostri l’equivalenza di almeno alcune delle definizionialternative citate (cioe si scelgano arbitrariamente alcune coppie x, y ∈{1, . . . , 6} e si dimostri che x implica y).

Un nodo di grado 1 in un albero si chiama una foglia. In ogni albero conn ≥ 2 ci sono almeno due foglie (per esercizio, lo si dimostri). Un nodo nonfoglia di un albero si chiama anche nodo interno. Si noti che un cammino dilunghezza l rappresenta un caso estremo di albero (con esattamente 2 fogliee l − 1 nodi interni). Il cammino e l’albero di diametro massimo tra tuttigli alberi su un certo insieme di nodi. All’altro estremo abbiamo la stella,ossia un albero in cui c’e un nodo interno e tutti gli altri nodi sono foglie.La stella e l’albero di diametro minimo.

Sia T = (V,ET ) un albero di supporto in un grafo G = (V,E). Larimozione da T di un qualsiasi arco e = ij disconnette l’albero. In parti-colare, l’arco individua una partizione dei nodi in due insiemi: Vi (i nodi


raggiungibili da i in (V,ET − {e})) e Vj = V − Vi (i nodi raggiungibili da jin (V,ET −{e})). Il taglio δ(Vi) e anche detto taglio fondamentale associatoall’arco e nell’albero T .

Similmente, l’aggiunta a T di un qualsiasi arco a = ij ∈ E−ET definisceunivocamente un circuito C in G passante per i e j. Il circuito, consistentedell’unico cammino tra i e j in T piu l’arco a, e detto circuito fondamentale

associato ad a nell’albero T .

Concludiamo questa sezione con un teorema riguardo al numero di alberipossibili su un insieme di n nodi.

Teorema 17: (Cayley) Il numero di alberi diversi su un insieme di n nodie

nn−2.

In questo teorema, alberi isomorfi ma non identici vengono consideratidiversi. Ad esempio, per n = 3 risultano 3 alberi diversi, mentre, se con-tassimo solo gli alberi non isomorfi fra loro, ci sarebbe un unico alberopossibile.

Non e nota alcuna formula semplice (del tipo della formula di Cayley)che fornisca il numero Tn di alberi non isomorfi di n nodi. Possiamo perodare dei limiti inferiori e superiori quali

nn−2

n!≤ Tn ≤ 4n−1. (6.1)

6.5 Grafi orientati

Un grafo orientato (o grafo diretto o digrafo) e una coppia G = (N,A) doveN e detto l’insieme dei nodi e A l’insieme degli archi. Ogni arco e unacoppia (i, j) ordinata di nodi, con i 6= j. Graficamente, l’arco (i, j) vienerappresentato con una freccia uscente dal nodo i ed entrante nel nodo j. Sidice anche che j e la testa dell’arco (i, j) e i ne e la coda.

Gli archi orientati rappresentano una relazione binaria non necessaria-mente simmetrica (per cui (i, j) 6= (j, i). Si noti che pero gli archi (i, j) e(j, i) possono esistere entrambi). Esempi di tale relazione possono essere

• “sul lavoro, i prende ordini da j”,

• “una strada tra i e j e percorribile nel senso che va da i a j”,

• “la squadra i ha battuto la squadra j in almeno un’occasione”,

• ecc.

6.5. GRAFI ORIENTATI 79

Per un insieme di nodi S ⊆ N , restano definiti i due insiemi di archiuscenti (δ+(S)) e entranti (δ−(S)) in questo modo:

δ+(S) := {(i, j) ∈ A | i ∈ S, j ∈ N − S} (6.2)

δ−(S) := {(i, j) ∈ A | i ∈ N − S, j ∈ S} (6.3)

In un digrafo si distinguono due tipi di gradi per i nodi, un grado d’uscita,d+(v) := |δ+({v})| pari al numero di archi di cui v e la coda, e un grado

d’entrata, d−(v) := |δ−({v})| pari al numero di archi di cui v e la testa.Un cammino in un grafo orientato G = (N,A) e una sequenza di vertici

v0, v1, . . . , vk−1, vk tali che, per 0 ≤ i ≤ k − 1, si ha (vi, vi+1) ∈ A. Si diceanche che un siffatto cammino va da v0 a vk (o parte da v0 e arriva a vk).Se v0 = vk il cammino si dice circuito o ciclo. Circuiti e cammini semplici,elementari, euleriani e hamiltoniani, sono definiti in maniera analoga al casonon orientato.

Dato un digrafo G = (N,A), resta definito un grafo non orientato, G′ =(N,E), detto il grafo non orientato sottostante, ottenuto “rimuovendo ladirezione” dagli archi di A (piu formalmente, ij ∈ E se (i, j) ∈ A∨(j, i) ∈ A).

Un digrafo si dice debolmente connesso se il grafo non orientato sot-tostante e connesso. Il digrafo si dice fortemente connesso se per ogni coppiai, j ∈ N esiste un cammino che va da i a j. Un digrafo risulta fortementeconnesso se e solo se ogni coppia di nodi e contenuta in un circuito. Da-to un digrafo G = (N,A) i nodi possono essere partizionati in sottoinsiemimassimali N1, . . . , Nk tali che i sottografi indotti G[Ni] sono fortemente con-nessi (e sono detti le componenti fortemente connesse di G). Si noti che, adifferenza del caso dei grafi non orientati, non e necessariamente vero cheogni arco in A appartenga a qualche componente fortemente connessa. In-fatti (esercizio) un arco a ∈ A appartiene a qualche componente fortementeconnessa se e solo se a e contenuto in almeno un circuito di G.

Esercizio 6.10. Vero o Falso: Esiste un grafo orientato G = (N,A) in cui(i) d+(v) 6= d+(w) per ogni v 6= w ∈ N e (ii) per ogni v ∈ N esiste u ∈ Ncon d−(u) = d+(v) − 1.

Un albero orientato anche detto (arborescenza) di radice r, e un grafoorientato aciclico in cui esiste un cammino da r a ogni altro nodo. In untale albero, si ha d−(r) = 0 e d−(v) = 1 per ogni nodo v 6= r. Un nododi un albero orientato in cui d+(v) = 0 si dice una foglia. Dato un nodov in un’arborescenza, l’insieme di tutti i cammini che cominciano in v edetto il sottoalbero di radice v. Ogni nodo in tale sottoalbero si dice anchediscendente di v. Un nodo v e antenato di tutti i suoi discendenti. In


particolare, se esiste l’arco (v, w), si dice che v e padre di w, e w e figlio div. Si noti che il sottografo sottostante un’arborescenza e un albero.

Un albero orientato si dice binario se d+(v) = 2 per ogni nodo v nonfoglia; si dice ternario se d+(v) = 3 per ogni nodo v non foglia; piu ingenerale, si dice k-ario se d+(v) = k per ogni nodo v non foglia. Dato unnodo u in un albero orientato di radice r, si dice livello di u la lunghezzadel cammino da r a u. In un albero k-ario ci sono al piu k l nodi di livello l.L’altezza di un albero e il livello massimo di uno qualsiasi dei suoi nodi.

Esercizio 6.11. Sia T = (N,A) un albero orientato binario di altezza h.Dimostrare che T ha al piu 2h foglie.

Capitolo 7

Ottimizzazione combinatoria

7.1 Il minimo albero di supporto

Sia dato un grafo pesato G = (V,E, c), con c(e) ≥ 0 per ogni e ∈ E.Studiamo il problema di determinare un albero di supporto di costo minimo.Il costo di un albero di supporto T = (V,ET ) e definito come

c(T ) :=∑

e∈E(T )

c(e).

Il grafo G (che supponiamo connesso) puo essere completo o meno. Nonc’e perdita di generalita ad assumere che G sia completo, in quanto, se non lofosse, potremmo aggiungere i lati mancanti e dare a loro un costo “infinito”.E facile verificare che la soluzione ottima necessariamente usera solo gli archioriginali.

Per il problema del minimo albero di supporto (detto anche MST, dall’in-glese Minimum Spanning Tree) e possibile l’utilizzo di un algoritmo greedy

(avido, ingordo).L’approccio greedy a un problema consiste nel fare scelte che massimiz-

zano il profitto immediato, senza preoccuparsi del fatto che queste sceltepossono portare a dei problemi in futuro. L’approccio greedy (quello cheusa la cicala rispetto alla formica) in generale non funziona. Ad esempio,supponendo di avere 100 euro con i quali vogliamo comprare un paio discarpe e un paio di jeans, l’approccio greedy porterebbe ad acquistare ilprimo paio di scarpe che ci piace (anche se costasse 99 euro!), salvo poi ren-derci conto che non abbiamo piu abbastanza soldi per i jeans. L’approcciocorretto, in questo esempio, consisterebbe nel raccogliere i prezzi di tutte lescarpe e tutti i jeans che ci piacciono, e scegliere la coppia che piu ci piacetra quelle che possiamo effettivamente permetterci.

81

82 CAPITOLO 7. OTTIMIZZAZIONE COMBINATORIA

Nel caso del MST l’approccio greedy constiste nello scegliere i lati damettere nella soluzione ottima (l’albero che stiamo costruendo) cercandosempre di aggiungere il lato di costo minimo tra quelli ancora disponibili.

Dato un insieme A di lati, diciamo che A e un insieme estendibile seesiste almeno un albero T ∗ = (V,ET∗) di costo minimo tale che A ⊆ ET ∗ .Se A e un insieme estendibile, ed e ∈ E − A e tale che A ∪ {e} e ancora uninsieme estendibile, allora e si dice un lato sicuro per A. Chiaramente, unacondizione perche un insieme di lati sia estendibile e che sia aciclico. Inoltre∅ e sicuramente estendibile.

La seguente procedura rappresenta uno schema generico per la costruzionedi un MST:

Algorithm 5 GenericMST

1. A := ∅;2. for i := 1 to |V | − 1 do

3. Trova un lato e ∈ E − A sicuro per A;4. A := A ∪ {e};5. endfor

Si noti che al termine della procedura siamo sicuri di aver selezionatoesattamente i lati di un albero. Infatti un albero ha |V | − 1 lati. Inoltre,l’albero ha costo minimo, come e immediato verificare. La procedura datanon puo pero ancora dirsi un algoritmo, in quanto il passo 3. e descrittotroppo genericamente, e non e chiaro in che modo si possa determinare unlato sicuro. Diamo ora una condizione sufficiente (ma non necessaria ***)perche un lato e sia sicuro per un insieme estendibile A.

Teorema 18: Sia A un insieme estendibile e sia V ′ l’insieme dei verticiche sono estremi di qualche lato in A. Sia e un lato in δ(V ′) (ossia con unestremo in V ′ e l’altro fuori da V ′). Se avviene che c(e) ≤ c(a) per ognia ∈ δ(V ′), allora e e sicuro per A.

Dim: ♣

7.1.1 Strategie di Prim e Kruskal

• Prim: T cresce come un’unica componente conessa, aggiungendo adogni iterazione il lato di costo minimo tra quelli in δ(T )

• Kruskal: T cresce come una foresta, aggiungendo ad ogni iterazione illato di costo minimo tra quelli in δ(T )

7.2. ACCOPPIAMENTI 83

7.1.2 Casi speciali, facili e difficili

Il problema del MST e stato presentato assumendo che tutti i lati abbianocosti non-negativi. Facciamo ora vedere come la presenza di eventuali costinegativi non altera la complessita del problema. Infatti, detto C = mine c(e)e ridefinendo i costi dei lati come c′(e) := c(e) − C, abbiamo che c′(e) ≥ 0per ogni e ∈ E. Inoltre, per ogni albero di supporto T si ha c′(T ) =c(T )− (n−1)C (in quanto ogni albero ha esattamente n−1 lati). Pertanto,dati due alberi T1 e T2 si avra c′(T1) ≤ c′(T2) se e solo se c(T1) ≤ c(T2).Quindi, per trovare l’albero di costo minimo per i costi originali, c(.), bastatrovare l’albero di costo minimo per i nuovi costi c′(.).

Ora, da questo risultato consegue anche che il problema di trovare l’al-bero di supporto di costo massimo puo essere risolto allo stesso modo cheper il costo minimo. Infatti, detto w(e) = −c(e), si ha che T ha costo mini-mo per w() se e solo se ha costo massimo per c(). Infatti, per ogni funzionef , si ha min f(x) = −max(−f(x)).

Il problema del minimo albero di supporto in presenza di vincoli ag-giuntivi sul grado dei nodi interni e/o sulla scelta delle foglie diventa perodifficile. Infatti, Qualora si imponga che il grado dei nodi interni sia 2, oche due determinati nodi, e solo quelli, siano le foglie dell’albero, un siffattoalbero deve necessariamente essere un cammino hamiltoniano. Dalla teoriadella complessita si sa pero che trovare cammini hamiltoniani in un grafo eun problema difficile.

7.2 Accoppiamenti

Un accoppiamento (o matching) in un grafo G = (V,E) e un insieme diarchi E′ a due a due non adiacenti, ossia tali che non hanno alcun estremoin comune. Altrimenti detto, E ′ e un matching se nel grafo G(E ′) = (V,E′)ogni nodo ha grado al piu 1.

Un matching si dice perfetto se in G(E ′) ogni nodo ha grado esattamente1. Chiaramente, una condizione necessaria (ma non sufficiente) per cuiquesto possa avvenire e che |V | sia pari.

Esercizio 7.1. Quanti sono i matching perfetti possibili nel grafo completoK2n?

• Il problema di ottimizzazione consiste nel trovare un matching di car-dinalita massima

• Dato un matching M , un cammino alternante e fatto di lati di Malternati a lati di E −M . Un nodo si dice esposto se non c’e un lato di


M a lui incidente. Un cammino alternante fra due nodi esposti si dicecammino aumentante per M .

• Il teorema prinicipale e che un matching M e massimo se e solo se nonci sono cammini aumentanti per M . Dimostrazione.

• Esiste una procedura efficiente per trovare il matching massimo in grafigenerici, ma e troppo complessa per essere fatta in questo corso.

7.2.1 Il caso bipartito

• Il caso bipartito puo essere risolto in modo efficace con un algortimopiu semplice, che vedremo qui

• algoritmo delle etichette.

7.2.2 Matching pesati

• Problema dell’assegnamento = matching bipartito pesato. Esempio deilavoratori/lavori

• Caso di grafo generale

• Entrambi i problemi possono essere risolti con algortimi “efficienti”,per quanto il caso bipartito sia considerevolmente piu facile.

7.3 Matrimoni stabili

• In questo problema e dato un insieme di n uomini ed un insieme din donne. Ogni uomo esprime un’ordine di preferenza per le n donne,e viceversa. Si tratta di trovare un matrimonio stabile. Questo e unmatching perfetto in cui non esistono un uomo m e una donna d, nonsposati fra loro, che si preferiscano a vicenda rispetto ai loro attualiconsorti (in tale caso, c’e’ il rischio che scappino insieme). Il principalerisultato di questa sezione e che un matrimonio stabile esiste sempre

• algoritmo combinatorico maschio-ottimo e femmina-pessimo.

• caso di preferenze parziali. In questo caso non e detto che una soluzioneesista sempre. Procedura di risoluzione per il caso delle preferenzeparziali.

7.4. MINIMA COPERTURA DI VERTICI 85

7.4 Minima copertura di vertici

In un grafo G = (V,E) una copertura di vertici e un insieme di vertici C ⊆ Vtale che ogni lato di E e incidente in almeno un nodo di C. Il problema diottimizzazione consiste nel minimizzare |C|.

• esempio poliziotti/strade

• Per ogni matching M e copertura C, |M | ≤ |C|• Il complementare di una copertura di vertici e un insieme indipendente.

• Caso pesato. Dati pesi wi, per i ∈ V , si tratta di trovare una coperturaC tale che w(C) sia minimo, dove w(C) :=

∑

i∈C wi.

• Il problema e in generale difficile (altrettanto quanto trovare un in-sieme indipendente di dimensione massima, o una clique di dimensionemassima). Se il grafo G e bipartito, pero il problema puo essere risoltoin maniera efficiente.

7.4.1 Il caso bipartito

In questa sezione dimostriamo il seguente teorema.

Teorema 19: Sia G = (V1, V2, E) un grafo bipartito, e siano M un match-ing di cardinalita massima e C una copertura di vertici di cardinalita minimain G. Allora

|M | = |C| (7.1)

Dim: Dimostriamo il teorema per induzione su |E|. Se |E| = 1, chiara-mente il matching massimo ha valore 1, ed inoltre un solo nodo e sufficienteper coprire tutti i lati. Supponiamo ora |E| = k > 1 e che il teorema val-ga per |E| = 1, 2, . . . , k − 1. Se non c’e alcun nodo esposto in G, allorabasta prendere una copertura fatta di tutti i vertici di V1. In questo caso,|M | = |V1| = |V2| e la coperura presa e certamente ottima.

Altrimenti, sia uv ∈ E tale che u ∈ V1 e un nodo esposto (un ragion-amento analogo vale nel caso u sia un nodo esposto di V2). Siccome Me massimo, v non puo essere esposto, e quindi esiste un arco iv ∈ M . Sirimuova dal grafo il nodo v nonche tutti gli archi a lui incidenti. Sia G′ ilgrafo risultante e M ′ = M − {iv} il matching rimanente. Facciamo vedereche non esistono cammini aumentanti per M ′ in G′ (e quindi M ′ e massimoper G′). Per assurdo, sia x, . . . , y un tale cammino aumentante, con x ∈ V1

e y ∈ V2, nodi esposti. Siccome x non poteva essere esposto in G (altrimentisi sarebbe avuto un cammino aumentante in G), deve essere x = i. Maallora u, v, i = x, . . . , y sarebbe un cammino aumentante in G, assurdo.


Quindi M ′ e un matching ottimo in G′ e, per induzione, esiste una cop-ertura C ′ di G′ con |C ′| = |M ′|. Ma allora C := C ′ ∪ {v} e una coperturadi G con

|C| = |M ′| + 1 = |M |.♣

Si noti che la dimostrazione del teorema suggerisce la seguente proceduraiterativa per determinare una copertura di vertici C ottima a partire da unmatching M ottimo. Si costruisce C (partendo con C := ∅), prendendoesattamente un estremo da ogni arco di M , in questo modo:

1. Se non ci sono nodi esposti in V1 ne in V2, si ponga C := C ∪ V1 e sitermini la procedura.

2. Altrimenti, sia ij ∈ M con i ∈ V1 collegato a un nodo esposto di V2, nelqual caso si ponga v := i, oppure j ∈ V2 collegato a un nodo espostodi V1, nel qual caso si ponga v := j.

3. Si aggiorni il grafo togliendo il nodo v e tutti gli archi incidenti in v (sinoti che questo puo rendere esposto un nodo che prima non lo era), siaggiunga v a C (C := C ∪ {v}) e si torni al passo 1.

7.4.2 Soluzioni approssimate

• L’algoritmo greedy (prendi nella copertura il nodo di grado massimo.Rimuovilo, insieme a tutti i lati incidenti, e ripeti finche tutti i lati sonostati coperti) non funziona. Esempi di casi dove trova una soluzionesubottima.

• Un semplice algoritmo che ottiene il fattore 2 di approssimazione (ossiala soluzione trovata non puo costare piu del doppio della soluzioneottima): 1. trovare un matching M massimale (non necessariamentemassimo). 2. prendere nella copertura entrambi gli estremi di ogni latoin M .

• dimostrazione del risultato di 2-approssimazione.

7.5 Clique e insieme indipendente

Un insieme di nodi a due a due adiacenti e una clique. Un insieme di nodia due a due non adiacenti e un insieme indipente. Il problema di ottimiz-zazione (in entrambi i casi) consiste nel determinare l’insieme di cardinalitamassima. Si noti che si puo passare da un problema all’altro semplicemente

7.5. CLIQUE E INSIEME INDIPENDENTE 87

(a) (b) (c)

Figura 7.1: (a) Una proteina non ripiegata. (b) La sua struttura 3-D. (c) Ilgrafo della mappa dei contatti.

rimpiazzando un grafo con il grafo complementare. Esiste una versione pe-sata del problema, in cui ogni nodo i ha associato un profitto wi, e si vuoletrovare l’insieme S di profitto complessivo massimo.

♥ Esempio. Una mappa dei contatti e una rappresentazione bi-dimensionaledi una struttura proteica tri-dimensionale. Quando una proteina si ripie-ga, due residui che non erano vicini nella sequenza lineare della proteina,possono terminare vicini l’un l’altro nello spazio tri-dimesionale (si veda lafigura 7.1 (a) e (b)).

La mappa dei contatti di una proteina con n residui e una lista dellecoppie di residui che si trovano a una “piccola” distanza (tipicamente, circa5A) l’uno dall’altro nella ripiegatura della proteina, mentre non erano adia-centi nella sequenza lineare. Ogni tale coppia di residui si dice anche esserein contatto. La mappa dei contatti puo anche essere interpretata come ungrafo, in cui ogni residuo e un vertice, e ogni lato collega una coppia diresidui in contatto (figura 7.1 (c)).

Uno dei problemi piu importanti della proteomica e la determinazionedella funzione di una proteina. A tal fine, siccome la funzione di una proteinadipende in massima parte dalla sua struttura tri-dimensionale, e importanteessere in grado di confrontare una struttura nuova con altre strutture note (inmodo che, per analogia, se le due strutture si somigliano anche la funzionalitadelle proteine sara presumibilmente simile).

Un modo per valutare la somiglianza di due strutture proteiche e quellodi valutare la somiglianza delle loro mappe di contatto. L’obiettivo e quellodi determinare se ci sono numerose coppie di residui nelle due proteine che“si comportano allo stesso modo” (ossia, che sono in contatto in entrambele proteine). Tali residui vengono considerati equivalenti.

Supponiamo allora date due mappe di contatto (che, per quanto si e det-to prima, sono sostanzialmente due grafi): G1 = (V1, E1) e G2 = (V2, E2).Numeriamo i residui secondo il loro ordine nella sequenza lineare della pro-teina, in modo che V1 = {1, 2, . . . , n1} e V2 = {1, 2, . . . , n2} (si noti che non


e richiesto che le due proteine abbiano la stessa lunghezza). Per determinareun insieme di residui equivalenti, bisogna scegliere due sottoinsiemi A ⊆ V1

e B ⊆ V2 con |A| = |B|. Sia A = {a1, . . . , ak} e B = {b1, . . . , bk}, cona1 < · · · < ak e b1 < · · · < bk. Allora, si dice che ai e equivalente a (oallineato con) bi, per ogni 1 ≤ i ≤ k. Si noti che non e necessario che tuttii residui delle due proteine siano allineati a qualche altro. Si noti anche chel’equivalenza (l’allineamento) rispetta l’ordine dei residui: se a e allineato ab, un residuo che segue a nella prima proteina puo solo essere allineato a unresiduo che segua b nella seconda.

Il valore di un allineamento e dato dal numero di coppie in contattonella prima proteina che sono allineate con coppie in contatto nella seconda.Tanto maggiore e questo valore, tanto piu simili sono le proteine. Per trovareil numero massimo di tali coppie, costruiamo un nuovo grafo GC (il grafodei conflitti per i contatti). In GC inseriamo un nodo (denominato Nlg)per ogni l ∈ E1 e g ∈ E2. Siano e = ij ∈ E1, e′ = i′j′ ∈ E1, ed f =uv ∈ E1, f ′ = u′v′ ∈ E2. I due nodi Nef e Ne′f ′ sono collegati da un latoin GC se e impossibile che i sia equivalente a u e j sia equivalente a v e,contemporaneamente, i′ sia equivalente a u′ e j′ sia equivalente a v′. Quindi,ogni equivalenza (allineamento) corretta, deve scegliere se allineare i con ue j con v oppure i′ con u′ e j′ con v′ (quindi uno dei contatti comuni (e, f)ed (e′, f ′) deve essere perso).

Sia R = {i, j, i′, j′} e S = {u, v, u′, v′}. Nel piano cartesiano, si consid-erino i |R| punti di coordinate (r, 0) con r ∈ R, e i |S| punti di coordinate(s, 1), con s ∈ S. Per vedere se esiste il lato tra Nef e Ne′f ′ , si colleghino ipunti (i, 0) con (u, 1), (j, 0) con (v, 1), (i′, 0) con (u′, 1) e (j′, 0) con (v′, 1)determinando (al piu) 4 segmenti diversi. Allora (e, f) ed (e′, f ′) sono com-patibili (cioe non esiste in lato Nef e Ne′f ′ in GC) se e solo se questi segmentihanno, a due a due, intersezione vuota.

Una volta calcolato GC , un insieme di coppie equivalenti che siano incontatto in entrambi i grafi, coincide con un insieme indipendente in GC .Pertanto, il problema di determinare la somiglianza delle mappe dei contattisi puo risolere trovando il piu grande insieme indipendente di GS . �

7.6 Colorazione di grafi

Una colorazione di un grafo G = (V,E), con k colori e una funzione f : V 7→{1, 2, . . . , k} tale che

f(i) 6= f(j) ∀ij ∈ E. (7.2)

7.7. IL COMMESSO VIAGGIATORE 89

Il numero f(i) e detto il colore del vertice i. Si noti che un grafo ebipartito se e solo se e colorabile (ossia esiste una sua colorazione) con due solicolori. Si noti che colorare un grafo con k colori corrisponde a partizionarei vertici in k insiemi indipendenti.

Il seguente problema e detto problema della colorazione di grafi:

Dato un grafo G determinare il numero minimo di colori per il qualeesiste una colorazione di G.

Tale numero e detto il numero cromatico di G, e indicato con χ(G).

• χ(G) ≥ 3 su un ciclo dispari e χ(G) ≥ |Q| per ogni clique Q.

• In particolare sia ω(G) il numero della clique di G, ossia la dimensionedella massima clique in G. Allora vale la relazione χ(G) ≥ ω(G).

7.6.1 Le guardie del museo

Il problema e quello di piazzare il numero minimo di guardie in un museo,inteso come una figura poligonale chiusa, in maniera che possano osservareogni punto del museo. Sia n il numero di pareti. Allora si puo dimostrareche dn/3e guardie sono sempre sufficienti per questo scopo. Dimostrazione

• Triangolare il poligono. Dimostrare che cio e sempre possibile.

• Tri-colorazione della triangolazione. Dimostrazione per induzione.

• Sia c il colore meno usato nella triangolazione. Piazzare le guardie neivertici dei triangoli colorati con c.

7.7 Il commesso viaggiatore

Dato un grafo pesato (orientato o non) il problema consiste nel trovare ilcircuito hamiltoniano di costo complessivo minimo.

Caso simmetrico e asimmetrico

• la matrice dei costi

• il problema puo’ essere usato per scoprire se un grafo ha un circuitohamiltoniano

• come completare un grafo non completo. Archi di costo “infinito”


Soluzioni euristiche e ricerca locale

• soluzioni greedy (nearest neighbor) e loro possibile fallimento

• scambio di 2 lati con altri due lati. Soluzione ottima localmente

• concetto di lower bound e upper bound. Nozioni (minime) di branchand bound

7.7.1 TSP euclideo: algoritmi approssimati

Minimo albero di supporto e circuito euclideo

Questo approccio e basato sul MST. Si prende il minimo albero di supporto esi raddoppiano i lati. Diventa un grafo euleriano. Su questo grafo si trova uncircuito euleriano. Dal circuito euleriano si estrae un circuito hamiltoniano(tramite scrociatoie, che si dimostra avere costo complessivo al piu 2 volteil costo minimo.

Algoritmo di Christofides Anche questo approccio e basato sul MST.Si prende il minimo albero di supporto e si inserisce un matching perfettodi costo minimo tra i nodi di grado dispari. Diventa un grafo euleriano. Suquesto grafo si trova un circuito euleriano. Dal circuito euleriano si estraeun circuito hamiltoniano (tramite scrociatoie, che si dimostra avere costocomplessivo al piu 3/2 volte il costo minimo.

7.8 Set covering

Il problema del Set Covering e il seguente. E dato un insieme E = {e1, . . . , en}detto insieme universo, e una collezione S di sottoinsiemi di E. Una famigliaS ′ ⊆ S si dice una copertura di E se, per ogni e ∈ E, esiste almeno un S ∈ S ′

con e ∈ S. Il problema di ottimizzazione consiste nel minimizzare |S ′|. Laversione pesata di questo problema si ha quando ad ogni S ∈ S e associatoun costo w(S). L’obiettivo in questo caso diventa quello di minimizzare ilcosto complessivo della copertura, ossia w(S ′) :=

∑

S∈S′ w(S).Esempi e applicazioni:

• PCR primer design

• feature selection

• tissue classification

• test collection (20 questions)

• pattern covering

Capitolo 8

Tracce di soluzioni

8.1 Capitolo 1

8.2 Capitolo 2

Sol. 2: Ogni numero si puo fattorizzare come 2k × d, con d dispari,d ∈ {1, 3, . . . , 197, 199}. Siano p1, . . . , p100 i numeri scelti, e siano k1, . . . , k100

e d1, . . . , d100 tali che pi = 2kidi per ogni i. Se di = dj per qualche i 6= j ilrisultato segue. Si supponga allora di 6= dj per ogni i 6= j. Allora d1, . . . , d100

sono proprio i 100 dispari 1, 3, . . . , 199. In particolare siccome almeno unnumero tra 1 e 15 e stato scelto, avremo che:

1. o 2k1 × 1 e stato scelto (per k1 ≤ 3. Copre i casi 1, 2, 4, 8)

2. o 2k2 × 3 e stato scelto (per k2 ≤ 2. Copre i casi 3, 6, 12)

3. o 2k3 × 5 e stato scelto (per k3 ≤ 1. Copre i casi 5, 10)

4. o 2k4 × 7 e stato scelto (per k4 ≤ 1. Copre i casi 7, 14)

5. o e stato scelto uno tra 20 × 9, 20 × 11, 20 × 13, 20 × 15

Usiamo ora un ragionamento generale. Se si e scelto un numero di tipoa = 2p × d e un altro di tipo b = 2q × D, con d che divide D, ma a nondivide b, allora p > q.

Usiamo quest’idea per i casi di cui sopra. Avendo scelto a = 2p × d,consideriamo p + 1 numeri dispari D1, . . . , Dp+1 tali che d divide D1, D1

divide D2, D2 divide D3, e cosi’ via. In particolare, siccome per ogni possibiledispari D, si e scelto un numero della forma 2hD, sono stati scelti dei numeridel tipo 2k1D1, 2k2D2, ..., 2kp+1Dp+1. Supponiamo che uno qualsiasi degliesponenti k1, . . . , kp+1, diciamo kr, sia ≥ p. Allora a divide il numero 2krDr.In caso contrario, ognuno dei p + 1 esponenti e compreso tra 0 e p. Per cui

91

92 CAPITOLO 8. TRACCE DI SOLUZIONI

ci sono almeno due esponenti uguali (diciamo ki e kj , con i < j. Sia h taleche h = ki = kj). Ma allora 2hDi divide 2hDj .

Quindi, per dimostrare il risultato, ci basta trovare almeno 4 disparimultipli di 1 (sottointeso, qui e dopo, < 200), almeno 3 dispari multipli di 3,almeno 2 dispari multipli di 5 e due multipli di 7, almeno un dispari multiplodi 9, uno di 11, uno di 13 e uno di 15. Ad esempio basta prendere:

• 3, 15, 45, 135 come multipli di 1

• 9, 27, 51 come multipli di 3

• 15, 45 come multipli di 5

• 21, 63 come multipli di 7

• 3x come multiplo di x con x = 9, 11, 13, 15

♣

Sol. 5: Ognuno puo avere un numero di amici nell’insieme {0, 2, . . . , 98}(non e possibile 100 perche sono 100 in tutto, per cui ≤ 99). Ora, o 3 personehanno 0 amici, per cui la soluz segue. Oppure, restano almeno 98 numericompresi tra {2, . . . , 98}, ossia in 48 slots. La media e 98/48 = 2.04 . . . perslot, quindi in almeno uno slot vanno 3 valori, ossia 3 persone hanno lo stessonumero di amici. ♣

8.3 Capitolo 3

Sol. 10: Un quadrato puo avere lato di lunghezza 1, 2, . . . , n. Vediamodove puo avere il vertice alto a destra. Numeriamo, dal basso all’alto, len + 1 righe da 0 a n e anche le colonne. I quadrati di lato 1 hanno verticealto a dx in tutte le righe e colonne tranne la colonna 0 e la riga 0. Percion × n modi. I quadrati di lato 2 hanno vertice alto a dx in tutte le righetranne la 0 e la 1, e tutte le colonne tranne la 0 e la 1. Percio (n−1)×(n−1)modi. Proseguendo si ha che il numero totale di quadrati e:

n∑

j=1

j2.

♣

8.4. CAPITOLO ?? 93

8.4 Capitolo 4

Sol. 1: Sia S l’insieme di tutte le permutazioni. Siccome si trattadi permutazioni del multi-insieme {3 · V, 2 · I, 3 · A, 1 · L, 1 · T} si ha |S| =10!

3!2!3! = 50400. Consideriamo A1 come l’insieme di permutazioni in cuisi legge “VIVA”. Questo corrisponde alle permutazioni del multi-insieme{1 · VIVA, 1 · V, 1 · I, 2 · A, 1 · L, 1 · T} e quindi

|A1| =7!

2!= 2520.

Si noto che e importante il fatto che il multiinsieme {1 ·V, 1 · I, 2 ·A, 1 ·L, 1 ·T} non permette di comporre la parola “VIVA”, o altrimenti ci sarebberostate delle permutazioni in A1 contate due o piu volte. Sia A2 l’insiemedi permutazioni che contengono “LA”. Si tratta delle permutazioni di {1 ·LA, 3 · V, 2 · I, 2 · A, 1 · T} e quindi

|A2| =9!

3!2!2!= 15120.

Infine, sia A3 l’insieme di permutazioni in cui si legge “VITA”. Questo cor-risponde alle permutazioni del multi-insieme {1 ·VITA, 2 ·V, 1 · I, 2 ·A, 1 ·L}e quindi

|A3| =7!

2!2!= 1260.

L’insieme A1 ∩ A2 ha le permutazioni in cui si legge sia “VIVA” che“LA”. Questo insieme corrisponde alle permutazioni del multi-insieme {1 ·VIVA, 1 · LA, 1 · V, 1 · I, 1 · T, 1 · A} e quindi

|A1 ∩ A2| = 6! = 720.

L’insieme A1 ∩ A3 ha le permutazioni in cui si legge sia “VIVA” che“VITA”. Questo insieme corrisponde alle permutazioni del multi-insieme{1 · VIVA, 1 · VITA, 1 · L, 1 · A} e quindi

|A1 ∩ A3| = 4! = 24.

L’insieme A2∩A3 ha le permutazioni in cui si legge sia “LA” che “VITA”.Questo insieme corrisponde alle permutazioni del multi-insieme {1 · LA, 1 ·VITA, 2 · V, 1 · I, 1 · A} e quindi

|A2 ∩ A3| =6!

2!= 360.


Infine, in A1 ∩ A2 ∩ A3 abbiamo le permutazioni che contengono sia“VIVA” che “LA” che “VITA”. Queste corrispondono alle permutazioni delmulti-insieme {1 · VIVA, 1 · LA, 1 · VITA}, per cui

|A1 ∩ A2 ∩ A3| = 3! = 6.

Dal principio di inclusione esclusione abbiamo

|A1 ∩ A2 ∩ A3| = 50400 − (2520 + 151202 + 1260) + (720 + 24 + 360) − 6

e quindi |A1 ∩ A2 ∩ A3| = 32598. ♣

Sol. 3: Sono 4350. ♣

8.5 Capitolo 5

8.6 Capitolo 6

Sol. 1: Diamo due soluzioni alternative, una ricorsiva (1) e l’altra diretta(2).

(1) Chiamiamo S(n) il numero di matching perfetti nel grafo K2n. Ilcaso base e S(1) = 1. In generale, dati 2n vertici, il vertice 1 puo essereaccoppiato a uno qualsiasi fra 2n − 1 vertici. Restano 2(n − 1) vertici, cheammettono S(n − 1) possibili accoppiamenti perfetti. Quindi

S(n) = (2n − 1)S(2n − 1) (8.1)

Usando la formula (8.1), sostituendo n− 1 al posto di n, si ricava S(n−1) = (2(n−1)−1)S(n−2) = (2n−3)S(n−2). Allo stesso modo, S(n−2) =(2n − 5)S(n − 3), e cosı via. Sostituendo i vari valori di S(.) nella formula(8.1), si ottiene:

S(n) = (2n − 1) × (2n − 3) × (2n − 5) × · · · 3 × 1

Quindi, S(n) e il prodotto di tutti i numeri dispari compresi tra 1 e 2n.(2) Supponiamo di disporre tutti i vertici in una permutazione (il che

puo essere fatto in (2n)! modi), e di considerare come lati del matching lecoppie di vertici, a due a due, incontrate nella permutazione. In questo mo-do, pero piu permutazioni possono dare luogo allo stesso matching, per cuibisogna evitare di ricontare matching identici. Ad esempio, le n coppie dielementi adiacenti in una permutazione possono essere permutate fra loro e

8.6. CAPITOLO ?? 95

darebbero luogo allo stesso matching. Questo puo essere fatto in n! modi.Inoltre, per ogni permutazione, i due elementi adiacenti all’interno di unaqualsiasi coppia potrebbero essere scambiati fra loro, e la permutazione in-dividuerebbe ancora lo stesso matching. Questo scambio si puo effettuarein 2n modi. Si ottiene che il numero di matching perfetti e:

(2n)!

2n n!

Si noti che questa formula chiusa, apparentemente piu complessa da com-prendere, in effetti restituisce il prodotto S(n) degli n numeri dispari com-presi tra 1 e 2n. ♣

Sol. 3: Consideriamo il caso generale. Dati n vertici, il grafo completoha n(n−1)/2 lati. Ogni altro grafo e identificato da un sottoinsieme dei latidel grafo completo. Ci sono pertanto

2n(n−1)/2

grafi possibili su n nodi specificati. Nel caso di questo esercizio, la rispostae 2190. ♣

Sol. 6: Se un grafo non e connesso esiste una partizione dei nodi chelascia x nodi, 1 ≤ x ≤ n − 1 da una parte e n − x dall’altra, senza lati tra idue gruppi di nodi. Il numero massimo di archi in una tale partizione e:

f(x) =x(x − 1)

2+

(n − x)(n − x − 1)

2

cioe f(x) = x2 −nx+n(n− 1). Il massimo di questa funzione nell’intervallo[1, . . . , n − 1] eottenuto per x = 1 e per x = n − 1, e vale (n − 1)(n − 2)/2.Non appena si aggiunge un ulteriore lato, il grafo non puo piu essere nonconnesso. ♣

Sol. 7: (=>) Sia G connesso. Presi x e y in G′, se x, y ∈ V allora eranogia collegati in G. Altrimenti, s.p.d.g., sia x = c. Allora esiste un camminoa, . . . , y e quindi il cammino x, a, . . . , y collega x a y in G′.

(<=) Sia G′ connesso e siano x, y in G. Siccome G′ e euleriano, esiste uncircuito x, . . . , y, . . . x. Questo circuito va da x a y e poi da y a x. Siccome cpuo essere solo nel tratto “di andata” o solo in quello “di ritorno”, uno deidue tratti e completamente incluso in G, che quindi e connesso. ♣

Sol. 9: Siano D = {1, 3, 5, . . . , 19} e P = {2, 4, 6, . . . , 20} rispettivamentei numeri dispari e pari in V .


1. Risulta ab ∈ E se a ∈ D, b ∈ D o a ∈ P, b ∈ P . Quindi D e P induconodue clique, disgiunte, di 10 nodi ciascuna. Quindi G non e connesso,non e bipartito, non e euleriano (ogni nodo ha grado 9) ne hamiltoniano(siccome non connesso).

2. Risulta ab ∈ E se a ∈ D, b ∈ P . Quindi G e bipartito completo,con bipartizione data da D e P . G e connesso, ed euleriano (ogninodo ha grado 10). Infine G e hamiltoniano. Ad esempio, il ciclo2, 1, 4, 3, 6, 5, . . . , 20, 19, 2 e un circuito hamiltoniano.

3. Risulta ab ∈ E se almeno uno fra a e b ein P . G risulta uguale algrafo in 2. piu’ una clique sui nodi in P . Come prima, G e connesso ehamiltoniano. G pero non e piu bipartito, ne euleriano (ogni nodo inP ha grado 19).

4. Risulta ab ∈ E se a, b ∈ D. Ogni nodo in P e isolato e quindi G none connesso. D e una clique di 10 nodi e quindi G non e bipartito.Inoltre G non e euleriano (ogni nodo in D ha grado 9). Infine G non ehamiltoniano (non connesso).

5. In G esistono nodi isolati. Ad esempio, tutti i nodi primi ≥ 7. Infattise p e un numero primo e pq = r = x2, nella decomposizione di r inprimi deve comparire il fattore p2. In particolare, p deve dividere x.Inoltre la divisione di r per p2 deve essere a sua volta un quadrato, > 1.Ora, il piu piccolo quadrato e 4, e 4 × 7 = 28 /∈ V .

Quindi, siccome ci sono nodi isolati, G non e ne connesso ne hamilto-niano. Inoltre, esistono nodi di grado 1, per cui G non e euleriano. Adesempio, il nodo 5, per il ragionamento di cui sopra, puo avere un latosolo verso un nodo che sia multiplo di 5 e di 4, e in G c’e’ un solo talenodo, il nodo 20. Infine, G non e bipartito. Infatti, per ogni coppiadi numeri x, y tali che sia x che y sono dei quadrati, esiste il lato xy.Questo implica che i nodi 1, 4, 9, 16 inducono una clique, e quindi Gnon e bipartito.

6. Risulta ab ∈ E se il resto di a e b per 3 e lo stesso (ossia se a =b mod 3). V si divide nelle seguenti classi (la classe Ci da resto i nelladivisione per 3): C0 = {3, 6, 9, 12, 15, 18}, C1 = {1, 4, 10, 13, 16, 19},C2 = {2, 5, 8, 11, 14, 17, 20}. Ogni Ci induce una clique e quindi G none bipartito. Non si hanno archi tra Ci e Cj, con i 6= j, e quindi G none connesso ne hamiltoniano. Infine, siccome i nodi in C0 e C1 hannogrado dispari (5), G non e euleriano.

♣

8.7. CAPITOLO ?? 97

8.7 Capitolo 7

Matematica Discreta -...

Documents

Transcript of Matematica Discreta -...