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

2. zadaca
WWW:
Idite na 1, 2, 3  Sljedeće
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
gaston
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 07. 2008. (15:42:28)
Postovi: (21)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 20:35 sub, 1. 11. 2008    Naslov: 2. zadaca Citirajte i odgovorite

bok, molio bih (za pocetak ;)) pomoc oko 9. b) zadatka iz [url=http://web.math.hr/nastava/komb/zadace/zadaca2.pdf]zadace[/url], koji glasi:

neka je dan skup [latex]A[/latex] od [latex]n[/latex] elemenata,

odredite koliko ima bijekcija [latex]f:A \rightarrow A[/latex] koje su same sebi inverz i nemaju fiksnih tocaka.



ovo "da nemaju fiksnih tocaka" znaci [latex](\forall a \in A)[/latex], [latex]f(a) \neq a[/latex], 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? :neznam:

zahvaljujem
bok, molio bih (za pocetak Wink) pomoc oko 9. b) zadatka iz zadace, koji glasi:

neka je dan skup od 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



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 20:51 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="gaston"]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.[/quote]
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.
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.



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
gaston
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 07. 2008. (15:42:28)
Postovi: (21)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 21:05 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="goranm"]
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.[/quote]

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 [latex]S(n,k)[/latex] dan broj particija n-clanog skupa na k dijelova, pri cemu je ovdje [latex]k=\frac{n}{2}[/latex].

ne? :)
goranm (napisa):

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.


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



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 21:18 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="gaston"]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 [latex]S(n,k)[/latex] dan broj particija n-clanog skupa na k dijelova, pri cemu je ovdje [latex]k=\frac{n}{2}[/latex].

ne? :)[/quote]
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...:)

Uostalom, mislim da eksplicitnu formulu za Stirlingov broj druge vrste još niste radili.
gaston (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

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.



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
gaston
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 07. 2008. (15:42:28)
Postovi: (21)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 21:38 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="goranm"]
Broj svih 2-particija n-članog skupa nije teško izbrojati.
[/quote]

jao, pa da :!:

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:

[latex]\begin{pmatrix}n\\2 \end{pmatrix} \cdot \begin{pmatrix}n-2\\2 \end{pmatrix} \cdot \cdot \cdot \begin{pmatrix}2\\2 \end{pmatrix}=
\frac{n!}{2!(n-2)! } \cdot \frac{(n-2)!}{2!(n-4)! }\cdot\cdot\cdot \frac{2!}{2!0! }=$kad se sve skrati$= \frac{n!}{2^\frac{n}{2}}[/latex]

dakle, rjesenje je:
0, za n neparan
[latex]\frac{n!}{2^\frac{n}{2}}[/latex], za n paran

puno puno hvala na pomoci! :karma: reci ako je nesto krivo :)
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



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku
rafaelm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 12. 2006. (13:30:11)
Postovi: (21F)16
Spol: muško
Sarma = la pohva - posuda
76 = 86 - 10
Lokacija: Zagreb

PostPostano: 21:47 sub, 1. 11. 2008    Naslov: Citirajte i odgovorite

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


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 21:50 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="gaston"][quote="goranm"]
Broj svih 2-particija n-članog skupa nije teško izbrojati.
[/quote]

jao, pa da :!:[/quote]
Samo da napomenem da sam ja pogrešno napisao u ovom citatu unutar citata (ispravio sam u originalnom postu):). Ne računamo broj 2-particija n-članog skupa nego broj rastava n-članog podskupa na (disjunktne) dvočlane skupove.

[quote]puno puno hvala na pomoci! :karma: reci ako je nesto krivo :)[/quote]
rafaelm je napomenuo još jednu [i]sitnicu[/i] koja nedostaje :)
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



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
rafaelm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 12. 2006. (13:30:11)
Postovi: (21F)16
Spol: muško
Sarma = la pohva - posuda
76 = 86 - 10
Lokacija: Zagreb

PostPostano: 21:53 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="goranm"]Ne računamo broj 2-particija n-članog skupa nego broj rastava n-članog podskupa na (disjunktne) dvočlane skupove.
[/quote]

Ako se dobro sjećam, mi smo to zvali '[i]sparivanje[/i]', na vježbama iz diskretne.
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.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 22:07 sub, 1. 11. 2008    Naslov: Re: 2. zadaca Citirajte i odgovorite

[quote="rafaelm"]Ako se dobro sjećam, mi smo to zvali '[i]sparivanje[/i]', na vježbama iz diskretne.[/quote]
To je inače "broj transpozicija", a transpozicija je ciklus duljine 2. :) 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. :)
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



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
gaston
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 07. 2008. (15:42:28)
Postovi: (21)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 22:23 sub, 1. 11. 2008    Naslov: Citirajte i odgovorite

[quote="rafaelm"]Nije važan redosljed kojim biramo te elemente, pa bi tribalo još malo dijeliti.[/quote]

zaista! :oops:

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 [latex]\frac{n}{2}[/latex] parova elemenata iz A...

da li je onda konacno rjesenje

[latex]
(\begin{pmatrix}n\\2 \end{pmatrix} \cdot \begin{pmatrix}n-2\\2 \end{pmatrix} \cdot \cdot \cdot \begin{pmatrix}2\\2 \end{pmatrix})/(\frac{n}{2})![/latex]

:?:
rafaelm (napisa):
Nije važan redosljed kojim biramo te elemente, pa bi tribalo još malo dijeliti.


zaista! Embarassed

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



Question



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 22:35 sub, 1. 11. 2008    Naslov: Citirajte i odgovorite

[quote="gaston"]da li je onda konacno rjesenje

