E{n) = {(ai,a>) I i > j, at > Uj}

множество ее "неинверсий"

a) Докажите, что (тг) и Е{7г) транзитивны. (Множество 5 зпорядоченных пар называется транзитивным, если для любых (а,Ь) и (Ь, с), принадлежащих 5, пара (а, с) также принадлежит S.)

b) Обратно, пусть Е - любое транзитивное подмножество множества Т = {{х,у) \ 1 < у < X < п}, дополнение которого Е = Т \ Е также транзитивно. Докажите, что существует перестановка тг, такая, что (тг) = Е.

12. [M2S] Используя обозначения, принятые в предыдущем упражнении, докажите, что если 7Г1 и 7Г2 - перестановки, а, Е - минимальное транзитивное множество, содержащее E{ni)DE{TT2), то Ё - также транзитивное множество. [Следовательно, если мы говорим, что тп находится "над" 7Г2, когда (тп) С (тгг), то определена решетка перестановок; существует единственная "самая низкая" перестановка, находящаяся "над" двумя данными перестановками. Диаграмма решетки при п = 4 представлена на рис. 1.]

13. [М23] Известно, что в разложении определителя половина членов выписывается со знаком "-I-", а половина - со знаком "-". Другими словами, при п > 2 перестановок с четным числом инверсий ровно столько же, сколько с нечетным. Покажите, что вообще, при п > т количество перестановок с числом инверсий, конгруэнтным t по модулю т, равно п\/т, независимо от того, каково целое число t.

14. [М24] (Ф. Франклин (F. Franklin).) Разбиение числа п на /г различных частей - это

представление п в виде суммы n = pi -Ьрг Н-----hpjt, где pi > рг > > pjt > 0. Например,

