bulgakov

34. Беспорядки: письма и конверты

Беспорядок — это расстановка, в которой ни один элемент не стоит на своём месте. Сколькими способами можно разложить nn пронумерованных писем по nn пронумерованным конвертам так, чтобы ни одно письмо не попало в конверт со своим номером? Принцип включений и исключений даёт Dn=n!(1−11!+12!−⋯+(−1)nn!)D_n=n!\left(1-\dfrac1{1!}+\dfrac1{2!}-\dots+\dfrac{(-1)^n}{n!}\right), а это число почти равно n!e\dfrac{n!}{e}.

Что пригодится из прошлого: включения и исключения через свойства — формула E(0)=w(0)−w(1)+w(2)−…E(0)=w(0)-w(1)+w(2)-\dots; перестановки — всего способов разложить письма n!n!; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача о письмах и конвертах

Сколькими способами можно разместить nn писем с номерами 1,2,…,n1,2,\dots,n в nn конвертах с номерами 1,2,…,n1,2,\dots,n (по одному письму в конверт) так, чтобы никакое письмо не оказалось в конверте с тем же номером? Число таких размещений обозначим DnD_n.

Три письма

Запишем раскладку тремя цифрами: на ii-м месте номер конверта, в который попало письмо ii. Всего 3!=63!=6 раскладок. В правом столбце — номера писем, лежащих в своём конверте; прочерк значит, что таких писем нет, то есть это беспорядок:

Раскладка Письма дома
123 1, 2, 3
132 1
213 3
231 —
312 —
321 2

Беспорядков два: 231231 и 312312. Значит, D3=2D_3=2.

Для четырёх писем раскладок 2424, беспорядков D4=9D_4=9: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.

Формула

Применим принцип включений и исключений в форме свойств.

Пусть SS — множество всех раскладок nn писем по nn конвертам; ∣S∣=n!|S|=n!. Свойство pip_i (1≤i≤n1\le i\le n): ii-е письмо лежит в ii-м конверте. Нужные нам размещения — те, у которых ни одно свойство не выполнено: Dn=E(0)D_n=E(0).

Найдём w(k)w(k). Если заранее выбрать kk писем и потребовать, чтобы они лежали в своих конвертах, то остальные n−kn-k писем можно разложить по оставшимся n−kn-k конвертам произвольно, то есть (n−k)!(n-k)! способами. Выбрать эти kk писем можно (nk)\dbinom nk способами. Поэтому

w(0)=n!,w(1)=(n1)(n−1)!=n!1!,w(2)=(n2)(n−2)!=n!2!, …,w(k)=(nk)(n−k)!=n!k!, …,w(n)=(nn)(n−n)!=n!n!.\begin{gathered} w(0)=n!,\\ w(1)=\binom n1(n-1)!=\frac{n!}{1!},\\ w(2)=\binom n2(n-2)!=\frac{n!}{2!},\ \dots,\\ w(k)=\binom nk(n-k)!=\frac{n!}{k!},\ \dots,\\ w(n)=\binom nn(n-n)!=\frac{n!}{n!}. \end{gathered}

Проверим последнюю цепочку: (nk)(n−k)!=n!k! (n−k)!⋅(n−k)!=n!k!\dbinom nk(n-k)!=\dfrac{n!}{k!\,(n-k)!}\cdot(n-k)!=\dfrac{n!}{k!}.

Теперь формула включений и исключений:

Dn=w(0)−w(1)+w(2)−⋯+(−1)nw(n)=n!−n!1!+n!2!−⋯+(−1)nn!n!.D_n=w(0)-w(1)+w(2)-\dots+(-1)^nw(n)=n!-\frac{n!}{1!}+\frac{n!}{2!}-\dots+(-1)^n\frac{n!}{n!}.

Вынесем n!n!:

Dn=n!(1−11!+12!−13!+⋯+(−1)nn!).\boxed{D_n=n!\left(1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+\frac{(-1)^n}{n!}\right)}.

Проверка на n=3n=3. 3!(1−1+12−16)=6⋅13=23!\left(1-1+\frac12-\frac16\right)=6\cdot\frac13=2 ✓. На n=4n=4: 24−24+12−4+1=924-24+12-4+1=9 ✓.

Почему Dn≈n!/eD_n\approx n!/e

