Ну давайте разберем еще такой вариант задачи о беспорядках, который,
на самом деле, по сути, был разобран на лекции.
Ну вот хочется, видимо, закрепить еще немножко материал и пообсуждать вариации
на тему «задачи о беспорядках».
Может быть, для конкретных чисел будет понятно.
Итак, есть 4 друга.
[ПИШЕТ_НА_ДОСКЕ] Есть праздник Новый год, на который они вместе собрались.
Давайте напишем «Новый год».
Ну и каждый принес 1 подарок.
Всего 4, соответственно, подарка.
У каждого по подарку.
У каждого друга есть свой подарок, который он хочет кому-то подарить.
Спрашивается, сколькими способами можно так, действительно,
перераспределить подарки между друзьями, чтобы каждый получил не свой подарок.
Ну конечно, в известном анекдоте говорится, куда бы еще пойти с этим
тортом, но это все-таки в анекдоте, давайте считать, что ребята хотят уйти,
ну или девушки, кто там эти 4 друга, хотят уйти не со своим подарком,
не со своим тортом, а чьим-то все-таки чужим, для разнообразия, так сказать.
Поэтому нас интересует именно количество таких перестановок подарков между
ребятами, при которых каждый получает не своё.
Вот такая вот вариация на тему задачи о беспорядках.
Ну давайте напишем: сколько существует перестановок подарков,
перераспределений, способов раздачи, не знаю как лучше сказать.
Ну давайте я прямо скажу слово «перестановок».
Значит, сколько существует перестановок подарков,
при которых каждый из друзей.
При которых, ну неважно, каждый из друзей получает не свой подарок.
Из друзей
получает не свой подарок.
Ну, как я уже сказал, это в чистом виде, конечно, задача
разобранная на лекции, только с другими числами и с немножко другой постановкой.
Поэтому я не буду очень медленно ее разжевывать.
У нас уже такое было.
Всего общее количество объектов — это количество перестановок, 4 факториал.
Ну, собственно, объектами у нас служат перестановки,
распределение подарков по друзьям.
Но это общее количество перестановок, и понятно, что среди этих перестановок
есть такие, при которых товарищи получают как раз свое, и уходят со своим тортом,
чего им бы не хотелось в данном конкретном случае.
Поэтому нужно вычесть те плохие ситуации.
И проще всего сделать так: сначала выбрать одного из друзей.
Это можно сделать четырьмя способами,
четырьмя способами можно выбрать какого-то друга,
после чего сказать: вот этот конкретный друг точно ушел со своим подарком.
А про остальных мы не знаем — то ли со своим, то ли не со своим.
Но в любом случае таких перестановок есть всего 3 факториал.
Но понятно, что вычитая такое количество перестановок,
мы лишний раз вычитаем ситуации, когда, например,
и первый товарищ ушел со своим тортом, и второй товарищ ушел со своим тортом.
Или ситуацию, когда первый и третий ушли со своим.
Второй и четвертый ушли со своим.
Всего, очевидно, таких ситуаций C из 4 по 2.
Это 6, если посчитать.
То есть надо прибавить С из 4 по 2, умноженное на 2 факториал.
Вот это вот — это количество способов выбрать двух товарищей, которые ушли со
своим тортом условным, а вот это вот — количество всех остальных перестановок.
Ну и дальше по аналогии, понятно, надо вычесть С из 4 по 3 на 1 факториал
и прибавить С из 4 по 4 на 0 факториал, если уж быть совсем занудным и аккуратным.
Ну это в чистом виде формула включений-исключений,
которая работает в задаче о беспорядках.
Что у нас получится на выходе?
Это дело сократится.
6 умножить на 2 это 12, минус 4, ну и плюс 1.
Итого: получаем 9.
Ну и если вы вспомните лекцию, я говорил, что должно получиться ну примерно столько,
сколько есть всего перестановок, то есть в данном случае 24 поделить на
некое число е — 2,71828 и так далее, основание натурального логарифма.
Если мы 24 поделим на 2,71, то в общем довольно близко к 9 и получится.
Так что даже вот в такой ситуации, когда друзей всего четверо, сходимость
достаточно хорошая получается, очень похожая на то, что предсказывает теория.
Ну а это вот в общем точный ответ задачи.
Дмитрий Ильинскийпреподаватель
Андрей Райгородскийпрофессор, доктор физико-математических наук
