Задача о беспорядках и встречах

Задача о беспорядках и встречах


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