Principiul includerii-excluderii în combinatorică: calcularea cu ușurință a dimensiunii setului

Principiul includerii-excluderii este o tehnică folosită în combinatorică pentru a calcula dimensiunea unei mulțimi, împărțind-o în submulțimi mai mici și numărând intersecția acestora. Se bazează pe ideea că, dacă avem două mulțimi, A și B, și dorim să numărăm elementele care se află în ambele mulțimi, putem face acest lucru scăzând elementele care sunt doar în A din numărul total de elemente din A, și apoi adăugând înapoi elementele care sunt doar în B.

Mai formal, fie A și B două mulțimi și fie |A| fie numărul de elemente din A. Atunci, principiul includerii-excluderii afirmă că:

|A ∪ B| = |A| + |B| - |A ∩ B|

unde |A ∪ B| este numărul de elemente din uniunea lui A și B și |A ∩ B| este numărul de elemente care sunt atât în A cât și în B.

Ideea din spatele acestei formule este că putem calcula dimensiunea uniunii a două mulțimi numărând mai întâi numărul de elemente din fiecare set separat și apoi scăzând elementele care sunt doar într-una dintre mulțimi (adică, elementele din intersecție). Aceasta ne oferă numărul total de elemente din uniune, care este suma numărului de elemente din fiecare mulțime minus numărul de elemente care sunt doar într-una dintre mulțimi.

De exemplu, să presupunem că avem două mulțimi: A = {1, 2, 3} și B = {4, 5, 6}. Pentru a calcula dimensiunea unirii lor folosind principiul includere-excludere, mai întâi numărăm numărul de elemente din fiecare set separat:

|A| = 3
|B| = 3

În continuare, calculăm numărul de elemente care se află în ambele mulțimi numărând intersecția lor:

|A ∩ B| = 2 (deoarece 1 și 2 sunt în ambele seturi)

Acum putem folosi principiul includerii-excluderi pentru a calcula mărimea uniunii:

|A ∪ B| = |A| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6

Deci, dimensiunea uniunii dintre A și B este 6.

Principiul de includere-excludere are multe aplicații în combinatorică, cum ar fi numărarea numărului de permutări, combinații și soluții la ecuații. Este un instrument puternic pentru rezolvarea problemelor de numărare și poate fi folosit pentru a simplifica calcule complexe.