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
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗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
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
#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
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