[latex]
(\begin{pmatrix}n\\2 \end{pmatrix} \cdot \begin{pmatrix}n-2\\2 \end{pmatrix} \cdot \cdot \cdot \begin{pmatrix}2\\2 \end{pmatrix})/(\frac{n}{2})![/latex]

:?:[/quote]
Je. :)

Sad možeš vidjeti da je to isto kao broj permutacija od n elemenata cikličkog tipa [latex](0,\frac{n}{2},0,\dots,0)[/latex], 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 [latex](c_1,c_2,\dots,c_n)[/latex] je
[latex]\dfrac{n!}{1^{c_1}c_1!2^{c_2}c_2!\cdots n^{c_n}c_n!},[/latex]

a u našem slučaju to je

[latex]\dfrac{n!}{2^{\frac{n}{2}}(\frac{n}{2})!}[/latex]
gaston (napisa):
da li je onda konacno rjesenje



Question

Je. Smile

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 je


a u našem slučaju to je




_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
rafaelm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 24. 12. 2006. (13:30:11)
Postovi: (21F)16
Spol: muško
Sarma = la pohva - posuda
76 = 86 - 10
Lokacija: Zagreb

PostPostano: 22:38 sub, 1. 11. 2008    Naslov: Citirajte i odgovorite

[quote="gaston"]da li je onda konacno rjesenje

[latex]
(\begin{pmatrix}n\\2 \end{pmatrix} \cdot \begin{pmatrix}n-2\\2 \end{pmatrix} \cdot \cdot \cdot \begin{pmatrix}2\\2 \end{pmatrix})/(\frac{n}{2})![/latex]

:?:[/quote]

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: [latex](n-1)(n-3)... \cdot 3 \cdot 1 = (n-1)!![/latex]
gaston (napisa):
da li je onda konacno rjesenje



Question


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:


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Cobs
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 21. 01. 2008. (13:32:15)
Postovi: (206)16
Spol: muško
Sarma = la pohva - posuda
26 = 40 - 14
Lokacija: Geto

PostPostano: 13:47 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

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.
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.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
goranm
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 12. 11. 2002. (20:09:12)
Postovi: (906)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
218 = 249 - 31

PostPostano: 17:11 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

A što točno je krivo postavljeno? :)
A što točno je krivo postavljeno? Smile



_________________
The Dude Abides
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
gaston
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 10. 07. 2008. (15:42:28)
Postovi: (21)16
Sarma = la pohva - posuda
= 1 - 0

PostPostano: 19:57 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

evo, ja bih upao sa jednim drugim pitanjem, vezanim za zadatak 9.c)

neka je dan skup [latex]A[/latex] od [latex]n[/latex] elemenata. odredite koliko ima rastucih funkcija [latex]f:A\rightarrow A[/latex]


e sad, pretpostavljam da smijemo, bez smanjenja opcenitosti, uzeti [latex]A=\{1, 2,...,n\}[/latex], pa ce za svaku rastucu funkciju [latex]f:A\rightarrow A[/latex] vrijediti
[latex]i<j \Rightarrow f(i) \leq f(j)[/latex], pri cemu su [latex]i,j \in \{1, 2,...,n\}[/latex]

vidljivo je naprimjer da ako je, npr. [latex]f(2)=5[/latex], onda je nuzno [latex]f(3), f(4),...f(n) \in \{5,...,n\}[/latex],
odnosno [latex](f(i)=k) \Rightarrow f(j) \geq k[/latex], za [latex](i<j \leq n)[/latex]

ali ne znam kako ovo svojstvo icemu pomaze.

nemam pojma kako prebrojati sve rastuce funkcije sa [latex]A[/latex] u [latex]A[/latex] i bio bih izuzetno zahvalan na svakoj pomoci :D
evo, ja bih upao sa jednim drugim pitanjem, vezanim za zadatak 9.c)

neka je dan skup od 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 u i bio bih izuzetno zahvalan na svakoj pomoci Very Happy



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku
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: 20:13 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

Nije bas jednostavno. Probaj prvo prebrojati strogo rastuce funkcije, laske je. Vise onako za zagrijavanje (nije od velike koristi za tvoj zadatak :) )

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}.
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}.



_________________
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
Cobs
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 21. 01. 2008. (13:32:15)
Postovi: (206)16
Spol: muško
Sarma = la pohva - posuda
26 = 40 - 14
Lokacija: Geto

PostPostano: 20:46 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

[quote="goranm"]A što točno je krivo postavljeno? :)[/quote]

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.
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.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Atomised
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Sarma = la pohva - posuda
70 = 95 - 25
Lokacija: Exotica

PostPostano: 22:29 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

[quote="Cobs"][quote="goranm"]A što točno je krivo postavljeno? :)[/quote]

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)?
[/quote]

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. :D

Ma mislim da je pod d) jednostavno neka greška.
Cobs (napisa):
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)?


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.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Cobs
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 21. 01. 2008. (13:32:15)
Postovi: (206)16
Spol: muško
Sarma = la pohva - posuda
26 = 40 - 14
Lokacija: Geto

PostPostano: 22:34 ned, 2. 11. 2008    Naslov: Citirajte i odgovorite

[quote="Atomised"]

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

Ma mislim da je pod d) jednostavno neka greška.[/quote]

Na to sam tocno i mislio.
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.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Atomised
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Sarma = la pohva - posuda
70 = 95 - 25
Lokacija: Exotica

PostPostano: 0:11 pon, 3. 11. 2008    Naslov: Citirajte i odgovorite

@Cobs: Znam. :)

Nego, kako treba riješiti 4. zadatak? Ja znam ciklički zapisati permutaciju, ali ga i dalje baš ne kužim. :D
@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


[Vrh]
Korisnički profil Pošaljite privatnu poruku
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.
Idite na 1, 2, 3  Sljedeće
Stranica 1 / 3.

 
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