|
pretp da gledamo broj elemenata skupa
|A1 u A2 u .... u An|; Ai<=S; i = 1,...,n
Neka se x nalazi u točno k takvih podskupova, gdje je
0<k<=n
Lijeva strana:
S lijeve strane je skup, element u skupu može biti ili ne biti, tako da se pojavljuje 0 ili 1. S obzirom da je x element barem jednog skupa koji iz unije s lijeva, očito je on i element unije, pa je član skupa na lijevoj strani, pa se u njemu pojavljuje 1.
Desna strana:
m-ti element sume s desne strane je suma broja pojavljivanja od x u svim mogućim presjecima od točno m različitih Ai-ova (m=1,...,n)
x se pojavljuje u točno onim presjecima u kojima je član svih Ai-ova koji se sijeku. m Ai-ova koji se sijeku moramo izabrati iz skupa onih Ai-ova kojih je x član, a njih je [k povrh m]
Zbog toga je suma na desnoj strani
E(i=1...n) (-1)^(i+1)*[k povrh i]
Razvojem (-1+1)^k po binomnoj formuli dobivamo da je suma na desno jednaka 1.
pretp da gledamo broj elemenata skupa
|A1 u A2 u .... u An|; Ai⇐S; i = 1,...,n
Neka se x nalazi u točno k takvih podskupova, gdje je
0<k⇐n
Lijeva strana:
S lijeve strane je skup, element u skupu može biti ili ne biti, tako da se pojavljuje 0 ili 1. S obzirom da je x element barem jednog skupa koji iz unije s lijeva, očito je on i element unije, pa je član skupa na lijevoj strani, pa se u njemu pojavljuje 1.
Desna strana:
m-ti element sume s desne strane je suma broja pojavljivanja od x u svim mogućim presjecima od točno m različitih Ai-ova (m=1,...,n)
x se pojavljuje u točno onim presjecima u kojima je član svih Ai-ova koji se sijeku. m Ai-ova koji se sijeku moramo izabrati iz skupa onih Ai-ova kojih je x član, a njih je [k povrh m]
Zbog toga je suma na desnoj strani
E(i=1...n) (-1)^(i+1)*[k povrh i]
Razvojem (-1+1)^k po binomnoj formuli dobivamo da je suma na desno jednaka 1.
|
