29 Il Calcolo Combinatorio

Calcolo combinatorio

1. Permutazioni semplici di n oggetti

Dato un insieme di n oggetti, ad esempio n lettere, si vuol sapere quanti sono i possibili modi in cui esse possono essere ordinate in una fila. Il numero complessivo di questi modi viene detto permutazioni

semplici di n oggetti e lo indicheremo con il simbolo Pn.

Immaginiamo di disporre gli oggetti entro delle caselle numerate:

Per sapere quante sono le file costituite dagli stessi n oggetti, ma che differiscono solo per l’ordine, cominceremo con il posizionare uno qualunque di essi nella prima casella. Abbiamo evidentemente n scelte possibili per esso:

Procedendo con la scelta dell’oggetto che dovrà andare nelle seconda casella, avremo ora solo i rimanenti 1

n  oggetti fra cui sceglierlo:

Fermiamoci un momento a domandarci in quanti modi differenti possiamo fare queste due semplici operazioni successive. Per ognuna delle n scelte del primo oggetto vi sono le corrispondenti n  scelte del 1 secondo. Complessivamente ci sono quindi (n n  modi in cui posso prendere un oggetto qualunque da 1) un insieme di n e poi affiancarne ad esso un altro scelto fra i rimanenti. Andiamo avanti: per la terza casella ci rimangono n  scelte, per la quarta 2 n  : 3

Siamo così giunti alla quarta casella ed il numero di modi possibili è cresciuto fino a (n n1)(n2)(n3). Più in generale, si capisce ormai che se con k indichiamo il numero di casella, quando saremo giunti ad essa saremo rimasti con solo n k 1 oggetti fra i quali scegliere. Il processo continua fino alla casella numero

n , dove la scelta sarà obbligata essendo ormai rimasto un solo oggetto. Se k si ha infatti n n  k 1 1.

A questo punto è chiaro che il numero complessivo possibile di modi di ordinare gli n oggetti è dato da: ( 1)( 2)( 3)...1

n n n n

una tale espressione prende il nome di fattoriale di n e si indica con la scrittura n!. Abbiamo così dimostrato che:

n

1

2

3

4

5

6

n

A

1

B

2

C

3

D

4

E

5

F

6

n

n

1

n-1

2

3

4

5

6

n

n

1

n-1

2

n-2

3

n-3

4

5

6

n

n

1

n-1 n-2 n-3 n-4

2

3

4

5

n-5

6

n-k+1

k

1

n

! ( 1)( 2)( 3)...1 n

P n n n n n Esempio 1

In quanti modi differenti può essere mescolato un mazzo di 40 carte?

Si tratta di calcolare le possibili file ordinate di n 40 carte. La risposta è evidentemente 40!8.16 10 47, un numero, come si vede, enorme.

Esempio 2

In quanti modi differenti 15 studenti possono occupare i posti in un’aula?

Anche in questo caso la risposta è data dal numero di permutazioni di n 15 studenti, cioè 15!1307674368000

Esempio 3

Quante sono le funzioni biettive

f A

:



B

?

Esistono funzioni biiettive solo se la cardinalità dei due insiemi è la stessa, altrimenti non è possibile che ogni elemento di

B

sia immagine di uno ed un solo elemento di

A

. Detto

n



card A

( )



card B

( )

il numero di funzioni biiettive è dato dal numero di modi in cui gli

n

elementi di

B

possono essere associati agli

n

elementi di

A

, cioè il numero di modi in cui possono essere ordinati, vale a dire le loro permutazioni:

n

!

2. Disposizioni semplici di n oggetti in classe k

Un caso particolare delle permutazioni semplici di n oggetti si ha quando se ne vuole ordinare solamente un sottoinsieme costituito da k elementi. La domanda alla quale risponderemo è dunque: dato un insieme ad esempio di n 27 oggetti, quanti sottogruppi ordinati, ad esempio di k  di essi, possiamo formare? 6 Chiameremo il numero di tali sottogruppi ordinati disposizioni semplici di n oggetti in classe k e lo indicheremo con il simbolo Dn k, . Notiamo che:

1. Si deve avere sempre kn

2. Due sottogruppi potranno differire per l’ordine degli oggetti al loro interno ma anche perché hanno almeno un elemento diverso

Il calcolo numerico si effettua immediatamente considerato che dobbiamo solo ripetere la costruzione fatta per le permutazioni semplici, solo che adesso bisognerà fermarsi alla casella numero k :

In accordo con quanto abbiamo già osservato, il numero di modi in cui questo può essere fatto vale (n n1)(n2)(n3)...(n  , e quindi le possibili disposizioni semplici di n oggetti in classe k k 1) sono:

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

n k

D n n n n n  k

Esempio 4

In quanti modi differenti si possono scegliere 6 studenti da una classe di 27 per mandarli ad assistere ad uno spettacolo teatrale con dei posti a sedere numerati?

