Задача о беспорядках и встречах
Задача о беспорядках и встречах
популярной литературе по теории вероятностей часто встречается
Задача о рассеянной секретарше. Секретарше нужно отправить п различных писем по п различным адресам. Она подписывает конверты и случайным образом вкладывает письма в конверты. Какова вероятность того, что ни одно письмо не дойдет до своего адресата ?
Оказывается, искомая вероятность не так мала, как может показаться на первый взгляд, и, что замечательно, имеет пределом . Данная задача является (литературным) вариантом широко известной комбинаторной задачи о беспорядках, решением которой мы сейчас и займемся.
Задача о беспорядках и встречах
Перестановка называется беспорядком, если для любого . Через Dn обозначим число всех беспорядков из п элементов. Заметим, что в задаче о секретарше искомая вероятность Рп равна отношению Dn к общему числу всех перестановок п элементов: Рп =
Пусть — множество всех перестановок чисел 1 множество тех перестановок, у которых на t-м месте стоит число ). Тогда множество беспорядков совпадает с пересечением множеств Dn равно его мощности. Для того чтобы применить формулу включения-исключения, нужн о найти мощности соответствующих множеств.
Имеем: (так как во всех перестановках, входящих в Ai, положение одного числа фиксировано, то число таких перестановок совпадает с числом перестановок п- 1 элементов), если (здесь фиксированы положения двух элементов); вообще: мощность пересечения к множеств равна (к чисел «знают» свои места, переставляются оставшиеся п-к).
Заметим, наконец, что п множеств Л, образуют С„ попарных пересечений, ..., пересечений по к множеств (к ^ п). Таким образом,
Возвратимся (в последний раз) к задаче о секретарше. Из полученной формулы для числа беспорядков следует:
Задача о беспорядках и встречах
Рекуррентные формулы для числа беспорядков. На основе формулы (1) получим интересные соотношения для
. Полученное рекуррентное соотношение
очень похоже на соотношение, позволяющее рекуррентно вычислять фаеториалы: (все отличие — слагаемое (-1)п+|). В связи с этим обстоятельством число беспорядков Dn иногда называют субфакториалом (или псевдофакториалом). Зная, что JD, = 0, с помощью (2) найдем несколько значений Dn:
. Еще одно соотношение получается так:
). Заметим, что рекуррентной зависимости
наряду с последовательностью псевдофакториалов Dn удовлетворяет и последовательность (обычных) факториалов п! (убедитесь в этом самостоятельно).
Обобщением задачи о беспорядках является задана о встречах. Говорят, что перестановка чисел п имеет к встреч, если ровно к чисел «остаются на своих местах» (когда порядковый номер элемента в перестановке совпадает с его величиной: Число перестановок п элементов с к встречами обозначим Д»,*. Отметим несколько частных случаев: Последнее равенство вытекает из того, что если все элементы перестановки, кроме одного, занимают «свои» места, то и этому элементу не остается ничего другого, как занять место, чей номер совпадает с ним, и, таким образом, ровно встреч не может быть!
Каждую перестановку п элементов с к встречами можно сгенерировать, выполняя следующую процедуру:
Задача о беспорядках и встречах
1-й шаг. Выбрать к элементов, остающихся на своих местах.
2-й шаг. Оставшиеся п - к элементов переставить так, чтобы ни один из них
не занял «своего» места.
Первый шаг выполняется способами, второй — £)„_* способами. С помощью правила произведения получаем формулу для числа встреч |