Количество отображений

[Starosta46]

добрый день. Нужна помощь с вычислением количества отображений из множества $g: (1..n+2)$ в $(1..n)$. преподаватель сказал, что там формула из трех или 4-х слагаемых. Очень надеюсь на вашу помощь, т.к. сам смог составить только длинную формулу.
получил формулу: $n^{n+2} - ((n-1)^{n+2} + (n-2)^{n+2} ... + (n-n+1)^{n+2})$

[arseniiv]

Starosta46 в сообщении #781401 писал(а):

сам смог составить только длинную формулу

Какую именно?

UPD: До помещения темы в «Карантин» формулы в исходном сообщении не было.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: не приведены попытки решения, формулы не оформлены $\TeX$ом.

Starosta46
приведите попытки решения, укажите конкретные затруднения.
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

[arseniiv]

Starosta46 в сообщении #781401 писал(а):

получил формулу: $n^{n+2} - ((n-1)^{n+2} + (n-2)^{n+2} ... + (n-n+1)^{n+2})$

Интересно. Вам нужно было посчитать число каких-то специфических отображений? Число всех отображений из множества с $m$ элементами в множество с $n$ элементами равно просто $n^m$ — для каждого элемента области определения выбираем, в какой элемент области значений отобразить, получая произведение $\underbrace{n\cdot\ldots\cdot n}_{m\text{ раз}}$.

[Starosta46]

arseniiv в сообщении #781914 писал(а):

Starosta46 в сообщении #781401 писал(а):

получил формулу: $n^{n+2} - ((n-1)^{n+2} + (n-2)^{n+2} ... + (n-n+1)^{n+2})$

Интересно. Вам нужно было посчитать число каких-то специфических отображений? Число всех отображений из множества с $m$ элементами в множество с $n$ элементами равно просто $n^m$ — для каждого элемента области определения выбираем, в какой элемент области значений отобразить, получая произведение $\underbrace{n\cdot\ldots\cdot n}_{m\text{ раз}}$.

извиняюсь. нужно посчитать количество сюръективных

[VAL]

Starosta46 в сообщении #781921 писал(а):

извиняюсь. нужно посчитать количество сюръективных

В таком случае Ваша формула неверна.
Получить правильную можно разными способами:
1. Применив принцип включения исключений (что Вы, видимо, и пытались сделать). Но там получится не 3-4 слагаемых.
2. Использовать числа Стирлинга второго рода. Но сами эти числа вычисляются либо рекуррентно, либо через подсчет числа сюръекций.
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

Впрочем, тут получится всего два слагаемых

[Starosta46]

VAL в сообщении #781926 писал(а):

Starosta46 в сообщении #781921 писал(а):

извиняюсь. нужно посчитать количество сюръективных

В таком случае Ваша формула неверна.
Получить правильную можно разными способами:
1. Применив принцип включения исключений (что Вы, видимо, и пытались сделать). Но там получится не 3-4 слагаемых.
2. Использовать числа Стирлинга второго рода. Но сами эти числа вычисляются либо рекуррентно, либо через подсчет числа сюръекций.
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

Впрочем, тут получится всего два слагаемых

каких? у меня так коротко не получается(

[VAL]

Starosta46 в сообщении #782541 писал(а):

VAL в сообщении #781926 писал(а):

Получить правильную можно разными способами:
[..]
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

Впрочем, тут получится всего два слагаемых

каких? у меня так коротко не получается(

Итак остановились на третьем способе.
Сюръективно отображаем $n+2$ элемента в $n$. В каждый элемент второго множества должна войти хотя бы одна стрелка (отобразиться хотя бы один элемент первого множества). Для этого хватит $n$ стрелок. А у нас - $n+2$. Какие возможности есть для двух "лишних" стрелок?

[Starosta46]

VAL в сообщении #782773 писал(а):

Starosta46 в сообщении #782541 писал(а):

VAL в сообщении #781926 писал(а):

Получить правильную можно разными способами:
[..]
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

Впрочем, тут получится всего два слагаемых

каких? у меня так коротко не получается(

Итак остановились на третьем способе.
Сюръективно отображаем $n+2$ элемента в $n$. В каждый элемент второго множества должна войти хотя бы одна стрелка (отобразиться хотя бы один элемент первого множества). Для этого хватит $n$ стрелок. А у нас - $n+2$. Какие возможности есть для двух "лишних" стрелок?

Для каждой из них n вариантов

[VAL]

Starosta46 в сообщении #782864 писал(а):

VAL в сообщении #782773 писал(а):

Сюръективно отображаем $n+2$ элемента в $n$. В каждый элемент второго множества должна войти хотя бы одна стрелка (отобразиться хотя бы один элемент первого множества). Для этого хватит $n$ стрелок. А у нас - $n+2$. Какие возможности есть для двух "лишних" стрелок?

Для каждой из них n вариантов

(Оффтоп)

Этот ответ напомнил мне ответ на вопрос "Где мы находимся?" из анекдота про воздушный шар и математиков.
Он тоже абсолютно правильный и абсолютно бесполезный для решения задачи

Рассмотрим обе стрелки вместе. Какие два принципиально различных случая Вы видите?

[Starosta46]

Они могут переходить в одни, а могут в разные

[VAL]

Starosta46 в сообщении #782899 писал(а):

Они могут переходить в одни, а могут в разные

Что значит "в одни"? Это значит "в один элемент"? Тогда почему он во множественном числе?
Впрочем, это мелочи. Главное, что два принципиальных случая выделены.
Рассмотрим первый.
План прост (выше я его уже излагал):
выберем элемент, имеющий целых три прообраза;
выберем прообразы этого элемента;
биективно отобразим остальные $n-1$ элементов первого множества в остальные $n-1$ элементов второго.
Скольким способами можно сделать все вышеизложенное?

[Lukum]

VAL в сообщении #782901 писал(а):

биективно отобразим остальные $n-1$ элементов первого множества в остальные $n-1$ элементов второго.
Скольким способами можно сделать все вышеизложенное?

похоже на $(n-1)!$, верно?

[VAL]

Lukum в сообщении #782904 писал(а):

VAL в сообщении #782901 писал(а):

биективно отобразим остальные $n-1$ элементов первого множества в остальные $n-1$ элементов второго.
Скольким способами можно сделать все вышеизложенное?

похоже на $(n-1)!$, верно?

Слегка. Но не совсем.
Там же три пункта (два первых Вы пеочему-то не процитировали). Последовательно отвечайте на поставленные вопросы и не забывайте применять правило умножения.

[Lukum]

Все вместе на это похоже (n)! S(n+2,n)$