как найти количество сюрективных отображений?

[vvsh]

применяя метод включения и исключения.
заранее спасибо

[jetyb]

Что такое метод включения и исключения не знаю.
Но поробуйте решить задачу в случае отображения во множество из одного элемента.

[gris]

По-моему это связано с диаграммами Венна. Для нахождения количества элементов объединения нескольких пересекающихся конечных множеств складывают их мощности, вычитают мощности попарных пересечений, прибавляют мощности пересечений по три и как-то так.
Это для решения задач типа: в группе знают три языка. Французский и алглийский 6 студентов, все три 2, ну и так дальше. Надо что-то найти.
Может быть имеется в виду количество сюрьекций множества из $n$ элементов на себя?
Напоминает задачу о количестве биекций, при которых ни один элемент не отображается в себя.

[vvsh]

может это и есть для задач такого типа.
Применение метода включения и исключения (задача о беспорядках, задача о числе сюръективных отображений). - вопрос к экзамену звучит так.

[gris]

А, так это теоретический вопрос? Посмотрите у себя в лекциях Шутка.
А на самом деле наверняка это даже в википедии есть в статьях по комбинаторике. Беспорядочныt биекции я и имел в виду.
Ну не переписавать же сюда учебник. Если есть непонятности с чем-то конкретно, то спрашивайте.

[vvsh]

jetyb в сообщении #456507 писал(а):

Что такое метод включения и исключения не знаю.
Но поробуйте решить задачу в случае отображения во множество из одного элемента.

или вы не учили дискретку или не знаю.
Формула вкл. и иск.

-- 10.06.2011, 18:02 --

gris в сообщении #456530 писал(а):

А, так это теоретический вопрос? Посмотрите у себя в лекциях Шутка.
А на самом деле наверняка это даже в википедии есть в статьях по комбинаторике. Беспорядочныt биекции я и имел в виду.
Ну не переписавать же сюда учебник. Если есть непонятности с чем-то конкретно, то спрашивайте.

не очень понятно. ладно. попробую у лектора спросить. спасибо

[gris]

Так ведь неизвестно, какие именно сюрьекции имелись в виду в вашем курсе. Я, например, знаю задачу о количестве сюрьекций $k$ элементного множества на $n$ элементное.
Для $k=1$ это одна сюрьекция.
Для $k=2$ получается, что мы берём первый элемент и отображаем его в различные подмножества второго множества. А второй элемент должен отображаться на дополнение к образу первого да еще на всевозможные подмножества образа. Вот перемножаем и складываем. А в общем случае как раз и получается этот метод.

[VAL]

Сначала подсчитайте общее количество отображений из $n$-элементного множества в $k$-элементное. Потом удалите, те, при которых, по крайней мере, один элемент не имеет прообраза. При этом выясниться, что те, для которых два элемента не имеют прообраза, удалены дважды. Верните их назад. И т.д. В результате должна получиться формула:

$$sur(n,k)=\sum_{i=0}^{k-1} (-1)^i {k\choose i} (k-i)^n$$

[vvsh]

спросил у лектора.получилась такая формула n(0) = [

[gris]

Ну вот, это и есть формула из предыдущего сообщения, то есть количество всех сюрьекций m-элементного множества на n-элементное. Надо заменить в той формуле $n$ на $m$, а $k$ на $n$.

А беспорядок это биекция такого множества на себя без неподвижных точек. Там знакопеременная формула с факториаламии тоже построенная по этому принципу. То есть берём количество вообще всех перестановок, вычитаем те, у которых по крайней мере одна неподвижная точка, прибавляем те, у которых по крайней мере две и так далее.

Только в Вашей формуле небольшая ошибочка с минусом в средней части.

[mihailm]

(Оффтоп)

ТС вероятно со знаком суммы не знаком и прочитать сообщение VAL'а не может)

[vvsh]

да, я не обратил внимания на сходство