Visto che i posti sono numerati, l’ordine con il quale vengono scelti gli studenti è importante. Si tratta pertanto di calcolare quante sono le file ordinate di 6 elementi scelti da un insieme di 27, e cioè di calcolare le disposizioni

semplici di 27 oggetti in classe 6, D27,6. Per poter applicare la formula occorre calcolare quanto vale n k 1. In questo caso: 1 27 6 1 22 n  k    e pertanto: 27,6 27 26 25 24 23 22 213127200 D        . Esempio 5

Dato l’ insieme A(1, 2, 3) e l’insieme B h k l m( , , , )si dica quante sono le funzioni iniettive f A: B

Ricordando che una funzione è iniettiva se ad elementi diversi di A corrispondono immagini diverse in B, e che

f

agisce su tutti gli elementi di A, solo quando (come in questo caso) la cardinalità di B è maggiore di quella di A, ne concludiamo che possono esistere funzioni iniettive da A in B. Dobbiamo quindi calcolare il numero di modi in cui, scelti 3 elementi di B, essi possono associarsi ai 3 elementi di A. Si tratta quindi di scegliere sottogruppi di 3 da B tenendo conto del loro ordine, e quindi la risposta è data dalle disposizioni semplici di 4 elementi in classe 3. Abbiamo n 4, k 3, e n     k 1 4 3 1 2 da cui:

4,3 4 3 2 24

D    

Esempio 6

Un fioraio deve piantare lungo il bordo di una terrazza 5 piante di fiori tutte di colore diverso, da scegliersi fra 10 disponibili. Quanti modi diversi esistono di adornare il terrazzo?

L’ordine è essenziale, quindi si tratta di disposizioni semplici n 10, k 5, n  k 1 10  5 1 6, da cui:

10,5 10 9 8 7 6 30240

D      

Esempio 7

Utilizzando le cifre 1, 3, 5, 8, 4 si dica:

- Quanti numeri di 3 cifre differenti si possono formare - Quanti numeri dispari si possono formare

- Quanti numeri di tre cifre minori di 400 si possono formare - Quanti numeri di tre cifre divisibili per 5 si possono formare

I numeri di tre cifre costruibili con 1, 3, 5, 8, 4 sono una configurazione ordinata, quindi si tratta di disposizioni semplici di 5 elementi in classe 3:

5

n 

,

k 3

,

n     k 1 5 3 1 3 da cui:

D5,3   5 4 3 60

I numeri dispari costruibili con 1, 3, 5, 8, 4 sono quelli che terminano con 1, con 3 o con 5. Quindi, essendo l’ultima cifra fissata, si tratta di calcolare in quanti modi si possono ordinare le 4 rimanenti, vale a dire le permutazioni di 4 elementi:

P ₄ 4!    4 3 2 1 24

Ed ognuna di queste permutazioni può essere associata al 5, al 3 o all`1. In totale esistono: 24×3 = 7224 3 72

numeri dispari costruibili con le cifre 1, 3, 5, 8, 4.

I numeri di tre cifre minori di 400 costruibili con 1, 3, 5, 8, 4 sono quelli di tre cifre che iniziano con 1 oppure con 3. Quindi, essendo la prima cifra fissata, si tratta di calcolare in quanti modi si possono ordinare le 2 rimanenti, da scegliere fra le altre 4. Sono quindi le disposizioni in classe 2 di 4 elementi.

Essendo n – k + 1 = 4 -2 +1 = 3 risulta: D4,2   4 3 12

Ed ognuna di queste disposizioni può essere associata al 3 o all`1. In totale esistono: 12 2 24

I

numeri divisibili per 5 costruibili con 1, 3, 5, 8, 4 sono solamente quelli che terminano per 5. Quindi, essendo l’ultima cifra fissata, si tratta di calcolare in quanti modi si possono ordinare le 4 rimanenti. Sono quindi le permutazioni di 4 elementi.

P 4 4!    4 3 2 1 24

Ci sono quindi 24 numeri divisibili per 5 fra quelli costruibili con le cifre 1, 3, 5, 8, 4

3. Combinazioni semplici di n oggetti in classe k

Dato un numero complessivo di n oggetti ci concentreremo ora sulla possibilità di estrarre da essi

k elementi senza riguardo per l’ordine di estrazione. Considereremo quindi diversi due sottogruppi di k

elementi che differiscono per almeno un oggetto, ma li diremo uguali se differiscono solo per l’ordine. Chiameremo il numero di tali sottogruppi non ordinati le combinazioni semplici di n oggetti in classe k e lo indicheremo con il simbolo Cn k, .

