§ 14. Задача о встречах. Беспорядки и совпадения

Рассмотрим множество из элементов

и множество ячеек, в которые размещаются эти элементы:

Сколькими способами можно разместить элементов в ячейках (по одному в каждой) так, чтобы никакой элемент не попал в ячейку Здесь речь идет о знаменитой задаче,

предложенной Монмором и называемой задачей о встречах. Эта задача и ее обобщение, которое будет дано ниже, представляют интерес для различных приложений.

Перестановка, обладающая указанным свойством, называется беспорядком и обозначается через

Для перечисления беспорядков из элементов мы будем использовать формулы, установленные в § 11. Рис. 9 дает пример беспорядка из 6 элементов.

Обозначим через свойство: перестановка ( множество всех перестановок) и такова, что через свойство: обладает совпадением, т. е. для одного и только одного значения для остальных: через свойство: обладает совпадениями, т. е. в точности для значений и для остальных.

Рис. 9

Рис. 10

Например, перестановка, изображенная на рис. 10, обладает двумя совпадениями.

Следовательно, можно записать

Если нам известно соответствующее то мы можем воспользоваться формулами (12.7) и (12.20). Имеем

Если обозначим, как и раньше (см. (12.17)),

то

Легко вычислить

В самом деле,

т. e. равно числу перестановок из элементов. Поэтому

Подставляя (14.7) в (14.6), получаем

Но и есть искомое число беспорядков

Например,

При достаточно большом существует хорошее приближение для (14.11). Из

следует, что отличаются не более чем на Таким образом,

т. е. ашроксимирует тем лучше, чем больше

Понятие беспорядка обобщается, если рассмотреть перестановки с совпадениями. Беспорядок — это перестановка с 0 совпадениями. Обозначим через число перестановок в точности с совпадениями, через -число перестановок с не меньше чем совпадениями, а через с не больше чем совпадениями. В этих обозначениях

Положим также Имеем

В силу (14.11)

Умножая обе части (14.16) на С, получаем

Легко видеть, что

Ниже приводится таблица чисел для Положим для удобства Числа можно представить в виде

Таблица 14.1 (см. скан) Таблица количества перестановок элементов с совпадениями

Дадим удобную рекуррентную формулу для чисел Запишем (14.11), заменяя на

Умножим обе части (14.22) на

Прибавим к обеим частям равенства по

Таким образом,

так как

Получим теперь рекуррентную формулу для В силу

Из получаем

Определяя из (14.26), а из (14.27) и подставляя их в (14.28), находим

Можно построить денумератор для чисел следующим образом. Полагаем

Рассмотрим разложение

Символически можно записать

где разлагается как причем заменяется на

УПРАЖНЕНИЯ

(см. скан)