Principiul includerii si excluderii

Consideram:

  • O multime universala U astfel incat card(U)=N;
  • p1,p2,…, pr proprietati ale elementelor multimii U;
  • N0 numarul de elemente din multimea U care nu au nici una din proprietatile p1,p2,…, pr ;
  • N(pi1, pi2, ……..,pim) numarul elementelor din multimea U care au simultan proproietatile pi1,pi2,….,pim;

Atunci are loc egalitatea (principiul includerii si excluderii ):

Equation2

Exemplu:

Daca din cei 50  de angajati ai unei firme,  25 cunosc limba germana, 30 limba engleza si 20 limba franceza,  18 germana si engleza,  12 germana si franceza,  15 franceza si engleza, iar 8 toate cele trei limbi, atunci numarul de angajati ai firmei, care nu cunosc nici una din cele trei limbi straine, se poate calcula folosind principiul includerii si excluderii.

Intr-adevar vom avea:

50=N0 +N (G)+N (E)+N (F)-N (G,E)-N (E,F)-N (F,G)+N (G,E,F)⇔
50=N0 +25+30+20-18-15-12+8⇔ N0=17.

Academia de matematica aici:http://robeauty.ro

Reclame

Principiul lui Dirichlet

Acest principiu este intalnit sub diverse ale denumiri (principiul cutiei, principiul porumbeilor, etc.). Enuntul sau este urmatorul:

Fie n un numar natural nenul. Daca mai mult de n obiecte sunt distribuite in n containere, atunci cel putin un container contine cel putin 2 obiecte.

Exemplu:

Daca n pugilisti concureaza intr-un turneu care prevede cate un meci intre fiecare pereche de pugilisti, iar fiecare pugilist a pierdut cel putin un meci, atunci exista cel putin doi pugilisti cu acelasi numar de victorii ( n≥2 ).

Demonstratie:

Fiecare din cei n pugilisti a jucat n-1 meciuri si numarul de victorii obtinute este un numar din multimea { 0,1,….,n-2 }. Cum avem n pugilisti si card { 0,1,…,n-2 } = n-1, conform pricipiului lui Dirichlet, avem cel putin doi pugilisti cu acelasi numar de victorii.

Generalizare:Fie m,n doua numere naturale strict pozitive. Daca mai mult de m•n obiecte sunt distribuite in n containere, atunci cel putin un container contine cel putin m+1 obiecte.

Demonstratie:

Presupunem prin reducere la absurd ca cele n containere contin cel putin m obiecte. Atunci numarul de obiecte este cel mult egal cu n•mContradictie.

Academia de matematica aici:http://robeauty.ro

Vodafone

Regula sumei

Presupunem ca o procedura poate fi efectuata in m moduri:

  • in modul 1 exista n1 variante de efectuare a procedurii;
  • in modul 2 exista n2 variante de efectuare a procedurii;
  • ……………………………………………………………………..
  • in modul m exista nm variante de efectuare a procedurii;

Daca oricare doua din cele m moduri se exclud reciproc (nu au variante comune), atunci numarul total de variante prin care poate fi efectuata procedura este n1+n2+…..+nm.

Exemplu:

Un elev trebuie sa-si alega un proiect de programare din trei liste. Daca prima lista contine 7 proiecte, a doua lista 9, a treia lista 8 si orice proiect apare intr-o singura lista, atunci exista 7+9+8=24 variante de alegere a proiectului.

Academia de matematica aici:http://robeauty.ro

Regula produsului

Daca o procedura se poate decompune intr-o secventa de m proceduri astfel incat:

  • prima procedura se poate efectua in n1 moduri,
  • a doua procedura se poate efectua in n2 moduri,
  • …………………………………………………………..
  • a m-a procedura se poate efectua in nm moduri,

atunci procedura initiala se poate efectua in n1•n2•……•nm  moduri.

Exemplu:calculul cardinalului multimii:
Equation1

  • f (a1) poate fi ales in m moduri;
  • f (a2) poate fi ales in m moduri;
  • ……………………………………….
  • f (an) poate fi ales in m moduri;

Deci, conform regulii produsului, multime  multimea F are m n elemente.

Academia de matematica aici:http://robeauty.ro

Combinari cu repetitie

Consideram urmatoarea problema: avem n urne  numerotate  U1,….,Un  si k bile identice. Ne intereseaza in cate moduri se pot plasa cele k bile in cele n urne.

urne

Pentru gasirea raspunsului vom nota fiecare bila cu simbolul  „*” si marcam schimbarea urnei in care sunt plasate bilele(trecerea la o noua urna)  prin simbolul  „|„.

Exemple:

  1. **|*|*** – plasarea a 6 bile in 3 urne (2 bile in U1, 1 bila in U2 si 3 bile in U3).
  2. |*|* – plasarea a 2 bile in 3 urne (0 bile in U1, 1 bila U2 si 1 bila U3).
  3. **||**| – plasarea 4 bile in 4 urne (2 bile in U1, 0 bile in U2, 2 bile in U3, si 0 bile in U4).
  4. |||****|||**||| – plasarea 6 bile  in 10 urne (0 bile in U1,U2 si U3,  4 bile in U4, 0 bile in U5 si U6, 2 bile in U7, 0 bile in urnele U8,U9 si U10).

In cazul general problema se reduce la a determina in cate moduri putem plasa n-1 simboluri „|” pe k+n-1 pozitii. Obtinuem ceea ce se numeste k-combinari cu repetitie din n obiecte (urna se repeta – adica  folosesc urna eventual de mai multe ori pentru a pune in ea bile):

equation

Academia de matematica aici:http://robeauty.ro