|X| = m, |Y| = n.  Нека A е м-вото от сюр. X --> Y. Избираме y \in Y. 

Нека A1 е подм-вото на A, в което повече от един елемент на X има образ y.  Очевидно |A1| = S(m-1, n).

Нека A2 е подм-вото на A, в което точно един елемент на X има образ y.  Очевидно |A2| = S(m-1, n-1).

Тъй като можем да изберем y по n начина, като цяло имаме n(S(m-1,n) + S(m-1,n-1)).


Това е грешно.  Ето контрапример.  Нека m = 5 и n = 3.  S(m,n) = 150.  Фиксираме елемент y \in Y.   Съгласно горното "решение", броят на сюрекциите, които покриват y повече от веднъж, е S(4,3).  Но S(4,3) = 36.  А сюрекциите, покриващи y повече от веднъж, са 10.6 + 10.2 = 80.  Ето защо

1) сюрекциите, покриващи y точно 2 пъти, са binomial(5,2) x S(3,2) = 10 x 6, понеже по binomial(5,2) начина избираме кои да са покриващите от X, и остават 3 елемента от X да покрият някакси останалите два от Y

2) сюрекциите, покриващи y точно 3 пъти, са binomial(5,3) x S(2,2)

Последно модифициране: петък, 5 септември 2025, 15:21