2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

 
 
 
 
Сообщение22.12.2007, 11:18 
Спасибо. Попробую разобраться.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group