Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Сколько инверсий во всех перестановках элементов ( натуральных чисел ) вместе?
Сложность для меня в том, что нужно каким-то образом учесть перестановки элементов. ?
EtCetera
Re: О числе инверсий во всех перестановках элементов
18.09.2010, 19:18
Как было сегодня выяснено, для перестановок справедлив принцип "мы с Тамарой ходим парой", суммарное количество инверсий для такой парочки зависит только от . Всего же перестановок из элементов ровно штук (про количество пар, думаю, догадаетесь).
maxal
Re: О числе инверсий во всех перестановках элементов
18.09.2010, 19:47
Любая пара элементов образует инверсию ровно в половине всех перестановок, откуда ответ получается мгновенно.