Основной индекс

В математике (и особенно в комбинаторике ) главным индексом перестановки является сумма позиций спусков перестановки . В символах главный индекс перестановки w равен

$\operatorname {maj} (w)=\sum _{w(i)>w(i+1)}i.$

Например, если w задано в однострочной записи как w = 351624 (т. е. w — это перестановка {1, 2, 3, 4, 5, 6} такая, что w (1) = 3, w (2 ) = 5 и т. д.), то w имеет спуски в позициях 2 (с 5 на 1) и 4 (с 6 на 2), и поэтому maj( w ) = 2 + 4 = 6.

Эта статистика названа в честь майора Перси Александра Мак-Магона , который показал в 1913 году , что распределение основного индекса на всех перестановках фиксированной длины такое же, как распределение инверсий . То есть количество перестановок длины n с k инверсиями такое же, как количество перестановок длины n со старшим индексом, равным k . (Эти числа известны как числа Маона , также в честь Мак-Магона. ) На самом деле верен более сильный результат: количество перестановок длины n со старшим индексом k и инверсиями i такое же, как количество перестановок длины n со старшим индексом i и инверсиями k , то есть две статистики равны равнораспределенные. Например, количество перестановок длины 4 с заданным старшим индексом и количеством инверсий указано в таблице ниже.

${\begin{array}{c|ccccccc}&0&1&2&3&4&5&6\\\hline 0&1&0&0&0&0&0&0\\1&0&1&1&1&0&0&0\\2&0&1&2&1&1&0&0\\3&0&1&1&2&1&1&0\\4&0&0&1&1&2&1&0\\5&0&0&0&1&1&1&0\\6&0&0&0&0&0&0&1\end{array}}$

Ссылки

• МакМахон, Пенсильвания (1913). «Индексы перестановок и вывод из них функций одной переменной, связанных с перестановками любого набора объектов». амер. Дж. Математика . 35 (3): 281–322. дои : 10.2307/2370312 . JSTOR   2370312 . .