Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

dokaz?
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
Gost
PostPostano: 10:07 ned, 8. 2. 2004    Naslov: dokaz? Citirajte i odgovorite
Neka je S konačan skup, A1,...,An podskupovi od S, a za 0<=k<=n,
Sk=(Suma po |I|=k)|AI|, S0=|S|, a f=(k) (f>=(k)) broj elemenata iz S koji su u točno (barem) k podskupova Ai. Tada je

f=(k) = (Suma po t od k do n)(-1)^(t-k)*(t povrh k)*St

f>=(k) = (Suma po t od k do n)(-1)^(t-k)*(t-1 povrh k-1)*St


Da li mi netko može napisati dokaz?
U knjizi prof. Veljana(korolar 5, str 151) piše da to neposredno slijedi iz izraza za f=(0) i f=(S), ali ja ne vidim kako.
Neka je S konačan skup, A1,...,An podskupovi od S, a za 0<=k<=n,
Sk=(Suma po |I|=k)|AI|, S0=|S|, a f=(k) (f>=(k)) broj elemenata iz S koji su u točno (barem) k podskupova Ai. Tada je

f=(k) = (Suma po t od k do n)(-1)^(t-k)*(t povrh k)*St

f>=(k) = (Suma po t od k do n)(-1)^(t-k)*(t-1 povrh k-1)*St


Da li mi netko može napisati dokaz?
U knjizi prof. Veljana(korolar 5, str 151) piše da to neposredno slijedi iz izraza za f=(0) i f=(S), ali ja ne vidim kako.


[Vrh]
krcko
Forumaš nagrađen za životno djelo
Forumaš nagrađen za životno djelo


Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
Sarma = la pohva - posuda
655 = 759 - 104
PostPostano: 16:36 sri, 11. 2. 2004    Naslov: Citirajte i odgovorite
Ako je to korolar, pretpostavljam da slijedi iz teorema neposredno prije. Ajde pls napisi taj teorem. Nemam novu knjigu, a u staroj na str. 151 je nesto sasvim drugo.
Ako je to korolar, pretpostavljam da slijedi iz teorema neposredno prije. Ajde pls napisi taj teorem. Nemam novu knjigu, a u staroj na str. 151 je nesto sasvim drugo.



_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
Nesi
Inventar Foruma
(Moderator)
Inventar Foruma<br>(Moderator)


Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol: kućni ljubimac
Sarma: -
PostPostano: 17:52 sri, 11. 2. 2004    Naslov: Citirajte i odgovorite
[quote="krcko"]Ako je to korolar, pretpostavljam da slijedi iz teorema neposredno prije. Ajde pls napisi taj teorem. Nemam novu knjigu, a u staroj na str. 151 je nesto sasvim drugo.[/quote]

teorem 2 (poopceni FUI)
[b]Neka je [i]S[/i] konacni skup, a [i]f:2^S -> |R [/i]realna funkcija definirana na podskupovima od [i]S[/i]. Neka je [i]g:2^S -> |R [/i]definirana s
[i]g(T) = suma[/i] ([u]po X podskup od T[/u]) [i]f(X)[/i], za svaki [i]T podskup S[/i]
Tada je
[i]f(T) = suma[/i]([u]po X podskup od T[/u])[i](-1)^|T-X|*g(X)[/i], za svaki [i]T podskup od S[/i]
[/b]


nakon toga ide definiranje
[b]Na [i]S[/i] treba gledati kao na skup svojstava koje objekti (elementi) nekog konacnog skupa objekata [i]U[/i] imaju ili nemaju. Za podskup [i]T podskup S[/i], oznacimo:
[i]f=(T)[/i] := broj objekata iz U koji imaju tocno svojstva iz T (dakle, nemaju svojstva iz T komplement = S - T)
[i]f>=(T)[/i] := broj objekata iz U koji imaju barem svojstva iz T (dakle, imaju sva svojstva iz T i mozda jos neko)
[i]f<=(T)[/i] := broj objekata iz Z koji imaju najvise svojstva iz T (dakle, imaju samo neka svojstva iz T)[/b]

[b]Tada ocito vrijedi
[i]f<=(T) = suma[/i] [u](po X podskup od T)[/u][i] f=(X)[/i]
iz teorema 2 tada slijedi
[i]f=(T) = suma[/i] [u](po X podskup od T) [/u][i](-1)^|T-X| f<=(X)[/i]
isto je tako ocito
[i]f>=(T) = suma[/i] [u](po X nadskup od T)[/u] [i]f=(X)[/i]
[i]f=(T) = suma[/i] [u](po X nadskup od T)[/u] [i](-1)^|T-X| f>=(X)[/i]
[/b]
ako stavimo u zadnju [i]T=(prazan skup)[/i], tj brojimo sve objekte (iz U) koji nemaju nijedno svojstvo iz S, dobivamo
[b][i]f=(prazan skup)= suma [/i][u](po X)[/u] [i](-1)^|X| f>=(X)[/i][/b]

ako u trecu odozdola stavimo [i]T=S[/i] dobivamo
[b][i]f=(S) = suma[/i] [u](po X)[/u] [i](-1)^|S-X| f<=(X)[/i][/b]

e sad, iz ovog dvoje zadnjeg bi kao trebao slijediti korolar

hvala i u moje ime :g:
krcko (napisa):
Ako je to korolar, pretpostavljam da slijedi iz teorema neposredno prije. Ajde pls napisi taj teorem. Nemam novu knjigu, a u staroj na str. 151 je nesto sasvim drugo.


teorem 2 (poopceni FUI)
Neka je S konacni skup, a f:2^S → |R realna funkcija definirana na podskupovima od S. Neka je g:2^S → |R definirana s
g(T) = suma (po X podskup od T) f(X), za svaki T podskup S
Tada je
f(T) = suma(po X podskup od T)(-1)^|T-X|*g(X), za svaki T podskup od S



nakon toga ide definiranje
Na S treba gledati kao na skup svojstava koje objekti (elementi) nekog konacnog skupa objekata U imaju ili nemaju. Za podskup T podskup S, oznacimo:
f=(T) := broj objekata iz U koji imaju tocno svojstva iz T (dakle, nemaju svojstva iz T komplement = S - T)
f>=(T) := broj objekata iz U koji imaju barem svojstva iz T (dakle, imaju sva svojstva iz T i mozda jos neko)
f⇐(T) := broj objekata iz Z koji imaju najvise svojstva iz T (dakle, imaju samo neka svojstva iz T)

Tada ocito vrijedi
f⇐(T) = suma (po X podskup od T) f=(X)
iz teorema 2 tada slijedi
f=(T) = suma (po X podskup od T) (-1)^|T-X| f⇐(X)
isto je tako ocito
f>=(T) = suma (po X nadskup od T) f=(X)
f=(T) = suma (po X nadskup od T) (-1)^|T-X| f>=(X)

ako stavimo u zadnju T=(prazan skup), tj brojimo sve objekte (iz U) koji nemaju nijedno svojstvo iz S, dobivamo
f=(prazan skup)= suma (po X) (-1)^|X| f>=(X)

ako u trecu odozdola stavimo T=S dobivamo
f=(S) = suma (po X) (-1)^|S-X| f⇐(X)

e sad, iz ovog dvoje zadnjeg bi kao trebao slijediti korolar

hvala i u moje ime Mr. Green



_________________
It's not who you love. It's how.
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan