Броене на сюрекции

[РадоРадо]

Задачата :
Колко е броя на всички функции от вида f: Jn -> Jm, които са сюрекция ?

Според мен това са вариации с повторения и отговора е [tex]m^{n}[/tex] , но не съм особено сигурен.
Предложения ?

[nikko]

Задачата :
Колко е броя на всички функции от вида f: Jn -> Jm, които са сюрекция ?

Според мен това са вариации с повторения и отговора е [tex]m^{n}[/tex] , но не съм особено сигурен.
Предложения ?

А какво означавате с Jn и Jm?

[РадоРадо]

Множество с n елемента и множество с m елемента.
Всъщност и на мен не ми е много ясно. Така е зададено условието

[nikko]

Отговорът ти не е верен. [tex]m^n[/tex] са изобщо всички изображения на множество с n елемента в множество с m елемента. Броят на сюрекциите се определя чрез числата на Стърлинг от втори тип, а формулата за тях е сравнително сложна. Все пак ето какво се прави. Първо разделяме множеството с n елемента на m групи, като на всяка от тях ще съпоставяме различен елемент от множеството с m елемента. Това може да се направи по [tex]S(n,m)[/tex] начина, ако така сме означили числото на Стърлинг от втори тип. Имаме [tex]S(n,m)=\frac{1}{m!}\sum_{j=0}^{m}(-1)^{m-j}{m \choose j} j^n[/tex]. След като сме разделили множеството остава само да се види, че на всяка от m-те групи от множеството [tex]J_n[/tex] можем да съпоставим произволен елемент на [tex]J_m[/tex], т.е. имаме да подредим m-те групи, което може да се направи по [tex]m![/tex] начина. Окончателно броят на сюрекциите е [tex]m!.S(n,m)=\sum_{j=0}^{m}(-1)^{m-j}{m \choose j} j^n[/tex].

[РадоРадо]

За първи път го чувам този Стърлинг.
Благодаря за решението.