2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Количество отображений
Сообщение28.10.2013, 18:48 
Starosta46 в сообщении #781401 писал(а):
сам смог составить только длинную формулу
Какую именно?

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

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

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

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

 
 
 
 Re: Количество отображений
Сообщение29.10.2013, 20:20 
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{ раз}}$.

 
 
 
 Re: Количество отображений
Сообщение29.10.2013, 20:32 
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{ раз}}$.

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

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

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

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

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

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 16:40 
Starosta46 в сообщении #782541 писал(а):
VAL в сообщении #781926 писал(а):
Получить правильную можно разными способами:
[..]
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

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

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 17:34 
VAL в сообщении #782773 писал(а):
Starosta46 в сообщении #782541 писал(а):
VAL в сообщении #781926 писал(а):
Получить правильную можно разными способами:
[..]
3. Использовать специфику условия. Скорее всего, имелось в виду именно это.
Тогда во втором множестве надо выбрать
1) либо один особенный элемент, а первом его прообразы, а потом разобраться с остальными элементами ;
2) либо два особенных элемента, а первом их прообразы, а потом разобраться с остальными элементами.

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


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

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 19:00 
Starosta46 в сообщении #782864 писал(а):
VAL в сообщении #782773 писал(а):
Сюръективно отображаем $n+2$ элемента в $n$. В каждый элемент второго множества должна войти хотя бы одна стрелка (отобразиться хотя бы один элемент первого множества). Для этого хватит $n$ стрелок. А у нас - $n+2$. Какие возможности есть для двух "лишних" стрелок?

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

(Оффтоп)

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 19:03 
Они могут переходить в одни, а могут в разные

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 19:21 
VAL в сообщении #782901 писал(а):
биективно отобразим остальные $n-1$ элементов первого множества в остальные $n-1$ элементов второго.
Скольким способами можно сделать все вышеизложенное?

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

 
 
 
 Re: Количество отображений
Сообщение31.10.2013, 19:25 
Lukum в сообщении #782904 писал(а):
VAL в сообщении #782901 писал(а):
биективно отобразим остальные $n-1$ элементов первого множества в остальные $n-1$ элементов второго.
Скольким способами можно сделать все вышеизложенное?

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

 
 
 
 Re: Количество отображений
Сообщение01.11.2013, 07:00 
Все вместе на это похоже (n)! S(n+2,n)$

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group