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

Задача. Чему равно число таких перестановок

    \[(a_1,a_2,\ldots,a_n)\]

чисел

    \[(1,2,\ldots,n)\]

, которые удовлетворяют условию

    \[a_k\ne k\]

при всех

    \[k\]

?

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

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

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

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

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

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

    [Ответить]

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

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

    [Ответить]

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

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