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

задан 11 Июн '17 23:35

10|600 символов нужно символов осталось
1

В переводе на абстрактный язык, требуется найти число сюръективных отображений множества $%\{1,2,...,7\}$% на $%\{1,2,3,4\}$%. Такого рода задача недавно обсуждалась. Можно найти число Стирлинга II рода по таблицам при помощи рекуррентных формул: $%S(7,4)=350$%. Это число разбиений 7-элементного множества на 4 непустые части. Домножая на $%4!$%, имеем $%8400$%, и это есть число сюръекций.

Второй способ основан на формуле включений и исключений. Общее число отображений равно $%4^7$%. Вводим множества $%A_i$% при $%i=1,2,3,4$%. Они состоят из тех отображений, у которых $%i$% не присутствует в образе. Легко видеть, что $%|A_i|=3^7$%, $%|A_iA_j|=2^7$%, $%|A_iA_jA_k|=1$% для любых попарно различных индексов. Ясно также, что множеств первого типа имеется $%C_4^1=4$%, попарных пересечений будет $%C_4^2=6$%, трёхкратных пересечений $%C_4^3=4$%, а пересечение всех 4 множеств пусто. Вычитая из общего числа отображений количество элементов объединения $%|A_1\cup\cdots\cup A_4|$% (то есть число несюръективных), имеем по формуле включений и исключений $%4^7-4\cdot3^7+6\cdot2^7-4=8400$%.

Надо заметить, что тут фактически описан общий принцип подсчёта. Он же был изложен раньше (в задаче про грабителей), и можно было тем описанием воспользоваться.

ссылка

отвечен 12 Июн '17 0:02

10|600 символов нужно символов осталось
0

$$ 4C_7^1C_6^1C_5^1C_4^4+12C_7^1C_6^1C_5^2C_3^3+4C_7^1C_6^2C_4^2C_2^2=$$ $$ =4\cdot7\cdot6\cdot5+12\cdot7\cdot6\cdot10+4\cdot7\cdot15\cdot6=840+5040+2520=8400$$

ссылка

отвечен 12 Июн '17 0:11

изменен 12 Июн '17 0:12

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,300

задан
11 Июн '17 23:35

показан
501 раз

обновлен
12 Июн '17 0:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru