combinatorica
DESCRIPTION
COMBINATORICA. Probleme de numarare. PERMUTARI. Daca A este o multime cu n elemente atunci orice multime ordonata formata din toate elementele sale se numeste permutare a lui A. Ex: A= {1,2,3} Permutarile lui A: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) - PowerPoint PPT PresentationTRANSCRIPT
COMBINATORICA
Probleme de numarare
PERMUTARI
• Daca A este o multime cu n elemente atunci orice multime ordonata formata din toate elementele sale se numeste permutare a lui A.
• Ex: A={1,2,3}
• Permutarile lui A: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)
• Numarul permutarilor lui A este n!
Exercitii
• In cate moduri se pot aranja numerele de la 1 la 100 astfel incat numerele pare sa fie pe pozitii impare si numerele impare pe pozitii pare?
• In cate moduri pot fi aranjate numerele de la 1 la n astfel incat numerele 1 si 2 sa fie vecine in aceasta ordine?
ARANJAMENTE
• Se numesc aranjamente de n elemente luate cate k (k<n+1) submultimile ordonate formate cu cate k elemente ale lui A.Numarul lor este
• Ex: A={1,2,3,4}• Aranjamentele de k=2 elemente ale lui A sunt:
(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(2,1),(3,1),(3,2),(4,2),(4,3).
)!(
!
kn
nAkn
Exercitii
• Din 10 discipline trebuie alcatuit un orar pentru o zi , format din 5 discipline. In cate moduri poate fi alcatuit orarul?
• Cate numere de 4 cifre distincte se pot alcatui folosind cifre din multimea A={1,2,…8} ?
• In cate moduri poate fi confectionat un steag tricolor, avand la dispozitie 7 culori?
COMBINARI
• Submultimile cu cate k elemente ale unei multimi cu n elemente se numesc combinari de n elemente luate cate k.Numarul lor este
• Ex:A={1,2,3,4} Combinarile lui A de cate k=2 elemente sunt: {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}
)!(!
!
knk
nC kn
Exercitii
• Intr-o clasa sunt 12 baieti si 15 fete. Se formeaza o echipa de schiori din 3 baieti si 4 fete. In cate moduri se poate forma echipa?
• Dintr-un pachet de 52 carti de joc se extrag 5 carti. In cate cazuri printre cele 5 carti se gaseste cel putin un as?
Exercitii
• Cate triunghiuri formeaza 8 puncte in plan, oricare trei necoliniare?
• Cate diagonale are un poligon convex cu n laturi?
• O multime are 25 elemente. Aflati numarul submultimilor cu cel mult 4 elemente.
Formule pentru combinari
• Numarul submultimilor cu k elemente este egal cu numarul submultimilor cu n-k elemente al unei multimi cu n elemente.
• Formula de recurenta a combinarilor:
knn
kn CC
111 kn
kn
kn CCC
Formulă
• -
• Numarul submultimilor cu 0,1,2,...,n elemente este egal cu numarul total de submultimi ale unei multimi cu n elemente, deci 2n.
nnnnn CCC 2...10
Binomul lui Newton
• Membrul drept al relatiei se numeste dezvoltarea binomului a+b la puterea n.
• Termenii din dezvoltare au forma generala:
nnn
nnn
nn
nn
nn
n bCabCbaCbaCaCba 11222110 ...
1 k
notkknk
n TbaC
Aplicație
• Arătați că există xn și yn naturale astfel încât .
• Arătați că perechea este soluție a ecuației .
• Se poate demonstra ca toate solutiile ecuatiei sunt perechile de mai sus.
332 nn
nyx
nn yx ,
13 22 yx
Soluție
• Înmulțind cele două relații obținem:
33...32232 110nn
nnn
nn
nn
nyxCCC
331...32232 110nn
nnn
nnn
nn
nyxCCC
22 31 nn yx
Permutări cu repetiție
• Avem n obiecte de k tipuri: n1 obiecte de tip 1, n2 obiecte de tip 2, ..., nk obiecte de tip k, astfel încât n1+n2+...+nk=n.
• O permutare a acestor obiecte se numeste permutare cu repetiție.
• Ex: Numerele sunt 2,3,3. Permutările sunt (2,3,3),(3,2,3),(3,3,2). Dacă numerele erau distincte aveam 3!=6 permutări, având însă și numere egale, sunt numai 3 permutări.
Numărul permutărilor cu repetiție
• Cele n1 elemente de tip 1 se pot plasa în moduri pe cele n poziții ale permutării, cele n2 elemente de tip 2 se pot plasa în moduri pe pozițiile rămase,..., cele nk obiecte de tip k se pot plasa în moduri.
• Numărul total de moduri va fi :
1nnC
2
1
nnnC
k
k
nnnnC 11 ...
!!...!
!
!0!
!......
!!
!
!!
!...
21
11
212
1
11... 11
2
1
1
kk
knnnn
nnn
nn nnn
n
n
nnn
nnnn
nn
nnn
nCCC k
k
Exercițiu
• Avem un suport pentru bile cu 12 găuri. În câte moduri putem aranja 3 bile albe , 5 bile negre și 4 bile roșii pe suport?
•
Aranjamente cu repetiție
• Avem un numar infinit de obiecte de tipurile t1,t2,...,tk. În câte moduri putem așeza obictele pe n poziții?
• Răspuns: pe fiecare poziție din cele n avem k variante de a pune un obiect, deci în total vor fi nk moduri.
• Ex: Un cuvânt de lungime 5 se poate forma din literele: A,B,C. Câte cuvinte se pot forma?
Combinări cu repetiție
• Avem un numar infinit de obiecte de tipurile t1,t2,...,tk. În câte moduri putem alege n obiecte dintre acestea ?
• Răspuns: Considerăm k+1 bare verticale: |||…|. Exceptând prima și ultima bară, între acestea se vor găsi n obicte și k-1 bare, deci n+k-1 simboluri. Între două bare consecutive vor fi obicte de același tip. Problema este să alegem k-1 poziții din cele n+k-1 în care să așezăm barele.
• Acest lucru se poate face în moduri nkn
kkn CC 111
Aplicații
• Fie n și k numere naturale nenule. Numărul n se poate scrie ca sumă de k numere naturale în moduri.
• Numărul de drumuri (mergând numai spre dreapta sau în sus ) de la origine până în punctul A(n,k) este
11
kknC
kknC