имеют к инверсий. [Указание, Покажите, что, если взять любую перестановку а\.. .a„ i множества {1,...,п - 1} и поместить число п на все возможные места, обобщенный индекс увеличится на {0,1,..., п - 1} в некотором порядке.]

► 25. [МЗО] (Фоата и Шуценберже.) Пусть Существует перестановка о; - fli ... (in ; обозначим через ind(Q) ее индекс, а через inv(Q) - число ее инверсий.

a) Определите взаимно однозначное соответствие, которое преобразует перестановку q множества {1,..., п} в перестановку /(а), имеющую такие два свойства: (i) ind(/(Q)) = inv(Q); (ii) для \ < j < n число j появляется слева от j -Ь 1 в /(q) тогда и только тогда, когда оно появляется слева от j + 1 в Q. Какая перестановка при этом соответствует /(q), если Q = 19826374 5? Для какой перестановки /(а) = 198263745? [Указание. Если п > 1, напишите q = зпахжгаг • • • XfcQfcCn, где xi, Хк - все элементы, меньшие, че.м а„, если ai < а„; в противном случае xi, Хк - все элементы, большие, чем а„; другие элементы появятся в цепочках (возможно, пустых) Qi, Qfc. Сравните число инверсий h(a) = 01X102X2.. .ОкХк с inv(Q); в этом выражении число Сп отсутствует в h{a).]

b) Обозначьте через / другое однозначное соответствие д, которое имеет два следующих свойства: (i) ind(p(Q)) = inv(Q); (ii) inv(p(Q)) = ind(Q). [Указание. Примите во внимание обратные перестановки.]

26. [М25] Чему равен статистический коэффициент корреляции между числом инверсий и индексом случайной перестановки? (См. упр. 3.3.2-(24).)

27. [М37] Докажите, что в дополнение к (15) существует простое соотношение между inv(ai 02 ... fln) и n-мерной строкой (gi, дг, • • , Qn). Используйте это соотношение для получения производной соотношения (17) в общем случае и формирования алгебраического выражения в виде производящей функции двух переменных

