Malo Kombinatorike

Malo Kombinatorike 29.06.2011. u 00:46 · pre 186 meseci #1

Imam sljedeci problem imam opstu formulu ukljucivanja i iskljucivanja, $|A_1 \cup A_2 \cup \cdots \cup A_n|= \sum_{j=1}^n|A_j|- \sum_{1 \le i<j \le n}|A_i \cap A_j|+\sum_{1\le i<j<k\le n}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|$ .
I sad na primer kad imam da je $n=2$ ,lako odredim formulu,znaci: $|A_1 \cup A_2|=\sum_{j=1}^2|A_j|-\sum_{1\le i<j\le 2}|A_i \cap A_j|\Longrightarrow |A_1 \cup A_2|=|A_1|+|A_2|-|A_1 \cap A_2|$ ,Ovaj sledeci deo ,
$\sum_{1\le i<j<k\le n}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|$ ,otpada,jer za $n=2$ ,ne moze biti ispunjen uslov $1\le i<j<k\le n$ ,i to je jasno kao dan.

Ali problem nastaje kad imam za $n=3$ ili neki veci broj,za $n=3$ znam donekle da uradim,znaci imam sledece:
$|A_1 \cup A_2 \cup A_3|=\sum_{j=3}^3|A_j|-\sum_{1 \le i<j \le 3}|A_i \cap A_j|+\sum_{1\le i<j<k\le 3}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap \cdots \cap A_3|$ .
$\sum_{j=3}^3|A_j|\Longrightarrow |A_1|+|A_2|+|A_3|$
$\sum_{1 \le i<j \le 3}|A_i \cap A_j|\Longrightarrow -\left(|A_1 \cap A_2|+|A_1 \cap A_3|+|A_2 \cap A_3|\right)$

Ali sad ovaj deo koji me najvise buni jeste $\sum_{1\le i<j<k\le 3}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|$ ,znam da iz ovoga prethodnog treba da dobijem $|A_1 \cap A_2 \cap A_3|$ .
Ali ne znam kako,Evo sta ja dobijam,relacija $1\le i<j<k\le 3$ ,je zadovoljena samo kad je $k=n$ ,i tada postoji jedna jedina mogucnost a to je da : $\sum_{1\le i<j<k\le 3}|A_i \cap A_j \cap A_k| \Longrightarrow|A_1 \cap A_2 \cap A_3|$ ,Ali sta da radim sa ovim: $-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|$ .

Znaci za $n=3$ ,treba da dobijem $|A_1 \cup A_2 \cup A_3|=|A_1|+|A_2|+|A_3|-|A_1 \cap A_2|-|A_1 \cap A_3|-|A_2 \cap A_3|+|A_1 \cap A_2 \cap A_3|$ ,Ali nemogu zbog ovog $-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|$ ,nemogu to da dobijem.
Moze malo pojasnjenja?

_{[Ovu poruku je menjao edisnp dana 29.06.2011. u 02:04 GMT+1]}

_{[Ovu poruku je menjao edisnp dana 29.06.2011. u 02:04 GMT+1]}

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Malo Kombinatorike 29.06.2011. u 02:01 · pre 186 meseci #2

Očigledno si dobio. Izraz

-...+(-1)^n-1|A₁A₁...A_n|

za n=3 tumačiš tako što odrediš

(-1)^n-1|A₁A₁...A_n|

a to si odredio.

Minus - ispred ... znači da se u formuli sledeći član uzima kao negativan. A izraz

(-1)^n-1|A₁A₁...A_n|

daje opšti član za sve preostale članove (uključujući i taj koji je označen sa minus).

Re: Malo Kombinatorike 29.06.2011. u 02:13 · pre 186 meseci #3

Ja ne vidim da sam dobio ovaj $-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|$ ,clan
i koliko sam shvatio za $n=3$ ,sledeci clan,tj.ovaj: $-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|$ nepostoji.

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Malo Kombinatorike 29.06.2011. u 03:15 · pre 186 meseci #4

To je član

(-1)^3-1|A₁A₂A₃| = |A₁A₂A₃|

Re: Malo Kombinatorike 29.06.2011. u 06:15 · pre 186 meseci #5

