Matematica Discreta Lezione del giorno 17 novembre 2008 Principio delle scelte multiple.

(1)

Matematica Discreta

Lezione del giorno 17 novembre 2008 Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito X e di sapere che ogni elemento di X dipende dai valori di 2 variabili x,y, di modo che contare il numero di elementi di X equivalga a contare le possibili coppie di valori x,y: potremmo allora, per ogni fissato valore di x, calcolare il numero dei corrispondenti valori di y e poi sommare.

Esempio: supponiamo che X sia l’insieme dei numeri naturali di 2 cifre (in base 10) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia minore di quella delle unità. Per contare il numero di elementi di X, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

Fissato il valore x=1 otteniamo in corrispondenza 5 valori di y (2,3,4,5,6), analogamente fissato il valore x=2 otteniamo in corrispondenza 4 valori di y, fissato il valore x=3 otteniamo in corrispondenza 3 valori di y, fissato il valore x=4 otteniamo in corrispondenza 2 valori di y, fissato il valore x=5 otteniamo in corrispondenza 1 valore di y, fissato il valore x=6 otteniamo in corrispondenza 0 valori di y. In totale il numero di coppie di valori x,y (e quindi il numero di elementi di X) è la somma 5+4+3+2+1+0=15.

Sempre nell’ambito del problema di contare il numero di elementi di un insieme finito X in cui ogni elemento dipende dai valori di 2 variabili x,y, facciamo un ulteriore ipotesi (che non è verificata nell’esempio precedente): supponiamo che la variabile x assuma un numero n di valori diversi e che, fissato un valore di x, il numero dei corrispondenti valori di y sia costantemente uguale ad m (indipendentemente dal valore fissato per x).

In tale caso il numero delle coppie di valori di x,y (e quindi il numero di elementi di X) si otterrà sommando m+m+….+m (con n addendi) quindi sarà uguale al prodotto nm (principio delle scelte multiple per 2 variabili).

Esempio: supponiamo che X sia l’insieme dei numeri naturali di 2 cifre (in base 10) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia diversa da quella delle unità. Come nell’esempio precedente, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x delle decine e la cifra y delle unità.

La variabile x può assumere 6 valori distinti 1,2,3,4,5,6. Fissato un valore di x, il numero dei valori corrispondenti di y è costantemente uguale a 5 (sono tutti i valori 1,2,3,4,5,6 tranne quello scelto per x).

Siamo nelle ipotesi del principio delle scelte multiple e possiamo concludere che il numero di elementi di X è il prodotto 65=30

Con ragionamenti simili ai precedenti si ottiene il principio delle scelte multiple per più variabili:

supponiamo che ogni elemento dell’insieme finito X dipenda dai valori di n variabili x

1

,x

2

,….,x

k

; supponiamo inoltre che:

- la variabile x

1

assuma un numero n

1

di valori diversi

- fissato un valore di x

1

, il numero dei corrispondenti valori di x

2

sia costantemente uguale ad n

2

(indipendentemente dal valore fissato per x

1

)

- fissato un valore di x

1

e un valore di x

2

, il numero dei corrispondenti valori di x

3

sia costantemente uguale ad n

3

(indipendentemente dai valori fissati per x

1

e di x

2

)

……etc

(2)

- fissato un valore per ognuna delle variabili di x

1

,x

2

,…,x

k-1

, il numero dei corrispondenti valori di x

k

sia costantemente uguale ad n

k

(indipendentemente dai valori fissati per x

1

,x

2

,…,x

k-1

) allora il numero degli elementi di X è uguale al prodotto n

1

n

2

……n

k

.

Numero delle funzioni fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni f: A  B.

Se {a

1

, a

2

, ….., a

n

} sono gli elementi di A, ognuna di tali funzioni dipende dalle n variabili seguenti:

x

1

=valore del corrispondente in B dell’elemento a

1

; x

2

=valore del corrispondente in B dell’elemento a

2

;

…..

x

n

=valore del corrispondente in B dell’elemento a

n

.

La variabile x

1

ha m valori possibili (gli m elementi di B); fissato un valore di x

1

, la variabile x

2

ha m valori possibili (di nuovo gli m elementi di B); fissato un valore di x

1

e un valore di x

2

, la variabile x

3

ha m valori possibili (di nuovo gli m elementi di B); etc ..…. ; infine fissato un valore di x

1

, uno di x

2

,…, uno di x

n-1

, la variabile x

n

ha m valori possibili (sempre gli m elementi di B). Per il principio delle scelte multiple, il numero delle possibili funzioni f: A  B è il prodotto mm…..m (con n fattori), quindi è la potenza m

ⁿ

.

La formula che dà il numero di tutte le funzioni f: A  B è allora B

^A

.

Esempio: Se A={a,b}, B={1,2,3}, il numero delle possibili funzioni f: A  B è 3

²

=9, mentre il numero delle possibili funzioni f: B  A è 2

³

=8 .

Numero delle funzioni iniettive fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni iniettive f: A  B.

Sappiamo già che nel caso n>m non esiste nessuna di tali funzioni iniettive.

Quindi supponiamo nm.

Se {a

1

, a

2

, ….., a

n

} sono gli elementi di A, ognuna di tali funzioni iniettive dipende dalle n variabili seguenti:

x

1

=valore del corrispondente in B dell’elemento a

1

; x

2

=valore del corrispondente in B dell’elemento a

2

;

…..

x

n

=valore del corrispondente (in B) dell’elemento a

n

.

La variabile x

1

ha m valori possibili (gli m elementi di B); fissato un valore di x

1

, la variabile x

2

ha m-1 valori possibili (gli m elementi di B escluso quello scelto come corrispondente di a

1

); fissato un valore di x

1

e uno di x

2

, la variabile x

3

ha m-2 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a

1

,a

2

); etc...…. ; fissato un valore di x

1

, uno di x

2

,…, uno di x

n-1

, la variabile x

n

ha m-(n-1)=m-n+1 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a

1

,a

2

,….,a

n-1

).

Per il principio delle scelte multiple, il numero delle possibili funzioni iniettive f: A  B è il prodotto m(m-1)(m-2)…..(m-n+1), quindi è il prodotto in ordine decrescente dei numeri naturali da m ad m-n+1 (supponendo sempre nm) .

Esempio: Se A={a,b,c,d}, B={1,2,3,4,5,6}, A=4, B=6 il numero delle possibili funzioni

iniettive f: A  B è 6543=360.

(3)

Numero delle funzioni surgettive fra insiemi finiti

Il problema di contare il numero delle funzioni surgettive fra insiemi finiti sarà affrontato in seguito, nell’ambito della teoria dei numeri di Stirling.

Numero delle funzioni biunivoche fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni biunivoche f: A  B.

Sappiamo già che nel caso nm non esiste nessuna di tali funzioni.

Quindi supponiamo n=m.

Per un teorema già dimostrato, sappiamo che, sotto l’ipotesiA=B, una funzione iniettiva è sempre anche surgettiva, quindi biunivoca: basta allora contare le funzioni iniettive da A a B.

Applicando la formula precedente (con n=m) si ottiene che il numero delle possibili funzioni biunivoche f: A  B è il prodotto n(n-1)(n-2)…..1, ossia il prodotto di tutti i numeri naturali consecutivi da 1 ad n, detto fattoriale di n e indicato con il simbolo n! .