Matematica Discreta Lezione del giorno 2 novembre 2009 Principio delle scelte multiple.

(1)

Matematica Discreta

Lezione del giorno 2 novembre 2009 Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito A e di sapere che ogni elemento di A dipende dai valori di 2 variabili x,y, di modo che contare il numero di elementi di A equivalga a contare le possibili coppie di valori x,y: per contare le possibili coppie di valori x,y potremmo allora fissare in tutti i modi possibili un valore di x, e (per ogni valore fissato di x) calcolare il numero dei corrispondenti valori di y, e poi sommare i risultati ottenuti.

Esempio: supponiamo che A sia l’insieme dei numeri naturali di 2 cifre (decine e unità) con cifre scelte fra i valori 1,2,3,4, e tali che la cifra delle decine sia minore di quella delle unità. Per contare il numero di elementi di A, possiamo notare che ogni elemento di A 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 3 valori di y (che sono y=2,3,4), analogamente fissato il valore x=2 otteniamo in corrispondenza 2 valori di y (che sono y=3,4), fissato il valore x=3 otteniamo in corrispondenza 1 valore di y (che è y=4), fissato il valore x=4 otteniamo in corrispondenza 0 valori di y. In totale il numero di coppie di valori x,y (e quindi il numero di elementi di A) è la somma 3+2+1+0=6.

Sempre nell’ambito del problema di contare il numero di elementi di un insieme finito A 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 h di valori diversi e che, fissato un valore di x, il numero dei corrispondenti valori di y sia costantemente uguale a k (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 A) si otterrà sommando k+k+….+k (con h addendi) quindi sarà uguale al prodotto kh (questo è il cosiddetto principio delle scelte multiple per 2 variabili).

Quindi il principio delle scelte multiple per 2 variabili ha il seguente enunciato:

se ogni elemento dell’insieme finito A dipende dal valore di 2 variabili x,y e se - il numero di valori possibili di x è h

- fissato un valore di x, il numero di valori possibili di y è costantemente uguale a k allora la cardinalità di A è il prodotto kh.

Esempio: supponiamo che A 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 A è 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 A dipenda dai valori di n variabili x

1

,x

2

,….,x

n

; supponiamo inoltre che:

- il numero di possibili valori di x

1

é h

1

- fissato un valore di x

1

, il numero di valori possibili di x

2

è costantemente uguale a h

2

(2)

- fissato un valore di x

1

e di x

2

, il numero di valori possibili di x

3

é costantemente uguale a h

3

……etc

- fissato un valore per ognuna delle variabili x

1

,x

2

,…,x

n-1

, il numero dei valori possibili di x

n

é costantemente uguale ad h

n

allora il numero degli elementi di X è uguale al prodotto h

1

h

2

……h

n

. Permutazioni

Sia X={b

1

, b

2,…..,

b

n

}un insieme finito di cardinalità n.

Definiremo permutazione degli elementi b

1

, b

2

, ….., b

n

un qualunque modo di disporre ordinatamente gli elementi b

1

, b

2

, ….., b

n

.

Esempio:

Se n=3 e se X={b

1

, b

2

, b

3

}, si ottengono le seguenti 6 permutazioni degli elementi b

1

, b

2

, b

3

: b

1

b

2

b

3

, b

1

b

3

b

2

, b

2

b

1

b

3

, b

2

b

3

b

1

, b

3

b

2

b

1

, b

3

b

1

b

2

Poniamoci il problema di calcolare il numero delle permutazioni degli elementi b

1

,b

2

,…..,b

n

, utilizzando il principio delle scelte multiple.

Sia A l’insieme di tutte le permutazioni degli elementi b

1

,b

2

,…..,b

n

. Ogni elemento di A dipende da n variabili:

x

1

= scelta dell’elemento da inserire nella posizione numero 1 x

2

= scelta dell’elemento da inserire nella posizione numero 2 x

3

= scelta dell’elemento da inserire nella posizione numero 3

….

x

n

= scelta dell’elemento da inserire nella posizione numero n (l’ultima posizione).

Inoltre:

- il numero dei possibili valori di x

1

é n (nella posizione numero 1 si può inserire un elemento qualunque scelto fra gli elementi b

1

, b

2

, ….., b

n

)

- fissato un valore di x

1

, il numero di valori possibili di x

2

è costantemente uguale a (n-1) (nella posizione numero 2 si può inserire un elemento qualunque scelto fra gli elementi b

1

, b

2

, ….., b

n

tranne quello fissato nella posizione numero 1)

- fissato un valore di x

1

e di x

2

, il numero di valori possibili di x

3

é costantemente uguale a (n-2) (nella posizione numero 3 si può inserire un elemento qualunque scelto fra gli elementi b

1

, b

2

, …, b

n

tranne quelli fissati nella posizione numero 1 e 2)

………

……

- fissato un valore per ognuna delle variabili x

1

,x

2

,…,x

n-1

, il numero dei possibili valori di x

n

é costantemente uguale ad 1 (nella posizione numero n può essere inserito solo 1 elemento, l’unico rimasto dopo avere inserito (n-1) elementi nelle altre posizioni)

Per il principio delle scelte multiple, il numero il numero delle permutazioni degli elementi b

1

,b

2

,

…..,b

n