== include(page="template/taskheader" task_id="pinex") ==

h3. Enunţul principiului

A gamă foarte largă de probleme în cadrul concursurilor de informatică şi nu numai se rezolvă folosind principiul includerii şi excluderii. Deşi 'teoria':http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle poate părea greu de înţeles, mă voi strădui să ofer o explicaţie cât mai clară pentru cei interesaţi.

Fiind date $N$ multimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, este adevărată relaţia:
 
!problema/pinex?pinex.JPEG 80%!

Principiul enunţă faptul că fiind date $N$ multimi finite $A{~1~},A{~2~},A{~3~}...A{~n~}$, relaţia de mai jos este adevărată.

<tex> \displaystyle | \bigcup_{i=1}^{n} A_{i} | =  \sum_{i=1}^{n} | A_{i} | - \sum_{i,j:1 \le i < j \le n} |A_{i} \cap A_{j} | + \sum_{i,j,k:1 \le i < j < k \le n} |A_{i} \cap A_{j} \cap A_{k}| - \ldots + (-1)^{n-1} |A_{1} \cap \ldots \cap A_{n}| </tex>

h3. Aplicaţie

!problema/pinex?Inclusion-exclusion.png 50%!
 
Pentru demonstraţie, vom pleca de la cazul banal când avem doar două mulţimi, fie acestea $A$ şi $B$. Dacă sunt disjuncte, este clar că reuniunea lor se calculează după relaţia <tex>|A \cup B|=|A|+|B|</tex>. Ne rămâne de rezolvat cazul când $A$ şi $B$ au cel puţin un element în comun. Relaţia anterioară numără elementele comune din cadrul reuniunii de două ori(o dată pentru $A$ şi o dată pentru $B$), de aici apare nevoia să scădem numărul acestora din rezultat. Acest lucru este uşor de făcut, dat fiind faptul că pentru $A$ şi $B$, numărul de elemente comune celor doua mulţimi este <tex>|A \cap B|</tex>. Rezultă <tex>|A \cup B|=|A|+|B|-|A \cap B|</tex>
 
To be continued...
 
h2. Aplicaţie la teoria prezentă mai sus

Răspundeţi la $M$ întrebări de tipul: Dându-se două numere naturale $A$ şi $B$, să se determine numărul de numere mai mici ca $A$ şi prime cu $B$. Două numere naturale $(x,y)$ sunt prime între daca $cmmdc(x,y)=1$.