Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 18. 11. 2007 09:51

janoro
Zelenáč
Příspěvky: 18
Reputace:   
 

Počet šech funkcí

Mám tu dva příklady, které mi připadají tak trochu kombinatorické.
Zadání: f: {1,...,n} -> {1,..,m}
1) kolik je neklesajících f-cí? 2) Kolik je f-cí, které jsou NA?

Představuji si to jako zobrazení. S prvním úkolem si nevím rady, druhý tuším, tak ho tu zkusím vyřešit. Všech zobrazení by bylo m^n, prostých je m(m-1)(m-2)...(m-n+1), dále bych řekl, že bijekcí (tedy prostých i na) bude n!.
Spočítat rovnou všechna zobrazení NA je podle mě nemožné. Budu tedy počítat ty, které NA nejsou. Potom musí existovat bod, na který se nic nezobrazí. Označme tyto body písmeny "i" s indexy od jedné do "k". Zobrazení, které nic nezobrazí na tyto body je totéž jako zobrazení do (m-k) prvkové množiny, = (m-k)^n . Už před chvílí mě do očí praštilo něco, čemu se říká princip inkluze a exkluze. Počet zobrazení, které nejsou NA tedy bude suma pro k=1 do m výrazu (-1)^(k-1) * (m-k)^n. Potom počet zobrazení, které jsou NA bude m^n - (m "nad" jednou)*(m-1)^n + (m "nad" 2)*(m-2)^n - ...

Omluvte ty krkolomné formulace a zápisy, já vám nevím, v čem vy děláte ty pěkné obrázky vzorečků. No a jinak, myslíte, že je to správně? A co ten první příklad?

Offline

 

#2 18. 11. 2007 10:16

Ivana
Příspěvky: 4819
Reputace:   32 
 

Re: Počet šech funkcí

V indexu : < Připomínky a nápady > najdeš  jak se píší ty pěkné " vzorečky."

Já se to taky teprve učím . Ahoj Ivana :-)


Jedna krát jedna je  " tisíckrát " jedna :-)

Offline

 

#3 18. 11. 2007 21:52

janoro
Zelenáč
Příspěvky: 18
Reputace:   
 

Re: Počet šech funkcí

OK díky, snad se to naučim. No a ten příklad?

Offline

 

#4 18. 11. 2007 22:03 — Editoval Kondr (22. 11. 2007 20:08)

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
Web
 

Re: Počet šech funkcí

K prvnímu: každou takovou funkci si můžeme zobrazit takto: vytvoříme blok teček, v němž každá tečka odpovídá x takovému, že f(x)=1. Pak uděláme svislou čáru. Pak uděláme blok teček odpovídajících číslům, pro která f(x)=2 a opět svislou čáru, atd. V každém z n bloků může být i 0 teček. Funkci jsme tedy nahradili kódem z n teček a m-1 čárek.
Kolik je takových kódů? (hint: permutace s opakováním)

EDIT: řešení dvojky umazáno, omlouvám se za původní chybné.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#5 22. 11. 2007 21:43

janoro
Zelenáč
Příspěvky: 18
Reputace:   
 

Re: Počet šech funkcí

Můžu se zeptat, proč je počet funkcí, které jsou "na", spíš ten tvůj výsledek, než ten můj?

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson