Распечатать запись Распечатать запись

Число перестановок

Задача. Чему равно число таких перестановок (a_1,a_2,\ldots,a_n) чисел (1,2,\ldots,n), которые удовлетворяют условию a_k\ne k при всех k?

Это довольно известная задача, она встречается в разных формулировках, например, такой:

Несколько человек решили подарить друг другу подарки на Рождество. Каждый приготовил один подарок и подписал на нем свое имя. Друзья решили распределить подарки случайным образом. Они написали свои имена на листочках бумаги и положили в шапку. Каждый тянет листочек, и если получилось так, что у всех имена на вытащенных ими листках не совпали с их собственными именами (а иначе какой же это подарок — самому себе?), то распределение подарков состоялось. Сколькими различными способами могут распределиться подарки между друзьями?

Показать решение

Комментариев: 2

  1. 1 Владимир:

    В ответе в знаменателе должно быть k!. И ещё выкладки не совсем корректны: по формуле включения-исключения мы посчитали перестановки, которые не удовлетворяют условию, т.е. нужно это число вычесть из n!

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Владимир, спасибо! Исправила.

    [Ответить]

Оставьте свой отзыв

Добавить изображение