Notiamo subito che dati n oggetti, il numero delle loro disposizioni in classe k è sempre maggiore del numero delle loro combinazioni in classe k . Infatti, scegliere una combinazione in classe k significa semplicemente scegliere un sottoinsieme di k degli n oggetti, ma poi questi possono essere riordinati in molti modi differenti. Quanti ordinamenti differenti ci sono già lo sappiamo, si tratta del numero delle loro permutazioni, e cioè esistono Pk k! ordinamenti differenti del sottoinsieme scelto. Poiché questo si può fare per ciascuna delle combinazioni in classe k , vale allora la semplice relazione:

, ,

n k n k k

D C P

Vediamo, a chiarimento di quanto detto, le disposizioni e le combinazioni in classe 3 delle 4 lettere ABCD. Senza fare uso di formule, si vede facilmente che esistono solo 4 modi di prendere 3 elementi dalle lettere date, ed essi sono ABC, ACD, BCD, ABD. Si ha quindi C_4,3  . Ciascuno di tali modi è passibile di tanti 4 riordinamenti quanto vale il numero permutazioni, cioè si possono fare P ₃ 3! file ordinate per ogni 6 combinazione, e quindi si hanno in tutto D_4,3C_4,3P₃   4 6 24 disposizioni semplici. Chiaramente già sapevamo come calcolare le disposizioni semplici e quindi non è questo il risultato utile. L’utilità appare chiara se invertiamo la formula ricavando le combinazioni a partire dalle disposizioni:

, , ( 1)( 2)...( 1) ! n k n k k D n n n n k C P k      

ABC

ACB

BAC

CBA

BCA

CAB

BCD

BDC

CBD

DCB

DBC

CDB

ACD

ADC

CAD

DCA

CDA

DAC

ABD

ADB

BAD

DBA

BDA

DAB

Le combinazioni in classe 3 sono 4

Ci sono 3! permutazioni per ogni combinazione

Ognuna di queste colonne è una sola combinazione, ma 6 permutazioni

4,3 4,3 3 4 6 24

Osserviamo a questo punto una semplice proprietà del fattoriale: ! ( 1)!

n n n

ad esempio si ha 7 ! 7

 

6!   7 6

 

5! e così via. Più in generale:

! ! ( 1)...( 1) ( )! ( 1)...( 1) ( )! n n n n n k n k n n n k n k             che inserito nella formula sopra fornisce un’espressione alternativa per Cn k_, :

, ( 1)( 2)...( 1)( )( 1)...1 ! !( )! !( )! n k n n n n k n k n k n C k n k k n k           

A seconda della minore complessità dei calcoli si sceglierà di volta in volta quale delle due espressioni equivalenti conviene usare. Per le combinazioni di n elementi in classe k si usa anche il simbolo sintetico:

, n k n C k       _{ }  . che si legge “n su k ”. Esempio 8

Un barman ha a disposizione 5 liquori. Quanti cocktails differenti può ottenere mescolandone 4 alla volta?

Si tratta di scegliere 4 liquori da un gruppo di 5 senza che conti il loro ordine, quindi dobbiamo calcolare le combinazioni di 5 oggetti in classe 4:

5,4 5 _{5 ! 5 4 !} 4 4 !(5 4)! C   _{ }_        4 ! 5 Esempio 9

Quante cinquine si possono fare a tombola?

Dobbiamo prendere 5 numeri su 90 totali senza riguardo per l’ordine, quindi essendo n  k 1 86:

90,5 90 _{90 89 88 87 86} 43949268 5 _{5 !} C   _{  }       

si noti che la formula adoperata nell’esempio 4 avrebbe richiesto il calcolo di 90! Per evitare di lavorare con numeri così grandi conviene in questo caso l’espressione alternativa.

Esempio 10

Nel gioco del poker si danno 5 carte ciascuno da un mazzo di 32. In quanti modi differenti può essere servito un giocatore? Essendo n  k 1 28 abbiamo: _32,5 32 _{32 31 30 29 28} 201376 5 _{5 !} C   _{  }       

SPECCHIO RIASSUNTIVO

Permutazioni di n oggetti: numero di file ordinate che si possono realizzare con n oggetti

Disposizioni semplici di n oggetti in classe k: numero di gruppi di k elementi che possono essere estratti da un insieme di n oggetti assumendo che due gruppi siano diversi se differiscono o per l’ordine oppure almeno per un elemento

Combinazioni semplici di n oggetti in classe k: numero di gruppi di k elementi che possono essere estratti da un insieme di n oggetti assumendo che due gruppi siano diversi se differiscono almeno per un elemento

4. Tecniche di risoluzione

Vi sono alcuni tipi di domande che ricorrono negli esercizi di calcolo combinatorio, vediamole insieme.

Domanda 1: si trovi in quanti modi può aversi una successione di eventi indipendenti, di cui il primo si può

verificare in a modi diversi, il secondo in b modi diversi, il terzo in c modi diversi e così via

