Сколько существует перестановок длины m, являющихся беспорядком? задан 29 Апр '15 22:53 587896 |
Сколько существует перестановок длины m, являющихся беспорядком? задан 29 Апр '15 22:53 587896 |
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
29 Апр '15 22:53
показан
403 раза
обновлен
29 Апр '15 23:22
https://ru.wikipedia.org/wiki/Беспорядок_%28перестановка%29
Есть вывод формулы. http://neerc.ifmo.ru/wiki/index.php?title=Формула_включения-исключения#.D0.A0.D0.B5.D0.BA.D1.83.D1.80.D1.80.D0.B5.D1.82.D0.BD.D0.BE.D0.B5_.D1.81.D0.BE.D0.BE.D1.82.D0.BD.D0.BE.D1.88.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B4.D0.BB.D1.8F_.D0.BD.D0.B0.D1.85.D0.BE.D0.B6.D0.B4.D0.B5.D0.BD.D0.B8.D1.8F_.D0.BA.D0.BE.D0.BB.D0.B8.D1.87.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D0.B1.D0.B5.D1.81.D0.BF.D0.BE.D1.80.D1.8F.D0.B4.D0.BA.D0.BE.D0.B2
Имеется в виду перестановка, в которой никакой символ не стоит на своём месте. Например: 231. Задача о подсчёте таких перестановок хорошо известна. Её можно найти в литературе под разными именами. Например, "задача о рассеянном почтальоне". Она упоминалась на форуме не один раз -- например, здесь. У Виленкина это точно есть (возможно, под другим заголовком).