Matematica Discreta Lezione del giorno 9 novembre 2011 Uso del principio di inclusione-esclusione

(1)

Matematica Discreta

Lezione del giorno 9 novembre 2011 Uso del principio di inclusione-esclusione

Esistono un uso positivo e un uso negativo del principio di inclusione-esclusione.

1) Uso positivo del principio di inclusione-esclusione.

Sia dato un insieme finito A ed n diverse proprietà P

1

, P

2

,….,P

n

che possono (o non possono) essere soddisfatte dagli elementi di A. Se vogliamo contare il numero degli elementi di A che soddisfano almeno una delle n proprietà, ciò equivale a costruire per ogni i=1,2,…,n l’insieme A

i

degli elementi di A che soddisfano la proprietà A

i

, e calcolare la cardinalità dell’unione A

1

A

2

…

A

n

, servendosi della formula del principio di inclusione-esclusione.

Esempio: Sia A l’insieme dei numeri naturali di 5 cifre con cifre scelte fra 1,2,3,4,5,6. Risolviamo il problema di contare il numero degli elementi di A che soddisfano almeno una delle seguenti 3 proprietà:

P

1

la prima cifra è 2 ;

P

2

le prime 3 cifre sono uguali fra loro ; P

3

l’ultima cifra è 3.

Dobbiamo allora costruire gli insiemi degli elementi di A che soddisfano singolarmente le 3 proprietà:

A

1

= { xA / la prima cifra è 2 }

A

2

= { xA / le prime 3 cifre sono uguali fra loro } A

3

= { xA / l’ultima cifra è 3}

e calcolare, con la formula del principio di inclusione-esclusione:

A

1

A

2

A

3

=(A

1

+A

2

+A

3

)-(A

1

∩A

2

+A

1

∩A

3

+A

2

∩A

3

)+A

1

∩A

2

∩A

3

.

Servendoci del principio delle scelte multiple si ottengono i valori:

A

1

=6

⁴

,A

2

=6

³

, A

3

=6

⁴

, A

1

∩A

2

=6

²

,A

1

∩A

3

=6

³

,A

2

∩A

3

=6

²

, A

1

∩A

2

∩A

3

=6.

Quindi la risposta al problema è:

A

1

A

2

A

3

 = 6

⁴

+6

³

+6

⁴

-(6

²

+6

³

+6

²

)+6 = 1296+216+1296-(36+216+36)+6 = 2526 . 2) Uso negativo del principio di inclusione-esclusione.

Sia dato un insieme finito A ed n diverse proprietà P

1

, P

2

,….,P

n

che possono (o non possono) essere soddisfatte dagli elementi di A. Se vogliamo contare il numero degli elementi di A che non soddisfano nessuna delle n proprietà, ciò equivale a costruire per ogni i=1,2,…n l’insieme A

i

degli elementi di A che soddisfano la proprietà A

i

, e calcolare la cardinalità del complementare dell’unione A

1

A

2

…A

n

, cioè calcolare la differenza A-A

1

A

2

…A

n

, usando la formula del principio di inclusione-esclusione.

Esempio: Se i dati sono quelli dell’esempio precedente, il numero degli elementi di A che non soddisfano nessuna delle proprietà P

1

, P

2

, P

3

sarà:

A-A

1

A

2

A

3

= 6

⁵

- 2526 = 5250 .