Poiché gli eventi sono indipendenti, e quindi qualunque sia il tipo di quelli precedenti che si verifica, non influenza i successivi, ad ognuno degli a modi in cui si verifica il primo possiamo associare tutti gli b modi in cui si verifica il secondo e ad ognuno di questi il numero c di modi in cui si verifica il terzo etc.

modi modi del modi del modi del terzo primo totali secondo ...          _ _ _ _           _ _   _ _     La riposta è quindi a b c  ... Esempio 11

Un ristorante ha nel menù: 4 tipi di antipasto, 5 tipi di primo differenti, 3 tipi di secondo, 2 tipi di dolce. In quanti modi possiamo ordinare un pranzo completo?

Essendo gli eventi indipendenti, il numero di modi in cui la loro successione può verificarsi è

4 5 3 2   120, che coincide con il numero dei possibili pranzi completi. Esempio 12

Quanti sono i divisori positivi di 12000?

Scomponendo in fattori primi si ha 1200012 1000   3 4 103  3 2 2 52 3 3  3 2 55 3. Ne consegue che un divisore di 12000 ha la forma 3 2 5a  b c, dove ciascuno degli esponenti a b c, , va da zero fino al valore massimo che è quello che compare nella scomposizione in fattori primi trovata sopra. Ci sono quindi due esponenti possibili per il 3 (cioè 0 e 1), sei per il due (0,1, 2, 3, 4, 5) e quattro per il cinque (0,1, 2, 3). Il prodotto del numero di questi eventi indipendenti dà il totale dei divisori: 2 6 4  48.

In generale se un numero intero si scompone in 1 2 3

1a 2a 3a ... kak

n p p p p , allora il numero dei suoi divisori positivi è dato da: (a₁ 1)(a₂ 1)...(a_k 1).

Domanda 2: si trovi quanti sono gli anagrammi (senza significato compiuto) di una parola composta da

lettere tutte differenti, e di una parola composta anche da lettere che si ripetono.

Nel primo caso abbiamo a che fare con delle semplici permutazioni di n oggetti. Si vogliano ad esempio trovare gli anagrammi della parola CIELO, composta da 5 lettere. La prima lettera dell’anagramma la posso scegliere fra 5, la seconda fra quattro, la terza fra tre, la seconda fra due e per l’ultima ho solo una possibile scelta. Il risultato è di 5 4 3 2 1    120 anagrammi. Se invece alcune delle lettere si ripetono bisogna tenere conto del fatto che il loro scambio di posto non dà luogo ad anagrammi differenti. Calcoliamo il numero di anagrammi della parola BANANA, composta da 6 lettere. Se ripetessi il ragionamento di prima otterrei 6 5 4 3 2 1     720, un numero molto più alto degli anagrammi effettivamente possibili. E questo perché nel conto sono inclusi anche gli scambi di posto fra le 3 lettere A e quelli fra le 2 lettere N. Considerato che il numero di modi in cui le tre A possono scambiarsi di posto è3 !6 e che per le N è

2 !2, ogni anagramma è stato contato 6 volte di troppo a causa delle A e 2 volte di troppo a causa delle N. Dividendo per 6 2 12 abbiamo il giusto conteggio:720 60

6 2  .

In generale se si ha una parola di n lettere di cui una ripetuta k volte ed un’altra ripetuta p volte e così via, il numero di anagrammi che si possono fare è: !

! !.... n k p .

Esempio 13

Trovare quanti sono gli anagrammi della parola MATEMATICA

Ci sono 10 lettere di cui la M si ripete 2 volte, la T 2 volte, la A 3 volte, quindi: 10 ! 10 ! 10 ! 10 9 8 7 6 5 4 !

2 !2 ! 3 ! 4 3 ! 4 !

     

  

 4 ! 151200

Domanda 3: in quanti modi posso estrarre k oggetti da un insieme di n in modo che ne contengano esattamente m con una caratteristica fissata.

Il sottoinsieme di k oggetti è composto dagli m aventi la caratteristica richiesta e dai restanti k-m che non l’ hanno. Occorre dapprima calcolare il numero di modi in cui possono essere presi dal numero complessivo n gli m oggetti con le caratteristiche richieste. Queste saranno le combinazioni di n in classe m, (oppure le disposizioni se l’ordine è importante). Tale numero va poi moltiplicato per le possibili combinazioni (o disposizioni) degli oggetti rimasti (cioè nm) in classe km.

Esempio 14

Da una classe di 28 persone di cui 15 femmine e 13 maschi si dica in quanti modi si può formare una delegazione di 5 persone di cui 3 siano donne.

Il numero di modi in cui si possono prendere 3 donne da un gruppo di 15 è dato dalle combinazioni di 15 in classe 3: 15 3          

 , visto che l’ordine non è essenziale. I restanti 5 3 2 componenti della delegazione devono

