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

rastuće funkcije zadatak
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
Marko Beljan
Gost





PostPostano: 17:24 ned, 18. 12. 2005    Naslov: rastuće funkcije zadatak Citirajte i odgovorite

Treba bi mi rješenje jednog zadataka, ako bi htio pomoći netko tko zna.

Koliko ima rastućih (ne nužno strogo rastućih) funkcija
{1,2,...,n}x{1,2,...,n}->{0,1,2,...,n}
(n prirodan broj)

Zanima me samo formula (radi nečega), a ne treba postupak. Hvala :)
Treba bi mi rješenje jednog zadataka, ako bi htio pomoći netko tko zna.

Koliko ima rastućih (ne nužno strogo rastućih) funkcija
{1,2,...,n}x{1,2,...,n}->{0,1,2,...,n}
(n prirodan broj)

Zanima me samo formula (radi nečega), a ne treba postupak. Hvala Smile


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 17:37 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. :-s Koju koristis, tj. kada je (a,b) < (c,d)? :-k

(btw, strogo rastuca ne postoji ni jedna, osim za trivijalni slucaj n=1 ;))
Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. Eh? Koju koristis, tj. kada je (a,b) < (c,d)? Think

(btw, strogo rastuca ne postoji ni jedna, osim za trivijalni slucaj n=1 Wink)



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Marko Beljan
Gost





PostPostano: 17:57 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

[quote="vsego"]Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. :-s Koju koristis, tj. kada je (a,b) < (c,d)? :-k[/quote]
Definiramo (a,b)<=(c,d) ako i samo ako je a<=c i b<=d. Mislio sam da je to prirodno.
vsego (napisa):
Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. Eh? Koju koristis, tj. kada je (a,b) < (c,d)? Think

Definiramo (a,b)⇐(c,d) ako i samo ako je a⇐c i b⇐d. Mislio sam da je to prirodno.


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 18:05 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

[quote="Marko Beljan"][quote="vsego"]Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. :-s Koju koristis, tj. kada je (a,b) < (c,d)? :-k[/quote]
Definiramo (a,b)<=(c,d) ako i samo ako je a<=c i b<=d. Mislio sam da je to prirodno.[/quote]

Nije prirodno, jer ti onda nisu svi brojevi usporedivi. :? Recimo nije (1,2)<=(2,1), ali nije ni (2,1)<=(1,2)... :? Mi mozemo reci "ok, [b]ako su A<B[/b], onda mora biti i f(A)<f(B); ako nije ni A<B ni B<A, ni A=B, onda nas ne zanima kako se odnose f(A) i f(B)", no da li bas to zelis? :-k
Marko Beljan (napisa):
vsego (napisa):
Za to ti treba definicija uredjaja na {1,2,...,n}x{1,2,...,n}. Eh? Koju koristis, tj. kada je (a,b) < (c,d)? Think

Definiramo (a,b)⇐(c,d) ako i samo ako je a⇐c i b⇐d. Mislio sam da je to prirodno.


Nije prirodno, jer ti onda nisu svi brojevi usporedivi. Confused Recimo nije (1,2)⇐(2,1), ali nije ni (2,1)⇐(1,2)... Confused Mi mozemo reci "ok, ako su A<B, onda mora biti i f(A)<f(B); ako nije ni A<B ni B<A, ni A=B, onda nas ne zanima kako se odnose f(A) i f(B)", no da li bas to zelis? Think



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Marko Beljan
Gost





PostPostano: 21:45 ned, 18. 12. 2005    Naslov: Citirajte i odgovorite

Baš to želim!
Zamisliš si nxn tablicu koju trebaš popuniti brojevima 0,1,2,...,n tako da brojevi rastu (ne nužno strogo nego <=) da rastu i prema desno (u svakom retku) i prema dolje (u svakom stupcu).
Na koliko načina se to može?

Na prste se prebroji:
za n=1 na 2 načina (2 funkcije)
za n=2 na 20 načina (20 funkcija)

Ima li neka makar ružna formula za općeniti n ?
Baš to želim!
Zamisliš si nxn tablicu koju trebaš popuniti brojevima 0,1,2,...,n tako da brojevi rastu (ne nužno strogo nego <=) da rastu i prema desno (u svakom retku) i prema dolje (u svakom stupcu).
Na koliko načina se to može?

Na prste se prebroji:
za n=1 na 2 načina (2 funkcije)
za n=2 na 20 načina (20 funkcija)

Ima li neka makar ružna formula za općeniti n ?


[Vrh]
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 18:30 pon, 19. 12. 2005    Naslov: Citirajte i odgovorite

Evo jedna [u]lijepa[/u] formula za općeniti n. :D
To je "poznata" formula Mac Mahona koja je riješila dotični problem pred 80-ak godina.

Broj takvih funkcija (odnosno broj mogućih popunjavanja tablice je):
[latex]\displaystyle\frac{ {3n-1 \choose n} {3n-2 \choose n} \ldots {2n+1 \choose n} {2n \choose n} }{ {2n-1 \choose n} {2n-2 \choose n} \ldots {n+1 \choose n} {n \choose n} }[/latex]

I ne može se to jednostavnije zapisati, osim da se, eventualno, po definiciji raspišu binomni koeficijenti i pokrate neki faktorijeli.

Još nešto o tome ima [url=http://mathworld.wolfram.com/PlanePartition.html]ovdje[/url] jer taj problem ima lijepu "geometrijsku" interpretaciju i veze s još nekim kombinatornim problemima.
Evo jedna lijepa formula za općeniti n. Very Happy
To je "poznata" formula Mac Mahona koja je riješila dotični problem pred 80-ak godina.

Broj takvih funkcija (odnosno broj mogućih popunjavanja tablice je):


I ne može se to jednostavnije zapisati, osim da se, eventualno, po definiciji raspišu binomni koeficijenti i pokrate neki faktorijeli.

Još nešto o tome ima ovdje jer taj problem ima lijepu "geometrijsku" interpretaciju i veze s još nekim kombinatornim problemima.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Marko Beljan
Gost





PostPostano: 9:35 uto, 20. 12. 2005    Naslov: Citirajte i odgovorite

Hvala. Samo to me zanimalo. Živjeli!
Hvala. Samo to me zanimalo. Živjeli!


[Vrh]
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