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

Пусть множество . Рассмотрим перестановки элементов множества .

Элемент перестановки называется неподвижным, если , т.е. элемент стоит на своем месте.

Например:

при

5 2 4 3 1 – элемент “2” – неподвижный;

1 2 3 4 5 – все элементы неподвижны.

Беспорядком называется перестановка, не имеющая неподвижных элементов, т.е.

Постановка задачи:

Определить - количество беспорядков в n-элементном множестве, или количество перестановок чисел таких, что ? называют субфакториалом.

Решение:

Общее число перестановок – .

Обозначим через такое свойство перестановки, когда i-й элемент стоит на своем месте, т.е. а_i = i.

- число перестановок, обладающее свойством , т.е. .

- в этих перестановках только один элемент находится на своем месте, остальные – в беспорядке. , т.к. число перестановок не зависит от того, какой именно элемент находится на своем месте.

Обозначим через - количество перестановок, в которых только два элемента находятся на своих местах, , … , – количество перестановок, в которых только элементов находятся на своих местах .

По формуле включений-исключений имеем:

(1)

Распишем формулу:

Задача o встречах

Постановка задачи:

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

Иначе: нас интересуют перестановки, в которых точно элементов неподвижны.

Решение:

Из общего числа элементов некоторым образом выбирается , которые остаются на своих местах, остальные элементов находятся в беспорядке. Количество способов, которыми можно переставить элементов при таких условиях, равно .