Я„(ги, z) = j2 гу""" "•""г"*"

где суммирование выполняется по всем п! перестановкам oi 02 • • .а„.

► 28. [25] (Р. В. Флойд (R. W. Floyd), 1983.) Если oi 02 •.. о„ - перестановка множества {1, 2,..., п}, то его суммарное смещение определяется как Ylj=i 14 ~J\- Найдите верхнюю и нижнюю границы сзммарного смещения в терминах количества инверсий.

29. [28] Если тг = О] 02 ... Сп и тг = al а2 ... ап суть перестановки множества {1, 2,..., п}, то обозначим их произведение тгтг как а ... а. Пусть inv(7r) обозначает количество инверсий, как й в упр. 25. Покажите, что 1пу(7Г7г) < inv(7r) + inv(7r) и что равенство соблюдается тогда и только тогда, когда тгтг расположено "ниже" тг (как введено в упр. 12).

*5.1.2. Перестановки мультимножества

До сих пор мы рассматривали перестановки множества элементов, но это частный случай перестановок мультимножества. (Мультимножество - это то же самое, что и множество, но в нем могут содержаться одинаковые элементы. Некоторые основные свойства мультимножеств обсуждались в разделе 4.6.3-19.) Рассмотрим, например, мультимножество

М = {a,a,a,b,b,c,d,d,d,d], (1)

в котором содержится 3 элемента а, 2 элемента Ь, 1 элемент с и 4 элемента d. Повторения элементов в мультимножестве можно записать и другим способом:

М = {3-а, 2-Ь, с, 4-d}. (2)

Перестановка мультимножества* М - это некоторое расположение его элементов в ряд, например

cabddabdad.

С другой стороны, такую последовательность можно назвать буквенной строкой, содержащей 3 буквы а, 2 буквы Ь, 1 букву с и 4 буквы d. Сколько существует перестановок мультимножества М? Если бы мы рассматривали все элементы М как различные, обозначив их как ai, 02, 03, hi, b2, ci, di, d2, rfs, d, то получили бы 10! = 3,628,800 перестановок, но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка М встретилась бы ровно 3! 2! 1! 4! = 288 раз, поскольку в любой из них индексы при буквах можно расставить 3! способами, при bk (независимо) - 2! способами, при Ск - одним способом, при dk - 4! способами соответственно. Поэтому число перестановок М равно

= 12,600.

3!2!1!4!

В применении к общему случаю те же рассуждения показывают, что число перестановок любого мультимножества равно полиномиальному коэффициенту

где П1 - число элементов первого типа, пг - число элементов второго типа и т. д., an = щ + П2 + - общее число элементов. Количество перестановок множества было известно еще в древние времена. В древнееврейской Книге Творения (ок. 100 г. н. э.), наиболее раннем литературно.м произведении иудейского философского мистицизма, даны верные значения первых семи факториалов, после чего говорится: "Продолжай, и получишь числа, которые уста не могут произнести, а ухо не может воспринять". [Сефер Этзпрах, конец части 4. См. Solomon Gandz, Studies in Hebrew Astronomy and Mathematics (New York: Ktav, 1970), 494-496; Aryeh Kaplan, Sefer Yetzirah (York Beach, Maine: Samuel Weiser, 1993).] Это первый известный в истории подсчет числа перестановок. Второй встречается в индийском классическом произведении Анупогадвара-сутра (ок. 500 г. н. э.), правило 97, в котором приводится формула числа перестановок шести элементов, которые не расположены ни в порядке возрастания, ни в порядке убывания:

6x5x4x3x2x1-2.

[См. G. Chakravarti, Bull. Calcutta Math. Soc. 24 (1932), 79-88. "Ануйогадвара-сутра" - одна из книг канонов джайнизма, религиозной секты, распространенной в Индии.] Соответствующее правило для мультимножеств впервые, по-видимому, встречается в книге "Лилавати", написанной Бхаскарой Ахарьей (ок. 1150 г.) (разд. 270-271). У Бхаскары это правило сформулировано весьма сжато и проиллюстрировано лишь двумя простыми примерами: {2,2,1,1} и {4,8,5,5,5}. В результате в английском переводе это правило не сформулировано корректно, впрочем, имеются некоторые сомнения относительно того, понимал ли сам Бхаскара, о чем говорил.

* В англоязычной литературе такие перестановки иногда называют "permatution" в отличие от "permutation".

Вслед за этим правилом Бхаскара приводит интересную формулу

(4 + 8 + 5 + 5 + 5) X 120 X 11111 5x6

для суммы 20 чисел 48555 + 45855 + •. Верное правило для нахождения числа перестановок в случае, когда только один элемент может повторяться, найдено независимо немецким ученым иезуитом Атанасиусом Кирхером (Athanasius Kircher) в его многотомном труде о музыке [Musiirgia Universalis 2 (Rome: 1650), 5-7]. Кирхера интересовал вопрос о количестве мелодий, которые можно создать из данного набора нот; для этого он придумал то, что называл "музарифметикой! На стр. 18-21 своего труда он дает верное значение числа перестановок мультимножества {т С, п D] при нескольких значениях тип, хотя описал он свой метод вычислений лишь для случая п = 1. Общее правило (3) появилось позже в книге Жана Престэ (J. Prestet) Elemens de Mathematiques (Paris: 1675, 351-352), в которой содержится одно из первых изложений комбинаторной математики, написанных в Западной Европе. Престэ верно сформулировал правило для произвольного мультимножества, но проиллюстрировал его лишь простым примером {а, а, Ь, Ь, с, с}. Он особо отметил, что деление на сумму факториалов, которое он считал естественным обобщением правила Кир.хера, было бы ошибкой. Несколько лет спустя Джон Валлис (John WaUis) в своей книге Discourse of Combinations (Oxford: 1G85, Chapter 2), опубликованной вместе с его же Treatise of Algebra, рассмотрел это правило более подробно.

В 1965 году Доминик Фоата (Dominique Foata) ввел одно интересное понятие, так называемое "соединительное произведение" (intercalation product), которое позволило распространить лшогие известные результаты, касающиеся обычных перестановок, на обилий случай перестановок \13лыпмножества. [См. РиЫ. Inst. Statistique, Univ. Paris, 14 (1965), 81-241; a также Lecture Notes in Math. 85 (Springer, 1969).] Предполагая, что элементы мульти.мпожества каким-то способо.м линейно угюрядочены, можно рассмотреть двухстрочную нотацию, например

а а а ь Ъ с d d d d\ cabddabdad

Здесь верхняя строка содержит элементы М в порядке неубывания и нижняя - это сама перестановка. Соединительное произведение ajp двух перестановок мультимножеств Q и - это перестановка, которая получается, если (а) взять двухстрочные обозначения для а и Р, (Ъ) записать соответствующие строки в одну и (с) рассортировать столбцы так, чтобы элементы верхней строки расположились в порядке неубывания. Сортировка должна быть устойчивой в том смысле, что взаимное расположение элементов нижней строки сохраняется, если соответствующие элементы верхней строки равны. Например, с а d аЬ j bddad = cabddabdad, так как

а а b с d\ (а b d d d\ faaabbcdddd

с a d a bj уь d d a dj {c a b d d a b d a dj Нетрудно видеть, что операция соединительного произведе1Шя ассоциативна,

т. е.

(ат/3)т7 = ат(/т7), (6)