Forum@DeGiorgi :: Pogledajte temu

2. zadaca

through

FAQ

[^/[Print]\]
Idite na 1, 2, 3 Sljedeće :| |:
Forum@DeGiorgi -> Diskretna matematika

#1: 2. zadaca Autor/ica: gaston,

Postano: 20:35 sub, 1. 11. 2008
—
bok, molio bih (za pocetak Wink

) pomoc oko 9. b) zadatka iz zadace, koji glasi:

neka je dan skup

elemenata,

odredite koliko ima bijekcija

koje su same sebi inverz i nemaju fiksnih tocaka.

ovo "da nemaju fiksnih tocaka" znaci

, jel da? to znaci da je iskljucena bijekcija f(1)=1, f(2)=2,... itd.

znaci da bi jedna bijekcija koja je sama sebi inverz, i bez fiksnih tocaka, ako uzmemo A={1,2,3,4}, bila npr. f(1)=3, f(2)=4, f(3)=1, f(4)=2.

E sad, kako prebrojati sve takve bijekcije na n-clanom skupu? Ja to stvarno ne znam

zahvaljujem

#2: Re: 2. zadaca Autor/ica: goranm,

Postano: 20:51 sub, 1. 11. 2008
—

gaston (napisa):

znaci da bi jedna bijekcija koja je sama sebi inverz, i bez fiksnih tocaka, ako uzmemo A={1,2,3,4}, bila npr. f(1)=3, f(2)=4, f(3)=1, f(4)=2.

Ovdje si na dobrom tragu. Pogledaj npr. što se dešava sa elementima 1 i 3 skupa A. f(1)=3 i f(3)=1, to jest, skup {1,3} se mora preslikti u samog sebe, ali tako da nema fiksnih točaka. Ista stvar vrijedi za bilo koji dvočlani podskup tvog skupa A.

Ako još ne vidiš što bi trebao prebrojati, probaj isti "pokus" napraviti kada je A={1,2,3,4,5} i A={1,2,3,4,5,6}. Iz toga ćeš zaključiti nešto o (ne)parnosti broja n i što trebaš prebrojati da bi dobio broj traženih bijekcija.

#3: Re: 2. zadaca Autor/ica: gaston,

Postano: 21:05 sub, 1. 11. 2008
—

goranm (napisa):

ahaa, kuzim. ustvari trazim broj svih mogucih particija n-clanog skupa na (disjunktne) dvoclane podskupove. ali ako je n neparan, onda ce, nakon sto svih (n-1) elemenata bude spareno, ostati jedan element koji ce se morati preslikati u samog sebe, a takve funkcije ne uzimamo u obzir. dakle, broj takvih funkcija je 0 za n neparan (jer nuzno postoji fiksna tocka)

e sad, ako je n paran, onda je sa Stirlingovim brojem druge vrste

dan broj particija n-clanog skupa na k dijelova, pri cemu je ovdje

.

ne? Smile

#4: Re: 2. zadaca Autor/ica: goranm,

Postano: 21:18 sub, 1. 11. 2008
—

gaston (napisa):

dan broj particija n-clanog skupa na k dijelova, pri cemu je ovdje

.

ne? Smile

Jeste. Osim konačnog rješenja. Npr. jedna 2-particija četveročlanog skupa A={1,2,3,4} je {{1,2,3},{4}}, a takve particije ne želimo brojati pa će S(4,2) prebrojati više nego što želimo.

Broj rastava n-članog skupa na dvočlane podskupove nije teško izbrojati. Prvo odabereš jedan dvočlani podskup, pa drugi od ostatka, pa treći....neke stvari se ponavljaju pa se mora podijeliti s nečim i tak... Smile

Uostalom, mislim da eksplicitnu formulu za Stirlingov broj druge vrste još niste radili.

#5: Re: 2. zadaca Autor/ica: gaston,

Postano: 21:38 sub, 1. 11. 2008
—

goranm (napisa):

Broj svih 2-particija n-članog skupa nije teško izbrojati.

jao, pa da Exclamation

imamo skup od n elemenata, odaberemo dva, npr. a i b, i uzmemo f(a)=b, f(b)=a. ostane nam (n-2) elementa, od kojih biramo opet bilo koja 2, dakle ukupan nacin odabira je:

dakle, rjesenje je:
0, za n neparan

, za n paran

puno puno hvala na pomoci! karma++

reci ako je nesto krivo Smile

#6: Autor/ica: rafaelm, Lokacija: Zagreb

Postano: 21:47 sub, 1. 11. 2008
—
Nije važan redosljed kojim biramo te elemente, pa bi tribalo još malo dijeliti.

#7: Re: 2. zadaca Autor/ica: goranm,

Postano: 21:50 sub, 1. 11. 2008
—

gaston (napisa):

goranm (napisa):

Broj svih 2-particija n-članog skupa nije teško izbrojati.

jao, pa da Exclamation

Samo da napomenem da sam ja pogrešno napisao u ovom citatu unutar citata (ispravio sam u originalnom postu) Smile

. Ne računamo broj 2-particija n-članog skupa nego broj rastava n-članog podskupa na (disjunktne) dvočlane skupove.

Citat:

puno puno hvala na pomoci! karma++

reci ako je nesto krivo Smile

rafaelm je napomenuo još jednu sitnicu koja nedostaje Smile

#8: Re: 2. zadaca Autor/ica: rafaelm, Lokacija: Zagreb

Postano: 21:53 sub, 1. 11. 2008
—

goranm (napisa):

Ne računamo broj 2-particija n-članog skupa nego broj rastava n-članog podskupa na (disjunktne) dvočlane skupove.

Ako se dobro sjećam, mi smo to zvali 'sparivanje', na vježbama iz diskretne.

#9: Re: 2. zadaca Autor/ica: goranm,

Postano: 22:07 sub, 1. 11. 2008
—

rafaelm (napisa):

Ako se dobro sjećam, mi smo to zvali 'sparivanje', na vježbama iz diskretne.

To je inače "broj transpozicija", a transpozicija je ciklus duljine 2. Smile

A kako postoji formula za broj permutacija od n elemenata cikličkog tipa (c1,c2,...,c_n), tada iz te formule za ciklički tip (0,n/2,0,...,0) odmah slijedi rješenje zadatka. Smile

#10: Autor/ica: gaston,

Postano: 22:23 sub, 1. 11. 2008
—

rafaelm (napisa):

Nije važan redosljed kojim biramo te elemente, pa bi tribalo još malo dijeliti.

zaista!

mnozenje, tj. princip produkta koristimo kada trazimo broj uredjenih n-torki, a redoslijed dvoclanih skupova nam je u ovom zadatku nebitan. dakle, ako je n paran, onda ima

parova elemenata iz A...

da li je onda konacno rjesenje

#11: Autor/ica: goranm,

Postano: 22:35 sub, 1. 11. 2008
—

gaston (napisa):

da li je onda konacno rjesenje

Je.

Sad možeš vidjeti da je to isto kao broj permutacija od n elemenata cikličkog tipa

, to jest broj načina na koji n-člani skup možemo rastaviti u transpozicije iliti cikluse duljine 2 (ako rastavljamo samo na cikluse duljine 2, tada takvih ciklusa mora biti točno n/2, a svih ostalih očito mora biti 0).

Općenita formula za broj permutacija od n elemenata cikličkog tipa

a u našem slučaju to je

#12: Autor/ica: rafaelm, Lokacija: Zagreb

Postano: 22:38 sub, 1. 11. 2008
—

gaston (napisa):

da li je onda konacno rjesenje

Jep. Ali možeš vidjeti da je to umnožak svih neparnih brojeva manjih od n, jer su u nazivniviku svi parni manji ili jednaki n, a u brojniku n!. Pa rezultat možeš ljepše zapisati:

#13: Autor/ica: Cobs, Lokacija: Geto

Postano: 13:47 ned, 2. 11. 2008
—
jel bi mogo netko poslat rjesenja petog zadatka jer mi se cini da dobivam neka totalno kriva rjesenja...hvala

u biti upravo sam shvatio da je zadatak totalno krivo postavljen pa bih zamolio asistente ako sad to procitaju da izuzmu taj zadatak iz bodovanja.

#14: Autor/ica: goranm,

Postano: 17:11 ned, 2. 11. 2008
—
A što točno je krivo postavljeno? Smile

