Matematické Fórum

Forestgump · 11. 11. 2008 17:05

Určete počet všech neklesajících funkcí $[n] \rightarrow [m]$ .

Vedel by si nekdo s timhle rady?

Marian · 12. 11. 2008 08:13

↑ Forestgump:
Není mi jasné, co jsou to prvky m a n, tedy konkrétně, z jakých jsou množin. Není také zřejmý význam závorek [, ]. Jedná se snad o celou část reálného čísla (jestli ano, pak máš na mysli horní nebo dolní celou část)?

Pokud můžeš, opiš zadání přesně, popř. i v jakém předmětu toto děláte a co probíráte. Může to pomoct.

kaja.marik · 12. 11. 2008 08:29

neni to treba do kombinatoriky? mozna jsou mysleny funkce z n-prvkove množiny do m-prvkove množiny čísel. Tohle bylo prvni co mě napadlo, když jsem přemýšlel nad tím, na co se dotyčný vlastně ptá.

musixx · 12. 11. 2008 08:42 — Editoval musixx (12. 11. 2008 08:48)

↑ kaja.marik: Vidim to stejne. A reseni bych videl jako zakladni pouziti principu inkluze a exkluze: Vzit vsechny n-tice (a_1, ..., a_n) poskladane z cisel 1 az m a vyloucit ty z nich, pro ktere pro nejake i plati a_i > a_{i+1}. Staci takova napoveda?

EDIT: To, co jsem navrhl, da pocet monotonnich neklesajicich funkci. Pokud bychom funkci 1->1, 2->100, 3->1, 4->100 povazovali tez za neklesajici, coz bychom teda meli, tak by to bylo podobne: nejprve secist vsechny klesajici a vysledek odecist od vsech n-tic.

Kondr · 12. 11. 2008 12:19

EDITACE: opraveno ↑ MonkeyBrain:

Řekněme, že [x] obsahuje čísla od 1 do x.
Když pro neklesající fci f:[n]->[m] vezmeme rozdíly f(1)-1,f(2)-f(1), f(3)-f(2),...,f(n)-f(n-1),m-f(n), máme n+1 nezáporných celých čísel se součtem m-1. A takových n+1-tic je ${m+n-1 \choose m-1}={m+n-1 \choose n}$
Zdůvodnění viz http://forum.matweb.cz/viewtopic.php?id=1932 1. příklad.

Forestgump · 13. 11. 2008 09:08

Děkuju, to by snad mělo stačit. Jinak to zadání je opsané doslova a je to z diskrétní matematiky.

kaja.marik · 13. 11. 2008 09:37

↑ Forestgump:
On problem byl asi i v tom, ze jsme nevedeli, co v te ucebnici znamenaji ty hranate zavorky.

MonkeyBrain · 13. 11. 2008 13:36

↑ Kondr:

Tento postup je správný ale součet těch n+1 čísel není m ale m - 1 :)... proto je to (m + n - 1 nad n). V tvém případě by např. počet neklesajících funkcí z 3 prvkové množiny do 1 prvkové dával 3 různé neklesající funkce.. což je blbost protože je pouze jedna ;) [(1 + 3 - 1 nad 3) = 1] !!!

Holography · 16. 11. 2008 22:21

Nejak tohle nemuzu pochopit, muze mi to nekdo lepe vyslvetlit, jak to bude s poctem neklesajicich funkci z 3 prvkove do 2 prvkove mnoziny? Me to vychazi ze budou 3, ale podle tohoto modelu vypoctu by to melo byt 4, muze mi nekdo nazorne vysvetlit jak se dospelo k tomuto vztahu nejlepe na konkretnim prikladu. Dekuji za ochotu!

Kondr · 17. 11. 2008 00:54

Z {1,2,3} do {1,2} je trojice (f(1),f(2),f(3)) v množině {(1,1,1),(1,1,2),(1,2,2),(2,2,2)}, funkce jsou proto 4.

the_q · 19. 11. 2008 23:33

K úplnosti řešení už chybí jen ukázat, že ten převod neklesajících funkcí na (n+1) - tici nezáporných čísel se součtem m-1 je vzájemně jednoznačný.

Matematické Fórum

#1 11. 11. 2008 17:05

Pocet neklesajicich funkci.

#2 12. 11. 2008 08:13

Re: Pocet neklesajicich funkci.

#3 12. 11. 2008 08:29

Re: Pocet neklesajicich funkci.

#4 12. 11. 2008 08:42 — Editoval musixx (12. 11. 2008 08:48)

Re: Pocet neklesajicich funkci.

#5 12. 11. 2008 12:19

Re: Pocet neklesajicich funkci.

#6 13. 11. 2008 09:08

Re: Pocet neklesajicich funkci.

#7 13. 11. 2008 09:37

Re: Pocet neklesajicich funkci.

#8 13. 11. 2008 13:36

Re: Pocet neklesajicich funkci.

#9 16. 11. 2008 22:21

Re: Pocet neklesajicich funkci.

#10 17. 11. 2008 00:54

Re: Pocet neklesajicich funkci.

#11 19. 11. 2008 23:33

Re: Pocet neklesajicich funkci.

Zápatí