[Discrete_Math]Кол-во инъекций && сюрьекций.

Всегда считал, что инъекция и сюръекция - отображения на множествах. Соответственно, для функции достаточно построить по одной инъекции и сюръекции. Где я не прав?

Нет. дано отображение ф-ции, нужно посчитать сколько всего функций, сколько из них инъективный и сюръективных.

f: S->T
#S==m
#T = n

Все их изобразить нереал, тк ИМХО там вообще степенная зависимость

дано отображение ф-ции

libastral.0.6.9 подсказывает, что все-таки даны два числа m и n, и нужно найти кол-во отображений m-элементного множества в n-элементное, а также кол-во инъекций и сюрьекций. Возможный план решения:

Общее кол-во отображений посчитать просто.

Инъекции проще считать только монотонные, предположив что множества упорядочены, и затем домножить ответ на факториал. Кол-во монотонных инъекций считается по пропускам. Т.е. тебе нужно представить число n-m в виде суммы n+2 слагаемых, каждое из которых может быть равно 0. Для поиска кол-ва таких слагаемых нужно к каждому прибавить 1, чтобы они были не нулевые, а затем перейти к последовательности частичных сумм.

Кол-во сюрьекций ищется по формуле включений-исключений.

В обоих случаях можно попытаться составить рекурентное соотношение.

для суръекции будем рассматривать отображение A->B, когда n=|A|>=|B|=m, иначе не может быть суръекции.

нам нужно сделать как минимум m отображений на все элементы B, значит уже есть n!/(n-m)!. У нас остается еще n-m элементов, которые можно разместить как угодно - это m^(n-m)

получется количество суръекций - n!/(n-m)!*m^(n-m).

про инъекции аналогично можно.

Про инъекции то легко, там n*(n-1)...*(n-m+1), а вот с сюрьекциями я застрял. Спасибо!

правда еще вопрос, надо ли рассматривать случаи, когда во множестве A есть элементы, для которых функция не определена. В таком случае надо еще домножить на n!/((n-k)!k!), k - число элементов в A, для которых функция не определена.

Но я думаю, что можно ограничиться определенными на всем A функциями.

Про инъекции то легко, там n*(n-1)...*(n-m+1), а вот с сюрьекциями я застрял.

Точно :)

Я вот тоже думаю можно ограничиться...:)

нам нужно сделать как минимум m отображений на все элементы B, значит уже есть n!/(n-m)!. У нас остается еще n-m элементов, которые можно разместить как угодно - это m^(n-m)

получется количество суръекций - n!/(n-m)!*m^(n-m).

При n=2, m=1, формула, AFAIU, не работает. Это рассуждение дает оценку сюрьекций сверху.

точно. сейчас попробую поправить.

при 3 и 2 - тоже не получается...

m(m+1)*(m+2)*...*(m+n-1) ?

нет, вообще не получается

сумма по k от 0 до m

(-1)^k * m!/(k!*(m-k)!) * (m-k)^n

А так: n*(n+1)*...*(n+m-1) ? *trollface*

Если я правильно понял, то сюръекция — это число упорядоченных размещений n объектов по m ящикам: [m]^n = m(m+1)...(m+n-1)

дык ясное дело. Проблема в том, что при «разбросе» оставшихся после первого шага элементов A - мы получаем также варианты, которые могли бы получится и при другом отображении m элементов из A на B. Поэтому надо делить на количество возможных вариантов.

Возьмем для примера, что все оставшиеся элементы потом будут отображаться в какой-то один. тогда формула будет выглядеть:

n!/(n-m!)*m^(n-m)/(n-m+1)

надо теперь придумать на что делить, если остальные элементы отображаются не в какой-то один, а в k.

А потом просуммировать по всем возможным k.

Сюръекция это не число. Смена значений - несерьезно.

(-1)^k * m!/(k!*(m-k)!) * (m-k)^n

а откуда взялось (-1)^k ?

Сюръекция это не число.

расскажи кому-нибудь другому. Инъективное отображение в дискретной математике формулируется для простоты понимания как: число размещений, для которых каждый ящик содержит не более одного объекта.

Смена значений - несерьезно.

Ты чем проверяешь то?

а откуда взялось (-1)^k ?

Из формулы включений-исключений.

PS. Можно заменить k->m-k и получить с точностью до знака формулу по-компактней.

(-1)^k * <це из m по k> * k^n

Не думаю, что сумма свернется во что-то замкнутое.

Инъективное отображение в дискретной математике формулируется для простоты понимания как: число размещений, для которых каждый ящик содержит не более одного объекта.

ну вот. А мы тут про суръекцию.

http://www.mathforum.ru/forum/read/1/462/

Тут написан ответ.
А еще я гуглил сей вопрос всего 5 сек.

Липский — комбинаторика для программистов, 67ая страница, принцип включения и исключения, там найдешь.

А еще я гуглил сей вопрос всего 5 сек.

Молодец, возьми с полки пирожок.

Нашел вот что. По - моему как раз то, что нужно dropbox_img

Это формула для вычисления чисел Стирлинга второго рода чтоли?

Почти. С сюрьективным отображением из A->B действительно связано некоторое разбиение A на подмножества (праобразы элементов). И по этому формулы отличаются домножением на факториал.