Post on 12-Feb-2016
description
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
CALCOLO COMBINATORIOProf Sandro Pistori
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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?
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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;
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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)
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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?
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
Il binomio di Newton
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010 CALCOLO COMBIANTORIO
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 )(