Analisi matematica I - calcolo combinatorio

DEF

. Si chiama prodotto cartesiano di due insieme A e B , e si indica con A B , l'insieme delle coppie ordinate

∈ ∈

( a , b ) di elementi, con a A

, b B

.

α β γ α β γ α β γ

× =

Esempio: {

H , T } { , , } {( H , ), ( H , ), ( H , ), (

T , ), (

T , ), (

T , )}

# × = #Α)(#Β)

TEOR

.

1 Se A e B sono insiemi finiti ma non vuoti allora (

A B ) (

# × = # × ∪ × ∪ ∪ ×

DIM

. Dati a , a ,......, a gli elementi da A

, é (

A B ) ({

a } B ) ({

a } B ) ....... ({

a } B )

#Α #

1 2 1 2 A

# ⋅ #Β) # × = #

e questo è ( A

) ( perché l'unione è "disgiunta" e ({ } )

a B B

k

×

({ } è una "colonna" nella figura)

a B

k

B colonna AxB

. . . . .

. . . . .

. . . . .

. . . . .

a a a a a

1 2 3 k #A

A ⋅ =

Esempio Le sequenze di una lettera(inglese) e una cifra sono 26 10 260 perché esse costituiscono un

×

insieme con corrispondenza biunivoca con A B , essendo:

=

A : {

lettere inglesi

} Modello matematico

=

B : {

cifre

}

OSS4 . Spesso si usi implicitamente questa considerazione. Parlando in termini generali, se un'azione si

può fare in n modi (diversi), e una seconda azione si può fare in m modi, allora per l' , l'

OSS2 OSS 3 e il TEOR1

⋅

la sequenza delle due azioni si può fare in m n modi.

. La cardinalità di un insieme è la somma dei sottoinsiemi di una sua qualunque partizione.

OSS5 #14

. . . . . .

. . . . . . . .

Per trovare in quanti modi si può fare una certa cosa, si possono aggregare quei modi in insiemi disgiunti, determinare

la loro cardinalità e SOMMARLE.

Es.

(Quesito d'esame) Si lanciano contemporaneament

e due dadi per 5 volte consecutive e dopo ogni lancio si

registra il punteggio. In quanti modi si possono realizzare 8 punti in almeno 4 lanci su 5?

=

Risultato 100000

Svolg

. Seguendo l ' OSS5 sommeremo il n

umedo di modi di realizzare 8 in 5 lanci al numero di realizzare 8 su

esattamente 5 lanci.

In ogni lancio dei due dadi, da consideare distinguibili, otto punti si possono realizzare in questi 5 modi:

2 e 6, 3 e 5, 4 e 4, 5 e 3, 6 e 2. (Elencazione con conteggio)

5

Allora si possono realizzare 8 punti in 5 lanci in 5 modi. ⋅ ⋅ −

4

Otto punti in esattamente 4 lanci si possono realizzare in 5 5 (36 5) modi, com

e vedremo (si consideri OSS4 ).

5 sono i modi di scegliere in quali 4 dei 5 lanci si realizzano gli 8 punti( ovvero di scegliere in quale dei

4

5 lanci non si realizzano). 5 sono i modi di realizzare 8 p unti in ciascuno di quei 4 lanci, in base all'elencazione

con conteggio fatta prima. 36-5 sono le probabili uscite del lancio in cui si realizzano 8 punti.

+ ⋅ = ⋅ = ⋅ = =

5 5 2 5 5 5

Allora in tutto: 5 5 31 32 5 2 5 10 10 0000

Es

. In quanti modi si possono ordinare le lettere C,R,O,N,I,S,T,A?

DEF

. Ogni ordinamento totale di un insieme finito non vuoto A si dice permutazione degli elementi di A e viene

#

identificato con l'unico ( A)-iplo di elementi di A che rappresenta quell'ordinamento totale.

=

Il numero di esse si indica con Pn e si pone anche P : 1

0

∈ ⋅ ⋅ ⋅ ⋅ > =

ℕ

DEF

. Per ogni n , si dice FATTORIALE di n e di indica con n ! il nimero 1 2 n n n

3 ....... se 0 e 1 se 0.

= ⋅ ⋅ ⋅ ⋅ =

Per esempio: 5! 1 2 3 4 5 120

=

Pn n

TEOR . 2 ! − −

n n n e allora la

DIM

. Il primo elemtno può essere scelto in modi, il secondo in 1 modi (restano 1 elementi)

−

coppia ordinata dei primi 2 elementi può essere costituita in n ( n 1) modi. Similmente il terzo dei primi 3

− −

elementi può essere scelto in n 2 modi (perché restano n 2 elementi) e allora la terna dei primi 3 elementi

− −

può es sere costituta in n ( n 1)( n 2) modi.

−

E così via, finché l'ultimo elemnto, l'

n esimo , può essere scelto in un solo modo. Cosicché si ha in definitiva

− −

che il numero delle permutazioni è n ( n 1)( n 2).....1, cioè appunto n !

=

Soluzione

. Le lettere si possono riordinare in 8! 40320 modi.

Es

. Quanti sono i numeri esadecimali di 4 "cifre"(da 0000 a FFFF) con le "cifre" tutte diverse?

≤ ≤

> elementi, e un numero naturale k tale che 0 k n , i sottoinsiemi ordinati

DEF

. Dato un insieme E di n 0

E di k elementi si dicono DISPOSIZIONI(SEMPLICI) di n oggetti a k a k , e il numero di esse si indica con D

n , k

=

e si ponte per co

nvenzione D 1

n ,0

n !

=

TEOR . 3 D

n , k −

( n k !)

Svolg

. Consideriamo i sottinsiemi ordinati {0,1........9, A

......

F } di 4 elementi, che sono un numero di

⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅

16! 16! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

= = = = = =

D T3 DEF 43680

( ) ( )

16,4 − ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 12

(16 4)! 12! 1 2 3 4 5 6 7 8 9 10 11

.

DIM T3 P

= = = = = n

Se 0 : ( ) 1

k D D DEF

n k n

, ,0 P

n

P !

n

= = =

n

0 ( )

T2

k −

( )!

P n k

−

n k P P P !

n

= = = = = = = =

n n n

Se : ( )

T2

k n D D P

n k n n n

, , −

1 ( )!

P P n k

−

n k

0

e la secondo uguaglianza vale perché il numero di sottoinsiemi ordinati di el

n ementi di un sottoinsieme E di n elementi

coincide col numero di ordinamenti di .

E

< <

Se 0 Per ottenre una permutazioni di elementi possimao scegliare in modi una - ordinata, e posporvi

k n n D k upla

n , k

− −

con Pn k ordinamenti diversi gli n k elementi restanti, allora

P n !

= ⋅ = = =

n

P =( OSS4

) D P e allora D ( T2 )

− −

n n , k n k n k −

P n k

( )!

−

n k

> < <

DEF

. Dato un insieme E di n 0 elementi, e un numero naturale k tale che 0 k n , i sottoinsiemi

di E di k elementi li diremo COMBINAZIONI di n oggetti a k a k e il numero di esse si dirà

 

n

COEFFICIENTE BIN OMIALE, indicato .

 

k

 

  D

n n n

! !

n , k

= = = =

TEOR 4 T3

. ( )

  − −

n k

( )!

k k k n k

! !( )!

  k !

Es

. Quante sono le cinquine del lotto? é

Svolg

. Sono tante quante i sottoinsiemi di 5 elementi di un insieme di 90 elementi, cio

  ⋅ ⋅ ⋅

90 90 89 88 87.....

= = 43949268

  ⋅ ⋅ ⋅ ⋅

5 1 2 3 4 5

 

OSS

. Cercando la cardinalità di un insieme, bisogna stare attenti a computare tutti gli elementi

una sola volta ciascuno. In particolare si ha il seguente. ∩

T EOR . 5 (ovvio) Se A è un insieme di a elementi e B di b elementi, e l'insieme A B

≥ ∪ + −

ha r 0 elementi, allora l'insieme A B ha a b r elementi..

≤

. Quanti sono i numeri naturali 1000 che sono multipli di 3 o di 5?

Es ⋅ ⋅ ⋅ =

. Fra o primi 1000 numeri naturali positivi, i multipli di 3 sono questi 333 : 3 1, 3 2....3 333 999

Svolg ⋅ ⋅ ⋅ =

Similmente i multipli di 5 s è costituito dai multpli

ono 200 : 5 1,5 2....5 200 1000. L'insieme intersezione

⋅ ⋅ ⋅ = + − =

di 15 minori o uguali a 1000, sono 66 :15 1,15 2....15 66 990. Quindi 333 200 66 467

 

n

n

∑ −

+ = ⋅

n k n k

TEOR . 6 (formula di Newton per la potenz a b a b

a del binomio) ( )  

k

 

=

k 0 + ⋅ + +

n a b a b a b

DIM ) si

. Applicando ripetutamente la proprietà distributiva al prodotto di binomi ( ) ( ).....(

− ∈ = =

k n k 0 0

ottiene la somma formale di monomi ciascuno uguale ad a b , per un k {0,1....

n

}(con a b 1),

n

∑

− −

+

k n k n k n k

allora detto C il numero di volte che a b è in quella somma formale, (

a b ) è C a b .

k k

= 0

k

− +

k n k prodotto di n binomi

Ogniuno degli a b si origina sceglieno a in k binomi a b del

   

n n

+ + − =

( ).....( ), e ciò si puà fare in modi, e negli altri binomi, e allora C .

a b a b b n k

   

k

k k

   

TEOR. 7    

n n

≤ ≤ =

Per 0 k n    

−

k n k

   

 

n

Dim in modi possiamo scegliere un sottoinsieme di k elementi di un insieme di n elementi.

 

k

 

 

n

In modi possimao scegliere un sottoinsieme di n element i. E' evidente che le due scelte

 

−

n k

 

sono sostanzialmente la stessa scelta, perché sciegliere un sottoinsieme di k elementi equivale a scegliere

il complementare che ha n - k elementi. − −

     

n n n

1 1

+

∈ ℕ

TEOR. 8 Per ogni n,k tali che n>1 e o>k>n, è =

     

−

k k k

1

     

DIM. A E

Sia l'insieme dei sottoinsiemi di k elementi di un insieme di n elementi.

 

n Y X y E

Otteniamo una ripartizione di A, che ha elementi , in due insieme e fissando un elemnto di ,

 

k

 

Y A E y X y

e ponendo in quegli elementi di (sottoinsiemi di ) che contengono , e in quelli che non contengono .

− −

   

n 1

1 n

Y hé si ottengono unendo { } agli sottoinsiemi

Gli elementi di sono perc y di k-q elementi di E - { y

}.

   

− −

k 1 k 1

   

 

n

Il calcolo degli si può fare con il , e anche con il e il ,

OSS. TEOR. 4 TEOR. 7 TEOR. 8

 

k

 

specialmente quando si usi il procedimento seguente.

DEF. Scrivendo i valori dei coefficienti binominiali verso destra al crescere di k e verso il basso

al crescere di n (e magari entrambi le linee), si ottiene una scrit tura formale che si chiama

TRIANGOLO DI TARTAGLIA (o DI PASCAL) 1

1 1

1 2 1