Matematické Fórum

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?