перестановки шаров (число беспорядков)

[venja]

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

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

[maxal]

Это т.н. число беспорядков. Легко вычисляется классическим методом включений-исключений. См.:
http://mathworld.wolfram.com/Derangement.html
A000166

[venja]

Спасибо. Попробую разобраться.