#15: Autor/ica: gaston,

Postano: 19:57 ned, 2. 11. 2008
—
evo, ja bih upao sa jednim drugim pitanjem, vezanim za zadatak 9.c)

neka je dan skup

elemenata. odredite koliko ima rastucih funkcija

e sad, pretpostavljam da smijemo, bez smanjenja opcenitosti, uzeti

, pa ce za svaku rastucu funkciju

vrijediti

, pri cemu su

vidljivo je naprimjer da ako je, npr.

, onda je nuzno

,
odnosno

, za

ali ne znam kako ovo svojstvo icemu pomaze.

nemam pojma kako prebrojati sve rastuce funkcije sa

i bio bih izuzetno zahvalan na svakoj pomoci Very Happy

#16: Autor/ica: krcko,

Postano: 20:13 ned, 2. 11. 2008
—
Nije bas jednostavno. Probaj prvo prebrojati strogo rastuce funkcije, laske je. Vise onako za zagrijavanje (nije od velike koristi za tvoj zadatak Smile

)

Za rastuce funkcije treba pogledati prirast u svakoj tocki: f(i)-f(i-1). Moze se napraviti bijekcija s necim sto se moze prebrojati pomocu "kuglica i stapica".

Sad sam primijetio da su domena i kodomena isti skup pa su strogo rastuce funkcije trivijala. Zadatak se inace moze rijesiti za f:{1,..,m}->{1,..,n}.

#17: Autor/ica: Cobs, Lokacija: Geto

Postano: 20:46 ned, 2. 11. 2008
—

goranm (napisa):

A što točno je krivo postavljeno? Smile

pa pod (a) nam kaze da trebamo podijeliti zadatke ( nije nuzno da svaki student dobije zadatak ), tako da svaki od 30 zadataka dobije tocno jedan student, a pod (d) nam kaze da isto treba podijeliti zadatke( nije nuzno da svaki student dobije zadatak ), ali da niti jedan student ne smije dobiti dva ista zadatka?? pa zar mozemo iste zadatke dijeliti vise puta ako nam to i nije posebno napomenuto kao u (b)?
onda bi pod (a) imao beskonacno mnogo rjesenja, a pod (d) bi trebao moci podijeliti svakom studentu svih 30 zadatka, a i ne moram podijeliti ako ne zelim? pa bih molio objasnjenje... neznam dal se to samo meni događa, ali na svakoj zadaci ima jedan takav zadatak di trebam prvo dešifrirati dosta vremena na što se tu misli, a i kada rjesim zadatak nisam potpuno siguran dal je to tocno rjesenje jer nisam nikad siguran da li se baš to tražilo od mene.

#18: Autor/ica: Atomised, Lokacija: Exotica

Postano: 22:29 ned, 2. 11. 2008
—

Cobs (napisa):

goranm (napisa):

A što točno je krivo postavljeno? Smile

I pod a) je napomenuto da ne smiješ iste zadatke dijeliti više puta različitim studentima (tj. piše da svaki zadatak mora dobiti točno jedan student).
Problem je u tome što napomena pod d) ("niti jedan student ne smije dobiti dva ista zadatka") sugerira da se, ako nije napomenuto drugačije, isti zadatak može dijeliti više puta jednom te istom studentu.

Zamisli da dođeš na test i dobiješ, lajk, beskonačno istih zadataka. Very Happy

Ma mislim da je pod d) jednostavno neka greška.

#19: Autor/ica: Cobs, Lokacija: Geto

Postano: 22:34 ned, 2. 11. 2008
—

Atomised (napisa):

Zamisli da dođeš na test i dobiješ, lajk, beskonačno istih zadataka. Very Happy

Ma mislim da je pod d) jednostavno neka greška.

Na to sam tocno i mislio.

#20: Autor/ica: Atomised, Lokacija: Exotica

Postano: 0:11 pon, 3. 11. 2008
—
@Cobs: Znam. Smile

Nego, kako treba riješiti 4. zadatak? Ja znam ciklički zapisati permutaciju, ali ga i dalje baš ne kužim. Very Happy

Forum@DeGiorgi -> Diskretna matematika

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Idite na 1, 2, 3 Sljedeće :| |: Stranica 1 / 3.