essere scelti fra i 13 uomini ed il numero di modi di farlo è

13 2          

 . Poiché ad ogni sottogruppo di 3 donne può

corrispondere uno qualsiasi dei sottogruppi maschili, la risposta al problema sarà il prodotto

15 13 3 2    _{ }  _  _     _  _          .

Domanda 4: in quanti modi posso estrarre k oggetti da un insieme di n in modo che ne contengano almeno m

con una caratteristica fissata.

La strategia risolutiva consiste in questo caso nel calcolare il numero di casi sfavorevoli e nel sottrarlo al numero dei casi possibili. I casi possibili sono dati dal numero complessivo di modi in cui si possono prendere, senza riguardo per l’ordine, k oggetti da n:

n k        

 . I casi sfavorevoli sono dati dal numero di modi

in cui non si hanno almeno m oggetti del tipo voluto, e cioè quando se ne avranno m 2, m 3… etc. Al totale, allora, si sottrae dapprima il numero di modi in cui si possono prendere esattamente m 1 oggetti con la caratteristica richiesta, scelti nel sottoinsieme di quelli che fra gli n la presentano. Poi si tolgono i modi in cui se ne possono prendere m 2, m 3… fino all’ultimo caso in cui nel sottoinsieme di k elementi non

si ha nessun oggetto del tipo voluto.

Esempio 15

Da una classe di 28 persone di cui 15 femmine e 13 maschi si dica in quanti modi si può formare una delegazione di 5 persone di cui almeno 2 siano donne.

I casi possibili sono complessivamente

28 5        

 . I casi sfavorevoli sono quelli in cui fra i 5 elementi della

delegazione non figurano almeno 2 donne, e cioè nel caso in cui non ve ne sarà nessuna oppure ve ne sarà solo una. Il numero di modi in cui non è presente nessuna donna corrisponde a quello di tutte le delegazioni di 5 elementi maschi: 13 5        

 . Per stimare i casi in cui figura una sola donna, dobbiamo prima calcolare i

possibili insiemi di 4 maschi scelti fra i 13:

13 4          

 . Considerando poi che ad ognuno di tali insiemi si può

associare una qualunque delle 15 femmine, dovremo moltiplicare

13 4          

  per il numero complessivo delle

donne per avere il totale delle delegazioni costituite da 4 maschi ed una femmina. La risposta sarà allora:

delegazioni con almeno 2 donne 13 28 15 15 5 5 4      _{   }  _{ }    _ _ _ _                Esempio 16

Si dica quanti sono le cinquine della tombola che hanno 5 come MCD (massimo comune divisore).

Una cinquina che ha MCD=5 deve essere formata soltanto da multipli di 5. Essendo 90 i numeri della tombola, esistono dunque 90/5=18 numeri fra cui scegliere e quindi esistono

18 5          

  di tali cinquine. Tuttavia una cinquina di multipli di 5 può anche non avere 5 come MCD, ( si consideri ad esempio 20, 30, 40, 50, 60 che ha MCD=10). Ma dato che 5 è comunque un divisore di tutti i numeri della cinquina, se il MCD non è 5 allora deve essere un suo multiplo. Gli unici multipli di 5 che a loro volta hanno almeno cinque multipli minori di 90 (e quindi possono fare da MCD per una delle cinquine selezionate) sono 10 e 15: già il numero 20 ammette solo quattro multipli fino a 90. Esistono 6 multipli di 15 minori od uguali a 90 (15, 30, 45, 60, 75,

90) e 9 multipli di 10 minori od uguali a 90 (10, 20, 30…,90). Si possono quindi costruire 6 5             cinquine di multipli di 5 che hanno MCD=15 e 9

5          

  cinquine di multipli di 5 che hanno MCD=10. Il loro numero totale va sottratto a quello di tutte le cinquine possibili, per cui la risposta è:

Cinquine con MCD = 5 6 18 9 6 5 5 5 18 17 16 15 14 9 8 7 6 5 6 5 4 3 2 5 ! 1028160 15120 720 1012320 843 120 120  _                                                               Esame di stato 08-09

Sono dati gli insiemi A 1;2;3; 4 e Ba b c; ; . Tra le possibili funzioni di A in B ce ne sono di suriettive? Di iniettive? Di biettive?

Non ci sono certamente funzioni iniettive dato che il numero degli elementi di B è inferiore al numero degli elementi di A.

Non ci sono nemmeno funzioni biiettive perché queste dovrebbero essere contemporaneamente iniettive e suriettive, ma ciò non può essere non essendoci le iniettive.

Per il calcolo delle biiettive tutti e tre gli elementi di B devono essere delle immagini, nessuno di loro può restare escluso. Dobbiamo quindi associare a ciascuno degli elementi diA ognuno uno dei tre elementi di

