2014 dxdy logo

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

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




 
 Все циклы всех подстановок -- сколько их
Сообщение15.09.2010, 00:46 
Сколько всего циклов во всех подстановках порядка N?
У меня получается, что их количество равно
N!(1 + 1/2 + 1/3 + 1/4 + ... + 1/N)
Кстати, эта срезка гармонического ряда в скобках дает не только общее количество всех циклов, но и количество циклов каждой длины. Циклов длины 8 будет 1/8N!, а длины 17 будет 1/17N! — коротких циклов больше, длинных меньше.
Практика это подтверждает, однако я не умею объяснить, как пришел к этой формуле, и не умею доказать ее справедливость.
Надежда только на то, что я не первый ее нашел. В этом случае есть приличный выход из положения — сослаться на солидный источник, где эта формула приводится с обоснованиями. Вот только какой источник?
Буду весьма признателен, если кто-то подскажет.

С уважением,
Лев Магазаник

 
 
 
 Re: Все циклы всех подстановок -- сколько их
Сообщение15.09.2010, 09:59 
Если не только из "солидных", а рассматриваете и популярные, то
порекомендую недавнюю статью в "Кванте" на эту тему Два тюремщика
http://kvant.mirror1.mccme.ru/pdf/2008-05.pdf стр.44.

Очень интересная задача с парадоксальным ответом, которая использует приведенный вами факт с неожиданной стороны...

 
 
 
 Re: Все циклы всех подстановок -- сколько их
Сообщение15.09.2010, 10:45 
Cash
Благодарю за ссылку. Конечно, такое мое счастье, что на самом захватывающем месте забарахлил Adobe Reader, не хочет читать 49 страницу "Кванта", но это не беда, найду копию, которая читается.
А главное, что один из авторов статьи Лецко -- он уважаемый участник здешнего форума, его ник VAL. Словом, теперь есть кого спросить, есть авторитетный источник.

С уважением, Лев Магазаник

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


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