Matematické Fórum

petrkovar · 29. 10. 2010 12:31

Počet surjektivních zobrazení $k$ -prvkové množiny do $n$ -prvkové množiny je dán vztahem
$\sum_{i=0}^{n} (-1)^i {n \choose i} (n-i)^{k}$ .
Tento vztah dává správný výsledek $0$ i pro případy, kdy $n>k$ , ačkoliv se při konstrukci vztahu pomocí principu inkluze a exkluze s takovou možnosti explicitně neuvažuje.
Napadá vás nějaké pěkné (kombinatorické) zdůvodnění, proč tomu tak je?

Dvě poznámky:
1) triviální důvod, že taková surjekce není možná a proto počet vychází $0$ se mi nelíbí
2) uvědomíme-li si, že pri odvození vztahu nejprve od všech zobrazení odečítáme ta, ve kterých nějaký prvek není obrazem žádného prvku (což jsou všechna zobrazení), tak dostáváme $0$ se mi také nelíbí, neboť v uvedené sumě máme obvykle RŮZNÉ nenulové sčítance.

petrkovar · 09. 11. 2010 21:36

Druhou poznámku přeformuluji a budu spokojen.
Všech možných zobrazení je $n^k$ a uvědomíme si, že vypočímáme-li podle mírně upraveného vztahu $\sum_{i=1}^{n} (-1)^i {n \choose i} (n-i)^{k}$ ta zobrazení, ve kterých není alespoň jeden prvek obrazem jiného prvku, tak jsme druhou metodou spočítali opět všechna zobrazení, neboť v každém zobrazení alespoň jeden prvek z $N$ není obrazem žádného prvku z $K$ .
Počet surjektivních zobrazení je pro $n>k$ rozdílem dvou stejných hodnot a je proto vždy roven 0.

Matematické Fórum

#1 29. 10. 2010 12:31

Počet surjektivních zobrazení

#2 09. 11. 2010 21:36

Re: Počet surjektivních zobrazení

Zápatí