Algebra e geometria - calcolo combinatorio

Calcolo Combinatorio

A * B prodotto cartesiano

a∈ A , b∈B }

{(a,b)| A, B finiti

|A v B| = |A| * |B|

Es.

A = {a,b,c} B = {1,2}

Elenchiamo le coppie di A v B

(a,1) (a,2)

(b,1) (b,2)

(c,1) (c,2) ci sono 6 coppie = 3 * 2

Se |A| = 12 |B| = 10

A = {a1, a2,...., a12}

B = {b1,b2,..... b10}

b1

a2 b2 10 coppie che iniziano con a2

.

.

b10

Se A,B,C insiemi a∈ A , b∈ B , c∈C }

A x B x C = {(a,b,c)|

|A x B x C| = |A| * |B| * |C|

Es.

Un ristorante offre menù a prezzo fisso composto da un primo,

un secondo e un dolce

Se ci sono tre diversi primi

4 Secondi

3 Dolci

Quanti menù diversi si possono fare?

Primi * secondi * dolci

|Primi| = 3

|Secondi| = 4

|Dolci| = 3

Ci sono 3 * 4 * 3 menù diversi

Es. Identikit: 4 Tipi di capelli

3 Tipi di Occhi

8 Tipi di Naso

6 Tipi di Bocca

4 Tipi di Viso

Quanti volti diversi si possono ottenere

4 * 3 * 8 * 6 * 4 Volti diversi

Dobbiamo Contare le Quintuple

Es. Quante targhe si possono avere Due lettere - Tre cifre – Due lettere

26 * 26 * 10 * 10 * 10 * 26 * 26

PRINCIPIO MOLTIPLICATIVO

|A x B| = |A| * |B| Se A e B finiti

Se A = B A x A = A^2 |A^2| = |A|^2

A x A x A = A ^3

A^n = A * …. * A è l'insieme delle

V n-uple di elementi di A

n volte

Una n-upla si chiama anche sequenza di n elementi A * A

Es. A = {1,2,3}

A^2 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}

9 coppie

Invece di scrivere (1,1) scrivo 11

“ “ (2,1) scrivo 21

A^3 = {111,112,113,121,122,123,131,132,133}

{211,212,213,221,222,223,231,232,233}

311,312,313,321,322,323,331,332,333}

|A^4| = 3^4 Ci sono 3^4 sequenze di 4 elementi scelti tra 3

Adesso voglio contare le sequenze di elementi di A che si ottengono non ripetendo uno stesso

simbolo.

Se A = {1,2,3}

123,132,213,231,312,321

Ci sono solo 6 sequenze

Ottenute non ripetendo un simbolo

A = {1,2,3}

Sequenze di lunghezza 4 senza ripetizioni

Es.

A = {1,2,3,4}

Sequenze di 3 elementi senza ripetizioni

3 6 Sequenze iniz. 1

2 4

1 3 2

4

4 2

3

2 6 “” “” 2

3 6 “” “” 3

4 6 “” “” 4

Ho 4 modi di scegliere il primo elemento

Scelto il primo ho 3 modi di scegliere il secondo

Es.

Quanti numeri di 3 cifre diversi tra di loro esistono?

9 * 9 * 8

Quanti numeri < 160 esistono con cifre diverse?

10 * 9 * 8

9 + 9 * 9 * + 9 * 9 * 8

Quanti numeri <1000 esistono ammettendo le ripetizioni

Def. Disposizioni

Disposizioni semplici di h su n

sequenze di h simboli

scelti tra n possibilità senza ripetizioni

d n, h il numero di disposizioni semplici

Notazione n∈N

n! fattoriale di n

n! = n * (n-1) * (n-2) … * 2 * 1

Def. Ricorsiva

1! = 1

n! = n * (n-1)!

Es.

5! = 5*4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! =

= 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1

d n, h

Es. A = {a1,..., …,a2}

a3

a2 a4

a1 an

a3

an

Il primo scelto tra n

Il secondo scelto tra (n = 1)

Il terzo scelto tra (n = 2)

Il h-esimo scelto tra (n = (h+1) = (n-h-1)

Es. n = 5 h = 3

d 5,3 = 5 * 4 * 3

n * (n-1) * (n – 3 +1 )

d 5,3 = 5! / 2!

d n,h = n! / (n-h)!

Es.

5 biglie colorate

3 bambini

In quanti modi posso distribuire le biglie ai bambini? 5 * 4 * 3

Def.

Disposizioni con ripetizione di h oggetti scelti tra n

d' n, h = n ^ h

Es. A = {a,b,c} B = {1,2}

Quante funzioni ci sono tra A e B

3

(f(a), f(b), f(c)) B

∈

f: A → B

Quante terne su B ci sono? 2^3