skripta (objasnjenje gradiva)

[.anchy.]

molila bih pomoć..kao dokazati zad 1.6 na 15-oj stranici?
i nebi li s lijeve strane trebalo još pomnožiti s i u primjeru 1.3.10 str 19?
i zad 1.12 sa strane 27?

evo i link na skriptu http://web.math.hr/nastava/komb/predavanja/predavanja.pdf

[pbakic]

Pa probaj po def bijekcije: (injekcija + surjekcija)
Pretp. da se dva skupa slikaju u isti skup => dokazi da moraju biti jednaki
Takodjer, dokazi da je surjekcija, (tj da za svaki skup postoji neki koji se slika u njega). Lako je vidjet da ako promatramo neki skup S imamo dva slucaja:
Ako S sadrzi n, onda se u njega slika skup S\n
ako S ne sadrzi n, onda se u njega slika S unija n

U ovom iducem bi trebao stajat "i"

A u zadnjem isto po def:
f je surjekcija =>
f^-1({y}) je neprazan (upravo zbog surjektivnosti)
f^-1({y}) i f^-1({x}) su disjunktni za x!=y (za to ne trebamo surjektivnost)
unija svih f^-1({y}) kad y prolazi po B je cijela domena (jer se svaki element iz A slika u neki iz B)

a ako vrijedi da je familija {f^-1({y}), y iz B} particija, onda je dovoljno primjetiti da ni za jedan y f^-1({y}) nije prazan skup (tj da postoji x iz A koji se slika u njega)

[miam]

moze li netko rijesiti zadatak 1,8 ili 1,9 iz skripte? a moze i oba

_________________
<3

[pbakic]

1.8:
Ova tvrdnja, kolko vidim, ne vrijedi... Npr, za n=5 i r=2 ocito ne valja
Trebalo bi staviti da i ide od 1 do r+1
Tada se jednakost (koja vrijedi) moze kombinatorno argumentirati ovako:
s desne strane, ocito, biramo r clanova n-clanog skupa.
lijeva strana je rastav po slucajevima:
poredamo clanove skupa (pridruzimo im indekse 1,...,n)
onda gledamo slucajeve po tom koji je indeks najmanjeg clana koji ne sudjeluje u podskupu.
Ako je to indeks i, onda smo odabrali vec sve prije njega (i-1 element) pa trebamo od preostalih (m-i) odabrati (r-(i-1))=r-i+1. Posto su slucajevi disjunktni, na kraju samo zbrojimo sve te mogucnosti i vidimo da smo dobili sumu na lijevoj str.

1.9:
Slicna prica, s desne strane biramo n+1 element od n+k+1 clanog skupa.
S lijeve strane rastavimo po slucajevima (promatramo najveci indeks od clanova koji sudjeluju)
Ako je to indeks n+i+1 (ne moze biti manji ili jednak n jer onda nemamo n+1 element), onda za preostale clanove podskupa moramo izabrati n elemenata od n+i (to su ovi sa manjim indeksima). To nam daje sumande na lijevoj strani

[miam]

e puuuno ti hvala

_________________
<3

[Tomy007]

Može li netko riješiti zadatak 2.3 iz skripte iz predavanja, to je onaj zadatak sa (2n-1)!!.

[Flame]

[meda]

jel bi mogo netko rjesit zadatak 3.6.? hvala
http://web.math.hr/nastava/komb/predavanja/predavanja.pdf

[.anchy.]

mi može netko objasniti zadnju rečenicu na str 53. "neka je X univerzalan skup i...", i ovu jednakost sa presjekom..
tu isto nisam sigurna kužim li što su Ai-ovi, npr.za X={1,2,3}, je li onda npr.A1={1,2} i A2={3}, ili može biti da je A1={1,2} i A2={2,3},tj.moraju li biti disjunktni?

edit:never mind,skužila sam.. pretp.da sam dobro shvatila,znači Ai-ovi nemoraju biti disjunktni i nemoraju uopće u uniji davat cijeli X?

[Tomy007]

[frutabella]

Da li bi mi netko mogao rastumaciti alogoritme na 30 str.
http://web.math.hr/nastava/komb/predavanja/predavanja.pdf

Ne znam zaista na koji nacin djeluju, sasvim su mi nejasno napisani. :S

[krcko]

@meda, anchy, Tomy:
Ako se pripremate za prvi kolokvij, malo ste se pogubili. Formula ukljucivanja-ukljucivanja i teorija grafova bit ce tek na drugom kolokviju. To cu tumaciti na predavanju pa cu sad preskociti.

@frutabella:
Recimo da generiras podskupove od X={1,2,3} drugim algoritmom na str. 30. Pocnes od praznog skupa:

Koji je najveci element iz X koji nije u trenutnom podskupu? 3. Ubacim ga i izbacim sve elemente iza njega (nema ih) i tako dobijem drugi podskup:
{3}
Sad ponavljam. Najveci element koji nije u podskupu je 2. Ubacim ga i izbacim sve poslije njega (3) pa dobijem
{2}
Ubacim 3, izbacim nista:
{2,3}
Ubacim 1, izbacim sve poslije njega (2,3) itd:
{1}
{1,3}
{1,2}
{1,2,3}
Sad su svi elementi u podskupu pa stanem. Nasao sam sve podskupove.

