Последний раз редактировалось PAV 19.02.2010, 16:46, всего редактировалось 1 раз. |
уточнил заголовок |
Есть некоторый класс нетривиальных задач, с которыми я достаточно часто сталкивался в вопросах студентов. К сожалению, пока приходилось предлагать ручной подсчет вариантов, если параметры задачи не делали его невозможным. Что бы решать эти задачи в общем виде, желательно получить решение такой вспомогательной задачи.
В лунках с номерами 1,2,3,...,n первоначально расположены шарики с номерами 1,2,3,...,n. Пусть сначала номер шарика и лунки совпвдают (каждый шарик - в своей лунке). Пусть Q(n) означает число таких перестановок этих n шаров, при которых каждый шарик находится не в своей лунке (номер шарика и лунки не совпадают). Вопрос: найти формулу (хотя бы рекурентную) для Q(n). Для малых n легко вручную посчитать: Q(2)=1, Q(3)=2, Q(4)=9 . Как-то должна работать индукция. Может быть кому-нибудь это тоже интересно?
|