Число e=2,71828…e=2{,}71828\dots — основание натуральных логарифмов; нам хватит знать, что 1e≈0,368\dfrac1e\approx0{,}368. Известно, что сумма

1−11!+12!−13!+⋯+(−1)nn!→1e(n→∞).1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+\frac{(-1)^n}{n!}\to\frac1e\qquad(n\to\infty).

(Это значение ряда ∑kxkk!=ex\sum_k\dfrac{x^k}{k!}=e^x при x=−1x=-1.) Поэтому для больших nn

Dn=n!(1−11!+⋯+(−1)nn!)≈n!e.D_n=n!\left(1-\frac1{1!}+\dots+\frac{(-1)^n}{n!}\right)\approx\frac{n!}{e}.

Посмотрим на цифры:

nn n!n! DnD_n Dn/n!D_n/n! n!/en!/e
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

Доля беспорядков Dn/n!D_n/n! быстро устанавливается около 1e≈0,3679\dfrac1e\approx0{,}3679 и дальше почти не меняется. Значит, среди всех раскладок писем по конвертам беспорядки составляют примерно 37 %37\,\% при любом большом nn: если раскладывать письма наугад, то примерно в таком проценте случаев ни одно не попадёт «домой».

Любопытное наблюдение. Начиная с n=1n=1 число DnD_n — ближайшее целое к числу n!e\dfrac{n!}e: см. последние два столбца таблицы. Объяснение: ряд знакопеременный, а модули его членов убывают (у такого ряда ошибка меньше первого отброшенного члена), поэтому после nn-го слагаемого ошибка меньше первого отброшенного члена 1(n+1)!\dfrac1{(n+1)!}, и умножение на n!n! даёт ошибку меньше 1n+1≤12\dfrac1{n+1}\le\dfrac12.

Частые ошибки

  • Думать, что почти все раскладки — беспорядки. На самом деле они составляют около 37 %37\,\% всех n!n! раскладок.
  • Забыть про знаки. Слагаемые чередуются: +,−,+,−,…+,-,+,-,\dots
  • Путать «ни одно не на месте» и «ровно одно не на месте». Беспорядок — все письма не на своих местах.
  • Считать w(k)w(k) без коэффициента (nk)\dbinom nk. Выбрать, какие kk писем попадают в «свои» конверты, можно (nk)\dbinom nk способами.

Проверь себя

1. Найдите D4D_4 по формуле.

Решение

D4=4!(1−1+12−16+124)=24−24+12−4+1=9D_4=4!\left(1-1+\frac12-\frac16+\frac1{24}\right)=24-24+12-4+1=9.

2. Найдите D5D_5.

Решение

D5=120−120+60−20+5−1=44D_5=120-120+60-20+5-1=44.

3. Пять гостей оставили шляпы в гардеробе, а затем шляпы вернули им в случайном порядке. В скольких случаях из 120120 никто не получил свою шляпу? Какая это доля?

Решение

D5=44D_5=44 случая из 120120. Доля 44120=1130≈0,367\dfrac{44}{120}=\dfrac{11}{30}\approx0{,}367, то есть около 37 %37\,\% — как и обещал приближённый ответ 1e\dfrac1e.

4. Сколько существует раскладок четырёх писем в четырёх конвертах, при которых ровно одно письмо лежит в «своём» конверте?

Решение

Выберем это письмо: 44 способа. Остальные три письма должны лежать «не домой» — беспорядок на трёх письмах: D3=2D_3=2. Всего 4⋅2=84\cdot2=8.

Итог

  • Беспорядок — расстановка, в которой ни один элемент не стоит на своём месте; число беспорядков DnD_n.
  • w(k)=(nk)(n−k)!=n!k!w(k)=\dbinom nk(n-k)!=\dfrac{n!}{k!}, поэтому Dn=n!(1−11!+12!−⋯+(−1)nn!)D_n=n!\left(1-\dfrac1{1!}+\dfrac1{2!}-\dots+\dfrac{(-1)^n}{n!}\right).
  • Dn≈n!eD_n\approx\dfrac{n!}{e}; доля беспорядков стремится к 1e≈37 %\dfrac1e\approx37\,\%.
  • Первые значения: D1=0, D2=1, D3=2, D4=9, D5=44, D6=265D_1=0,\ D_2=1,\ D_3=2,\ D_4=9,\ D_5=44,\ D_6=265.
ПрактикаЗагружаем тест…