Probaj sama ispisati sve 3-podskupove od {1,2,3,4,5} onako kako bi radio prvi algoritam na str. 31!

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[frutabella]

Evo tek sad,nakon tri dana razmisljanja, skontala sam algoritam, puno jasnije raspisan nego sto je napisan u skripti (meni skroz nejasan u skripti).

Također ovaj drugi algoritam mi nikako ne ide:

Npr. Trazit cu 3-podskupove od {1,2,3,4}, znaci n=4, k=3


Kako kaze skripta:

Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.

SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je

------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,

to znaci, da je taj i=3, i s tim y3+1=4 nije element iz trenutnog Y


------> povecaj yi za jedan, stavi yj=j za j< i i vrati novi Y

to znaci y3+1=4, a j < i jesu j=1,2 < i=3, i stavim y1=1, y2=2,

da li onda ovo znaci vratiti novi Y ----> Y= {1,2,4} ????

Ali onda drugi krug opet ne znam, (jer pretpostavljam ni ovo nije dobro), jer sljedeci i takav da yi+1 nije element iz trenutnog Y, je i=2, jer y2+1=3, a on nije element trenutnog Y, a kako onda odrediti yj, kad je samo j=1 < i=2 ???

[krcko]

Dobro je! Sad imas ovaj podskup:
{1,2,4}
Znaci y1=1, y2=2, y3=4. Kao sto si napisala i=2, stavimo y2=3 i y_j=j za j<2 (tj. y1=1 sto vec je). Sljedeci podskup je
{1,3,4}
Sad je i=1, dobijemo
{2,3,4}
i gotovi smo ako je n=4. Ako je n=5 imali bismo i=3, y3=5 i stavimo y_j=j za j<3 (tj. y1=1 i y2=2):
{1,2,5}
Kako ide dalje?

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[frutabella]

{ 1, 3, 5}

{2, 3, 5}

{1, 4, 5}

{2, 4, 5}

{3, 4, 5}



Nadam se da je dobro.

Sad me samo jos zanima ovaj zadnji dio algoritma koji kaze:

----> ovaj postupak propada ukoliko je i=k, yk=n; u tom slucaju

Y={ n-k+1, ..., n} je zadnji skup

A ja sam skroz u prvom koraku imala i=3, sto je jednako k=3, i y3=4 ?
(ma da je istina da mi je zadnji skup ono sto veli zadnji dio alg)


Podsjetnik:
Prvi podskup je Y={1, ..., k}, u nasem slucaju to je valjda, recimo Y={1,2,3}.

SLJEDECI PODSKUP poslije Y={y1=1,y2=2,y3=3,} (gdje je 1<2<3) je

------> nađi prvi i takav da je yi + 1 nije elemenz iz trenutnog Y,

to znaci, da je taj i=3, i s tim y3+1=4 nije element iz trenutnog Y

[pedro]

kaj samo ta dva algoritma dolaze u obzir za kolokvij?

[krcko]

Ne, dolaze u obzir i drugi.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[pedro]

http://web.math.hr/nastava/komb/predavanja/predavanja.pdf str 37,
jasno mi je do ove rečenice:

Popločavanja (n + 1)–ploče kod kojeg koristimo barem jednu dominu
tako da zadnja domina pokriva mjesta (k+1) i (k+2) ima točno Jk.

oke, domina treba zauzeti dva mjesta k+1 i k+2, ali zašto onda ima točno Jk popločavanja??

[Phoenix]

Zato što, ako je zadnja domina na ploči na mjestima [tex](k+1)[/tex] i [tex](k+2)[/tex], sve poslije nje su kockice (sve do [tex](n+1)[/tex] pozicije). Međutim, mjesta od [tex](1)[/tex] do [tex](k)[/tex] mogu biti popunjena kako god želiš, stoga i imaš [tex]J_k[/tex] načina za ovaj slučaj.
I, naravno, ovisno o tome gdje se nalazi posljednja domina, napiši odgovarajuću sumu po [tex]k[/tex] i imaš rješenje.

[Lepi91]

znam da je vjerojatno svima dosta ovih pitanja o algoritmima i generiranju,ali jos jedno...
hocemo li mi u kolokviju trebati napisati svoj algoritam i onda po njemu odrediti kako bi isao poredak koji on generira ili cemo mi dobiti zdani algoritam pa cemo trebat odredit kako on generira jer ako sam ja shvatio postoje dvije vrste algoritma za podskupove i k-clane podskupove koji rade drugacijim redoslijedom...pa recimo u kolkviju 2007. ako se ne varam ima jedan zadatak sa generiranjem i sad jel tamo mi biramo koji algoritam koristimo? jesam to dobro shvatio,mi odaberemo koji cemo algoritam i njega napisemo i po njemu radimo

_________________
tko rano rani,malo spava