CALCOLO COMBINATORIO Prof Sandro Pistori

STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO

CALCOLO COMBINATORIOProf Sandro Pistori


Qualche problema introduttivo

1. In quanti modi diversi 3 ragazzi di una compagnia di 5 amici si possono sedere su 3 poltrone libere di un cinema?

2. Quanti numeri di 4 cifre si possono comporre con le cifre 1,2,3,4,5,6?

3. Quanti anagrammi si possono comporre con le lettere della parola ROMA? E con la parola ALA?

4. Quanti terni si possono fare con i 90 numeri del Lotto?

5. In quanti modi diversi 7 caramelle identiche possono essere distribuite tra 4 bambini?

E se le caramelle fossero diverse?


Il calcolo combinatorio

il Calcolo combinatorio fornisce quegli

strumenti di calcolo per determinare il numero di raggruppamenti che si possono formare con un numero k di oggetti presi da un insieme contenente n oggetti ( n k ) secondo le modalità seguenti:

se k = n otterremo dei gruppi ordinati permutazioni.

k oggetti possono formare gruppi ordinati: disposizioni;

k oggetti possono formare gruppi non ordinati: combinazioni;


Problema 1

Raggruppare gli elementi a,b,c a gruppi di 2 con elementi che non possono ripetersi

1° modo COPPIE ORDINATE:

ab ac ba bc

ca cb

2° modoCOPPIE PER LE QUALI NON IMPORTA

L’ORDINE: ab ac bc

DISPOSIZIONI semplici (D3,2) COMBINAZIONI semplici (C3,2)


Problema 2

Raggruppare gli elementi a, b, c a gruppi di 2 con elementi che possono ripetersi

1° modo COPPIE ORDINATE:

aa ab ac bb ba bc cc ca cb

DISPOSIZIONI con ripetizione (D’3,2)

COMBINAZIONI con ripetizione (C’3,2)

2° modoCOPPIE PER LE QUALI NON

IMPORTA L’ORDINE: aa ab ac bb bc cc


Quindi…

I RAGGRUPPAMENTI POSSONO ESSERE:

SEMPLICI: quando gli oggetti sono tutti diversiCON RIPETIZIONE: quando gli oggetti vi figurano una o più

volte

E riassumendo:

Permutazioni semplici o con ripetizioneDisposizioni semplici o con ripetizione Combinazioni semplici o con ripetizione


Fattoriale

Il FATTORIALE di un numero intero positivo n è il prodotto di tutti gli interi positivi minori o uguali ad n

In simboli:

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

Si può quindi scrivere in modo ricorsivo

n! = n(n -1)!

Da cui nasce l’esigenza di definire 0!=1 infatti

1!=1(1-1)!=1 0!=1

Esempi:

5!=5 4 3 2 1 = 120

6!=6 5!= 6 120=720

10!=3.628.800

17!=35.568.7428.100.000


Gli anagrammi (PERMUTAZIONI)

Quanti sono gli anagrammi anche privi di senso della parola MARE?

4 3 2 1 !)...)(()(!

nnnnnP

1212441234

Corrisponde ai modi diversi di ordinare tutte e quattro le lettere che in questo caso sono diverse: permutazione semplice di n oggetti

Quanti sono gli anagrammi della parola MAMMA?

Ad esempio MAMAM MAMAM MAMAM MAMAM rappresentano sempre la stessa “parola”

Faccio finta che siano tutti diversi e poi li divido per tutti i possibili scambi che mi producono la stessa parola

!...!!)('!

!!!

!

nnP1023345

235


DISPOSIZIONI

Le disposizioni semplici di k oggetti presi da un gruppo di n oggetti sono

Dn,k= n(n-1)…(n-(k-1))= n(n-1)…(n-k+1)=

n(n-1)…(n.-k+1)(n-k)(n-k-1)…1/(n-k)!

Dn,k = n!/(n-k)!

Le disposizioni con ripetizione di k oggetti presi da un gruppo di n oggetti sono

D’n,k=n k


Quanti sono numeri di 4 cifre tutte distinte e non nulle nel sistema decimale?

Disposizione semplice D9,4 = 9!/(9-4)! = 9!/5!=3024

Quante sono le combinazioni possibile per un lucchetto a 5 cifre?

Quanti sono i sottoinsiemi di un insieme con n elementi?

Esempi

9 8 7 6

A B C D E F G H0 0 1 0 1 1 0 11 0 0 0 0 0 0 01 1 1 1 1 1 1 1…

= 2 n = D’2,n


COMBINAZIONI

Combinazioni semplici

Facciamo finta che sia una disposizione e poi dividiamo per il numero di scambi che danno origine allo stesso gruppo di k oggetti

ABCDEF: ABCD ACBD ADBC… sono le permutazioni di 4 elementi

Cn,k=Dn,k/ k! =

Combinazioni con ripetizione

kn

knkn

)!(!!

kkn

C kn1

,'

COEFFICIENTE

BINOMIALE


Esercizi

In quanti modi diversi si possono sedere 4 amici in un scompartimento da sei posti di un treno?

In quanti modi diversi possono venire occupati 6 posti di uno scompartimento di un treno da quattro persone?

Quante sono le diagonali di un poligono di n lati?

Quanti sono i punti che vengono individuati da 20 rette complanari a due a due non parallele?

Quanti sono i punti di intersezione che vengono individuati da 20 rette se 7 di esse sono parallele e le restanti no?


Il binomio di Newton


Ancora sui coefficienti binomiali


Un problema già visto…

Quanti sono i sottoinsiemi di un insieme A di n elementi?

Siano

k0 tutti gli insiemi con nessun elemento

k1 numero degli insiemi con un elemento

k2 numero degli insiemi con due elementi

…

kn numero degli insiemi con n elementi

Allora | P(A) | = k0+k1+k2+…+kn=

nnnnnnn ......

2101

211

nn 211 )(

CALCOLO COMBINATORIO Prof Sandro Pistori

Documents

Transcript of CALCOLO COMBINATORIO Prof Sandro Pistori