34. Беспорядки: письма и конверты
Беспорядок — это расстановка, в которой ни один элемент не стоит на своём месте. Сколькими способами можно разложить пронумерованных писем по пронумерованным конвертам так, чтобы ни одно письмо не попало в конверт со своим номером? Принцип включений и исключений даёт , а это число почти равно .
Что пригодится из прошлого: включения и исключения через свойства — формула ; перестановки — всего способов разложить письма ; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача о письмах и конвертах
Сколькими способами можно разместить писем с номерами в конвертах с номерами (по одному письму в конверт) так, чтобы никакое письмо не оказалось в конверте с тем же номером? Число таких размещений обозначим .
Три письма
Запишем раскладку тремя цифрами: на -м месте номер конверта, в который попало письмо . Всего раскладок. В правом столбце — номера писем, лежащих в своём конверте; прочерк значит, что таких писем нет, то есть это беспорядок:
| Раскладка | Письма дома |
|---|---|
| 123 | 1, 2, 3 |
| 132 | 1 |
| 213 | 3 |
| 231 | — |
| 312 | — |
| 321 | 2 |
Беспорядков два: и . Значит, .
Для четырёх писем раскладок , беспорядков : 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
Формула
Применим принцип включений и исключений в форме свойств.
Пусть — множество всех раскладок писем по конвертам; . Свойство (): -е письмо лежит в -м конверте. Нужные нам размещения — те, у которых ни одно свойство не выполнено: .
Найдём . Если заранее выбрать писем и потребовать, чтобы они лежали в своих конвертах, то остальные писем можно разложить по оставшимся конвертам произвольно, то есть способами. Выбрать эти писем можно способами. Поэтому
Проверим последнюю цепочку: .
Теперь формула включений и исключений:
Вынесем :
Проверка на . ✓. На : ✓.
Почему
Число — основание натуральных логарифмов; нам хватит знать, что . Известно, что сумма
(Это значение ряда при .) Поэтому для больших
Посмотрим на цифры:
| 1 | 1 | 0 | 0,0000 | 0,368 |
| 2 | 2 | 1 | 0,5000 | 0,736 |
| 3 | 6 | 2 | 0,3333 | 2,207 |
| 4 | 24 | 9 | 0,3750 | 8,829 |
| 5 | 120 | 44 | 0,3667 | 44,146 |
| 6 | 720 | 265 | 0,3681 | 264,873 |
| 7 | 5 040 | 1 854 | 0,3679 | 1854,112 |
| 8 | 40 320 | 14 833 | 0,3679 | 14832,899 |
| 9 | 362 880 | 133 496 | 0,3679 | 133496,092 |
| 10 | 3 628 800 | 1 334 961 | 0,3679 | 1334960,916 |
Доля беспорядков быстро устанавливается около и дальше почти не меняется. Значит, среди всех раскладок писем по конвертам беспорядки составляют примерно при любом большом : если раскладывать письма наугад, то примерно в таком проценте случаев ни одно не попадёт «домой».
Любопытное наблюдение. Начиная с число — ближайшее целое к числу : см. последние два столбца таблицы. Объяснение: ряд знакопеременный, а модули его членов убывают (у такого ряда ошибка меньше первого отброшенного члена), поэтому после -го слагаемого ошибка меньше первого отброшенного члена , и умножение на даёт ошибку меньше .
Частые ошибки
- Думать, что почти все раскладки — беспорядки. На самом деле они составляют около всех раскладок.
- Забыть про знаки. Слагаемые чередуются:
- Путать «ни одно не на месте» и «ровно одно не на месте». Беспорядок — все письма не на своих местах.
- Считать без коэффициента . Выбрать, какие писем попадают в «свои» конверты, можно способами.
Проверь себя
1. Найдите по формуле.
Решение
.
2. Найдите .
Решение
.
3. Пять гостей оставили шляпы в гардеробе, а затем шляпы вернули им в случайном порядке. В скольких случаях из никто не получил свою шляпу? Какая это доля?
Решение
случая из . Доля , то есть около — как и обещал приближённый ответ .
4. Сколько существует раскладок четырёх писем в четырёх конвертах, при которых ровно одно письмо лежит в «своём» конверте?
Решение
Выберем это письмо: способа. Остальные три письма должны лежать «не домой» — беспорядок на трёх письмах: . Всего .
Итог
- Беспорядок — расстановка, в которой ни один элемент не стоит на своём месте; число беспорядков .
- , поэтому .
- ; доля беспорядков стремится к .
- Первые значения: .