B , pertanto ci saranno tre elementi di A con immagine differente e poi il quarto sarà associato ad un elemento ripetuto. Il numero di funzioni è dato quindi dal numero di coppie diverse che si possono scegliere fra i quattro elementi di A, moltiplicato per il totale dei tre elementi di B , a significare che scelta la coppia che ha la stessa immagine si può ancora scegliere l’elemento che fa da immagine.

4 3 18 2             

5. Disposizioni con ripetizione

Vogliamo ora calcolare quante file ordinate di k oggetti si possono formare scegliendo ciascuno di essi all’interno dello stesso insieme di n elementi, ma con la possibilità ogni volta di ripetere una scelta già fatta. Chiameremo il numero di tali file ordinate le disposizioni con ripetizione di n oggetti in classe k e lo indicheremo con il simbolo DR . La domanda alla quale risponderemo è dunque: dato un insieme ad n k,

esempio di n  oggetti, quante differenti file ordinate, ad esempio di 4 k  elementi, possiamo 6 formare scegliendo solo fra gli n? Notiamo che:

1. Essendo autorizzati a ripetere la scelta, si potrà avere kn ma anche kn

2. Considereremo diverse due file di k elementi che differiscono per almeno un oggetto o per l’ordine. Il calcolo numerico si effettua con una costruzione simile a quella delle permutazioni semplici, con la differenza che il numero delle possibili scelte non diminuisce di 1 passando alla casella successiva, ma è sempre n, visto che ogni volta ho n oggetti (virtuali) fra cui pescare:

Il numero di modi in cui questa fila ordinata può essere fatta vale allora: ... k n n n n n n n n k      _  volte

quindi le possibili disposizioni con ripetizione di n oggetti in classe k sono:

, k

n k

DR n

Esempio 17

Quanti diversi modi esistono di fare 13 al totocalcio?

Dato che ogni colonna differente è un potenziale 13, la domanda chiede di calcolare quante diverse colonne di 13 elementi si possono fare utilizzando i 3 simboli 1X2. Si tratta allora delle disposizioni con ripetizione di

3

n  elementi in classe k 13: DR_3,13 313 1594323.

Esempio 18

Due alunni di liceo seguono un percorso di studi che comprende 11 materie differenti. Calcolare:

a) in quanti modi diversi può verificarsi l’eventualità che entrambi prendano l’insufficienza in 2 materie a fine anno b) in quanti modi diversi può verificarsi l’eventualità che entrambi prendano un 3 ed un 4 a fine anno

L’ordine in cui si considerano gli studenti non conta, ed inoltre le insufficienze dei due ragazzi sono eventi indipendenti, e quindi come si è visto abbiamo:

modi modi del modi del primo totali secondo         _ _          _ _       .

a) Se lo studente fosse uno solo la risposta si otterrebbe calcolando in quanti modi diversi si possono scegliere 2 materie insufficienti fra le 11, cioè

11 2          

 . Ad ognuno di questi può essere associato uno qualunque

dei modi in cui il secondo studente può avere le 2 insufficienze, pertanto:

modi totali 11 11 2 2      _{   }  _{  }     _{   }         .

b) In questo caso l’assegnazione delle insufficienze alle materie diventa un processo ordinato perché vengono specificati due differenti voti, e ad esempio non è lo stesso avere 3 in Italiano e 4 in Matematica piuttosto che 4 in Italiano e 3 in Matematica. Dovremo quindi fare il prodotto delle disposizioni ordinate di

11 elementi in classe 2:





modi totali 2 11,2 11,2 11,2 D D D    _{   }      

. Essendo poi n  k 1 11 2  1 10 abbiamo





2 _{2 2}

11,2 (11 10) 110

D    .

Esempio 19

Quante sono le funzioni f A: B sapendo che

card A 

( )

3

e che

card B 

( )

4

? E scambiando le cardinalità?

Possiamo trovare tutte le funzioni calcolando il numero di modi in cui si possono prelevare 3 elementi da B, potendoli ripetere (anche tutti e tre uguali). Si tratta quindi delle disposizioni con ripetizione di 4 elementi in classe 3:

DR

4,3



4

3. Scambiando le cardinalità il numero di funzioni possibili diviene

3

4.

6. I coefficienti binomiali

Si voglia ottenere la potenza n-esima di un binomio, _{a b}



n

. Per definizione risulta:













 



volte ... n n ab _{}ab ab ab ab ab

Svolgendo i calcoli si ottiene una combinazione lineare1 _di n 1 _{monomi, ciascuno di grado n. All’interno} di essi a e b figurano con tutti gli esponenti da 0 fino ad n:







1





3 3





4 4





1



1 3 4 n-1

c c c ... c

n n n n n n n

ab a   a b   a b   a b    ab  b

ci proponiamo di calcolare i coefficienti della combinazione lineare c , c , c ,..., c_{1 2 3 n1}, detti coefficienti binomiali.