Okey, $-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3|=|A_1 \cap A_2 \cap A_3|$ ,to jeste,
ali imam da je i $\sum_{1\le i<j<k\le 3}|A_i \cap A_j \cap A_k|=|A_1 \cap A_2 \cap A_3|$

I kako sad posto imam da je $\sum_{1\le i<j<k\le 3}|A_i \cap A_j \cap A_k|-\cdots+(-1)^{3-1}|A_1 \cap A_2 \cap A_3| \Longrightarrow |A_i \cap A_j \cap A_k|-|A_i \cap A_j \cap A_k|$ ili sta .

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Malo Kombinatorike 29.06.2011. u 09:38 · pre 186 meseci #6

Dakle, dobio si, kao sto su ti ljudi vec rekli.

$\Big{|}A_1 \cup A_2 \cup \cdots \cup A_n \Big{|} = \sum_{1 \leq i \leq n} \Big{|}A_i \Big{|} - \sum_{1\leq i < j \leq n} \Big{|}A_i \cap A_j \Big{|} + \sum_{1\leq i < j < k \leq n} \Big{|}A_i \cap A_j \cap A_k \Big{|} + \cdots + (-1)^{n-1} \Big{|}A_1 \cap A_2 \cap \cdots \cap A_n \Big{|}$

Za $n=3$ poslednji clan postaje

$\Big{|}A_1 \cap A_2 \cap A_3 \Big{|}$

A to je u stvari ova treca suma. I onda ovoga posle tri tacke nema. Gotovo. :)

Na kraju imas da je:

$\Big{|}A_1 \cup A_2 \cup A_3 \Big{|} =\Big{|}A_1 \Big{|} + \Big{|}A_2 \Big{|} + \Big{|}A_3 \Big{|} - \Big{|}A_1 \cap A_2 \Big{|} - \Big{|}A_1 \cap A_3 \Big{|} - \Big{|}A_2 \cap A_3 \Big{|} + \Big{|}A_1 \cap A_2 \cap A_3 \Big{|}$

Potpis

If you can't explain it simply, you don't understand it well enough. A. Einstein

Re: Malo Kombinatorike 29.06.2011. u 10:11 · pre 186 meseci #7

Da li sam sad dobro radio za $n=4$ ,Evo sta ja dobijam:
$\sum_{j=1}^4\left|A_j\right|=|A_1|+|A_2|+|A_3|+|A_4|$

\sum_{1\le i<j \le 4} \left|A_i \cap A_j|=|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2
\cap A_3|+|A_2 \cap A_4|+|A_3\cap A_4|

$\sum_{1\le i<j<k\le 4}|A_i \cap A_j \cap A_k|=|A_1\cap A_2 \cap A_3|+|A_1\cap A_3 \cap A_4|+|A_1 \cap A_2 \cap A_4|+|A_2\cap A_3 \cap A_4|$
$-\cdots+(-1)^{3-1}|A_1 \cap \cdots \cap A_n|=-|A_1 \cap A_2 \cap A_3 \cap A_4|$ .

I konacna formula bi glasila: $\left|A_1\cup A_2\cup A_3\cup A_4\right|=|A_1|+|A_2|+|A_3|+|A_4|-\left(|A_i \cap A_j|+|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2 \cap A_3|+|A_2 \cap A_4|+|A_3\cap A_4|\right)+|A_1\cap A_2 \cap A_3|+|A_1\cap A_3 \cap A_4|+|A_1 \cap A_2 \cap A_4|+|A_2\cap A_3 \cap A_4|-|A_1 \cap A_2 \cap A_3 \cap A_4|$

_{[Ovu poruku je menjao edisnp dana 29.06.2011. u 13:09 GMT+1]}

Potpis

حياتي هو العلم بلدي (الرياضيات)

Re: Malo Kombinatorike 29.06.2011. u 11:07 · pre 186 meseci #8

Jeste uz primedbu da u poslednjoj formuli sa leve strane fali znak za uniju.

Re: Malo Kombinatorike 29.06.2011. u 12:10 · pre 186 meseci #9

Hvala vam puno na pomoci,ispravio sam.

Potpis

حياتي هو العلم بلدي (الرياضيات)

Srodne teme