разбиения числа 7 на различные части таковы: 7, 6 -Ь 1, 5 -Ь 2, 4-1-3, 4 -I- 2 -Ь 1. Пусть Д(п) - число разбиений п на, к различных частей. Докажите, что Sj, (-!)*/*:(«) = О, если только п не представляется в виде (3j i j)/2 при некотором неотрицательном целом j; в этом случае сумма равна (-1)-. Например, для п = 7 сумма равна -1-1-3 - 1 = 1, потому что 7 = (3 • 2 -f- 2)/2. [Указание. Представьте разбиения в виде массива точек, в г-й строке которого имеется рг точек, 1 < г < к. Найдите наименьшее j, такое, что Pj+i < р; - 1, и обведите крайние справа точки первых j строк. Если j < Рк, то эти j точек можно, как правило, изъять из массива, повернуть на 45° и поместить в новую, {к+1)-ю, строку. С другой стороны, если j > рк, то обычно можно изъять из массива к-ю строку точек, повернуть ее на 45° и поместить справа от обведенных точек (рис. 2). В результате в большинстве случаев разбиения с четным числом строк и разбиения с нечетным числом строк группируются в пары; таким образом, в сумме следует учитывать только непарные разбиения.]

Рис. 2. Соответствие Франклина между разбиениями на различные части.

Замечание. Как следствие получаем формулу Эйлера:

(1 - z)(l - z){l -z)... = l-z-z+z + z -z-z +

- ОО < J < ОО

Поскольку производящая функция для обычных разбиений (не обязательно на различные части) равна X!p(n)z" = 1/(1 - z){l - г)(1 - z)..., получаем неочевидное рекуррентное соотношение для числа разбиений:

р{п) =р{п- 1) +р{п - 2) -р(п- 5) -р{п-7) +р{п- 12) +p(n- 15)----.

15. [М23] Докажите, что соотношение (16) - это производящая функция для числа разбиений не более чем на п частей, т. е. докажите, что коэффициент при г"* в 1/(1 - z){l - z)... (1 - 2") равен числу способов представления т в виде суммы m = pi +р2 + •• +р„, где pi > р2 > > Рп > 0. [Указание. Нарисуйте точки, как в упр. 14, и покажите, что существует взаи.мно однозначное соответствие между п-мерными строками чисел (pi,p2,... ,Рп), такими, что pi > Р2 > • • • > Рп > О, и последовательностями (Pi, Рг, Рз,...), такими, что п > Pi > Р2 > Рз > • • > О, обладающее тем свойством,

что pi +Р2 Н-----hPn = Pi + Р2 + Рз Н----• Иными словами, покажите, что разбиениям не

более чем на п частей соответствуют разбиения на части, не превосходящие п.]

16. [М25] (Л. Эйлер.) Докажите следующие тождества, интерпретируя обе части соотношений в терминах разбиений:

П (1 А-г) (1 д2,

П (1 + q) = (1 + г)(1 + 9)(1 + q)

+ 1-, + (1-,)(1-,)+ /J}j

17. [20] Каковы 24 тетрады (91,92,93, 94), для которых в соответствии Мак-Магона, определенном в конце этого раздела, (р1,Р2,Рз,Р4) = (0,0,0,0)?

18. [МЗО] (Т. Hibbard, САСМ 6 (1963), 210.)

Пусть п > О и последовательность 2" п-разрядных целых чисел Ао,..., -Y2n-i получена случайным образом, причем каждый разряд каждого числа независимо от других разрядов принимает значение 1 с вероятностью р. Рассмотрим последовательность Хо ф О, Al ф 1, АГг"-1 ф (2" - 1), где ф - операция "исключающее или" над двоичными представлениями. Так, если р = О, то последовательность будет такой: 0,1,..., 2" - 1; если р = 1, то она будет такой: 2" -1,..., 1,0; если же р = 5, то каждый эле.мент последовательности - случайное число между О и 2" - 1. Вообще же, при разных р это хороший способ получения последовательности случайных целых чисел со смещенным числом инверсий, в то время как распределение элементов последовательности, рассматриваемой как единое целое, равномерно (uniform) в том смысле, что все п-разрядные целые двоичные числа будут иметь одинаковые распределения. Определите среднее число инверсий в такой последовательности как функцию от вероятности р.

19. [М28] (К. Мейер (С. Meyer).) Если тип - взаи.мно простые числа, то известно, что последовательность (т mod п){2т mod п).. .{{п - 1)т mod п) представляет собой перестановку множества {1,2,...,п - 1}. Покажите, что число инверсий этой перестановки может быть выражено в терминах сумм Дедекинда (см. п. 3.3.3).

20. [М4З] Следующее знаменитое тождество, принадлежащее Якоби [Fundamenta Nova Theorise Punctionum EUipticarum (1829), §64], лежит в основе многих замечательных соотношений, содержащих эллиптические функции;

- = (1 - ц){1 - гО{1 - ™){1 - Л)(1 - ™)(1 - иг;)...

- оо<>< + оо

Если, например, положить и = z, v = z, то получится формула Эйлера из упр. 14. Ес1и положить 2 = y/u/v, q = s/uv, то получим

llii---z){i--z-)ii-)= y: (-lГv

к>1 ~oo<n<oo

Существует ли комбинаторное доказательство тождества Якоби, аналогичное доказательству Франклина для частного случая из упр. 14? (Таким образом, нужно рассмотреть "комплексные разбиения"

тп + пг = (pi + q\i) + (рг + дгг) Н-----\-{Рк + qki),

тд,е Pj +qji - различные ненулевые комплексные числа; pj, g,, - неотрицательные целые числа, причем \pj - qj\ < 1. Согласно тождеству Якоби число таких представлений с четными к равно числу представлений с нечетными к, еат только т и п не являются соседними треугольными числами!) Какими еще замечательными свойствами обладают комплексные разбиения?

► 21. [М25] (Г. Д. Кнотт (G. D. Knott).) Покажите, что перестановку oi...On можно получить с помощью стека (см. упр. 2.2.1-5 или 2.3.1-6) тогда и только тогда, когда Cj < Cj+i + 1 при 1 < J < п (см. обозначения в упр. 7).

22. 1М26] Задана перестановка oi ог • • a,i множества {1,2,..., п}. Пусть hj - число индексов г < j, таких, что at € {aj + 1, aj + 2,. .., Oj+i}. (Если aj+i < Oj, элементы этого множества "оборачиваются" от п к 1. Когда j = п, используется множество {on-1-l, о„--2,..., п}.) Например, перестановка 591826473 приводит к hi.. .hg = 00121424 6.

a) Докажите, что oi ог . • о„ можно восстановить по числам hi hz - hn-

b) Докажите, что /ii -f /гг Н-----1- /in - суть индексы ai ог ... о„.

► 23. [М27] (Русская рулетка.) Группа из п человек, приговоренных к смерти, которые отдают предпочтение теории вероятности перед теорией чисел, могла бы, рассевшись по кругу и несколько модифицировав метод Иосифа (упр. 2), попробовать такой способ самоубийства. Первый приговоренный нажимает спусковой крючок револьвера, направив его себе в висок; с вероятностью р произойдет роковой выстрел, и он покинет круг. Затем револьвер переходит ко второму приговоренному и он делает то же самое. Далее сюжет повторяется по кругу с постоянной вероятностью р > О до тех пор, пока будет кому его продолжать.

Пусть Uj = к, если А;-му приговоренному выпал j-u роковой выстрел. Докажите, что порядок "выбывания" oi аг ... а„ появится с вероятностью, которая является функцией только п, р и индекса дуальной перестановки (п -Ь 1 - о„)... (п -Ь 1 - ог) (п -Ь 1 - oi). Какой порядок "выбывания" наименее вероятен?

24. [М26] Для заданного множество целых чисел t{l)t{2).. .t{n), где t{j) > j, обобщенный индекс перестановки oi ог ... а„ равен сумме всех нижних индексов j, таких, что aj > t{aj+i), плюс общее число инверсий, таких, что i < j и t(aj) > т > aj. Значит, если t{i) = j для всех j, обобщенный индекс совпадает с обычным индексом, но при *(j) н для всех j это будет число инверсий. Докажите, что число инверсий, для которых обобщенный индекс равен к, - то же самое, что и число перестановок, которые