Il generico monomio della combinazione lineare ha quindi la forma: n-k volte k volte

... ...

n k k

a b aaaaaaaa aa bbbb bb_{ }

uno dei modi in cui la moltiplicazione degli n fattori (ab) fa comparire il termine an k kb nello sviluppo dei calcoli è prendendo il fattore a dai primi nk binomi della moltiplicazione, ed il fattore b dai rimanenti k:

Questa però non è l’unica moltiplicazione che, svolgendo i calcoli, produce an k kb . Infatti è sufficiente prendere il fattore a da nk binomi comunque scelti all’interno del prodotto e di conseguenza il fattore b dai restanti k binomi per ottenere lo stesso risultato, come nell’esempio seguente:

È facile calcolare il numero complessivo di modi differenti in cui questo procedimento può essere compiuto: si tratta di tutte le possibili scelte di nk elementi da un insieme di n. E visto che una volta scelti gli

nk binomi da cui si prende il fattore a la scelta dei rimanenti k da cui prendere b è obbligata, questo

1

Si dice combinazione lineare dei numeri reali   1, ,2 3,...n a coefficienti reali c , c , c ,..., c1 2 3 n la quantità

c  c  c  ...c 

n-k volte _{k volte}



ab



n 



a b a



b a



b

 

... a  b

 

ab a



b

 

... ab



n-k volte k volte

numero è anche uguale a tutte le possibili scelte di k elementi da un totale di n, e cioè vale n k          . Nello

sviluppo della potenza



ab



n ci sono quindi

n k           termini simili n k k a b

, e questo per ogni valore di k da 0 fino ad n. Ne concludiamo che:





0 n n n k k k n a b a b k         _{  }  



A titolo di esempio calcoliamo lo sviluppo di 



5

a b :





5 5 5 5 4 3 2 2 3 4 5 0 5 4 3 2 2 3 4 5 5 5 5 5 5 5 5 5 0 1 2 3 4 5 10 10 5 k k k a b a b a a b a b a b ab b k a a b a b a b ab b    _  _  _  _  _  _    _  _  _  _  _  _  _         _{ } _{ }  _{ }  _{ } _{ }  _{ }  _{ }        



L’interpretazione data di n k        

  come coefficienti nello sviluppo di un binomio consente il calcolo della loro somma dal primo fino all’ n-esimo. Poniamo di voler calcolare lo sviluppo del binomio (11)n 2n:

1 1 (1 1) 1 1 2 n n n n k k n k k n n k k     _  _  _  _   _{ }   _{ }        





7. Il triangolo di Tartaglia e la formula di Stifel

E’ possibile evitare l’utilizzo della formula ,

! !( )! n k n C k n k 

 e calcolare i coefficienti binomiali con un semplice procedimento ricorsivo, detto triangolo di Tartaglia, che a sua volta si basa su di una proprietà detta formula di Stifel.

Consideriamo quindi il numero di modi differenti in cui si possono scegliere k elementi di un insieme A costituito da n oggetti. Chiamiamo a uno qualunque di questi elementi e poniamoci le seguenti due domande:

1. Quante solo le combinazioni in classe k degli oggetti di A che contengono a?

2. Quante sono le combinazioni in classe k degli oggetti di A che invece non contengono a?

La risposta alla prima domanda si ottiene considerando che se a deve essere contenuto fra i k elementi di ciascuna combinazione, allora abbiamo una scelta delle k che è vincolata, e ne rimangono da scegliere k 1 fra gli altri elementi di A, che tolto a, sono n 1. Pertanto il numero che cerchiamo è

1 1 n k  _{ }  _  _  _{ }    .

La risposta alla seconda domanda si ottiene considerando che se a non deve figurare in nessuna delle combinazioni, allora la scelta dei k oggetti è limitata solo a quegli elementi di A diversi da a, che sono ancora n 1. Il numero che cerchiamo sarà pertanto

1 n k  _{ }  _  _  _    .

A questo punto osserviamo che per una qualunque combinazione di k elementi di A vi sono solo due possibilità: o la combinazione contiene l’oggetto a oppure non contiene l’oggetto a. Ne concludiamo che

sommando il numero di combinazioni in classe k che contengono a con quelle che non lo contengono si ha la totalità delle combinazioni in classe k di n oggetti, e cioè

n k          . In formule si ha il risultato: 1 1 1 n n n k k k    _  _    _  _  _  _ _  _                    

che va sotto il nome di formula di Stifel2_. Questa proprietà consente di ricavare i coefficienti binomiali costruendo una struttura triangolare come quella a lato dove, con l’eccezione dei fattori 1 agli estremi, ciascun numero è ottenuto sommando i due che nella fila precedente occupano la posizione nella colonne alla sua sinistra ed alla sua destra.

8. Cardinalità degli insiemi di funzioni

Definizione: si dice cardinalità di un insieme il numero di elementi che appartengono ad esso.

La cardinalità può essere finita ma anche infinita, come nel caso dell’insieme di numeri pari. Poniamo di avere due insiemi A e B e sia:

( )

acard A bcard B( )

in termini elementari diremmo che l’insieme A si compone di a elementi mentre l’insieme B si compone di b elementi. Ci chiediamo ora quale sia la cardinalità dell’insieme costituito dalle funzioni che vanno da A

in B .

Insieme di funzioni f A: B

Costruiamo la funzione generica, che – lo ricordiamo - associa ad ogni elemento di A un solo elemento di B immaginando che ognuno degli elementi di A sia una scatola dove dobbiamo inserire un elemento di B , potendo anche ripetere la stessa scelta per scatole differenti. Abbiamo un numero totale di a scatole:

2_{Un’ espressione equivalente della formula di Stifel è:}

1 1 n n n k k k       _{   }  _ _{ }  _  _{  }                  1 1 1 1 2 1 3 1 1 3 4 1 4 6 1 1 5 10 10 5 1 riga - 1n riga n - 1 - 1 n k  _  _  _  _     n - 1 k  _  _  _  _     n k          

1

2

3

4

5

6

a

Ho a disposizione b oggetti da inserire in ciascuna scatola: ci sono quindi b diverse possibili scelte per la prima scatola. Dato che una funzione generica può associare anche tutti gli elementi di A allo stesso elemento di B , la scelta già fatta può essere ripetuta: è come se nel passare alla successiva casella gli b oggetti non si esaurissero mai. Passando quindi al secondo scomparto ho sempre b diverse possibili scelte, ognuna delle quali può essere associata a ciascuna delle scelte b della scatola precedente:

Lo stesso numero di scelte vale per le caselle successive. Il totale delle scelte possibili è quindi il prodotto delle diverse possibilità per ciascuna casella. Dato che si hanno un numero a di caselle: un numero di volte ... a a b b b b b_{}    b b

Quindi la cardinalità dell’insieme di funzioni f A: B è:

( )

( )card A a

card B b

Esempio 20

Quante sono le funzioni f A: B sapendo che A 1;2;3; 4 e che Bh k l; ; ? E quante sono invece le funzioni f B: A?

Risulta:

( ) 4 a card A  bcard B( )3 Ci sono quindi: 4

3

81

a

b 



funzioni f A: B 3

4

64

b

a 



funzioni f B: A

Insieme di funzioni iniettive f A: B

Ricordiamo che una funzione è iniettiva se ad elementi diversi di A corrispondono immagini diverse in B , e che

f

agisce su tutti gli elementi di A. Se quindi B contiene meno elementi di A non è possibile trovare un’immagine per ciascuno degli elementi di A senza ripetersi. E se ci si ripete, la funzione non è iniettiva. Ne concludiamo che:

Possono esistere funzioni iniettive da Ain B solo se la cardinalità di B è maggiore od uguale a quella diA.

Tornando al modello delle scatole contrassegnate con gli elementi di A, questa volta dovremo riempirle con elementi diversi di B , visto che la funzione iniettiva non può ripetere una stessa immagine. Rispetto a prima gli b elementi in nostro possesso ora diminuiscono a mano a mano che li si va posizionando. Abbiamo così

b possibili scelte per la prima casella, ma solo b  per la seconda, 1 b  per la terza e così via. 2

b 1 2

...

b 1 2

...

b 1 2

...

b

1

b

2

b

3

b

4

b

5

_b

6

_b

a

b

1

b-1

2

b-2

3

b-3

4

b-4

5

_b-5

6

_b-a+1

a

Come si vede il numero di scelte per ogni casella si ottiene sottraendo a b il numero ordinale della casella e poi sommando 1. Quindi giunti all’ultimo oggetto dell’insieme A, che avrà il numero d’ordine a saranno rimaste b a 1 scelte. Poiché ognuna delle scelte di ogni casella è associabile ad una qualsiasi delle scelte per la casella precedente, il numero totale si ottiene anche in questo caso facendo il prodotto:

( 1)( 2)...( 1)

b b b b a  con ba

espressione che rappresenta la cardinalità dell’insieme di funzioni iniettive f A: B.

Esempio 21

Dato l’ insieme A 



1;2; 3



e l’insieme B



h k l m, , ,



si dica quante sono le funzioni iniettive f A: B e quante sono le funzioni iniettive f B: A

Risulta:

( ) 3

a card A  bcard B( )4

poiché è ba possono esistere funzioni iniettive f B: A. Calcoliamo il numero delle funzioni iniettive

:

f AB. Dato che risulta:

(b a     1) 4 3 1 2

ci sono quindi:

( 1)( 2)...( 1) 4(4 1)(4 2) 24 b b b b a     