close

Вход

Забыли?

вход по аккаунту

"Современная математика" в Дубне

код для вставкиСкачать
Летняя школа «Современная математика»
Дубна, июль 
Е. Ю. Смирнов
Диаграммы Юнга,
плоские разбиения
и знакочередующиеся матрицы
Москва
Издательство МЦНМО

УДК .+.
ББК .+.
C
C
Смирнов Е. Ю.
Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. — М.: МЦНМО, . —  с.
ISBN ----
Сколько есть способов разбить натуральное число в сумму нескольких
слагаемых, если суммы, отличающиеся только порядком слагаемых, считаются одинаковыми? Оказывается, что на этот, казалось бы, элементарный
вопрос нет простого ответа. Зато теория, начинающаяся с этого вопроса,
оказывается очень интересной, а ее результаты находят применение в самых
разных разделах математики и математической физики.
Настоящая брошюра написана по материалам лекций, прочитанных автором на летней школе «Современная математика» в Дубне в июле  года.
Она рассчитана на старшеклассников и студентов младших курсов.
ББК .+.
Редакторы:
В. А. Клепцын, Г. А. Мерзон
ISBN ----
© Смирнов Е. Ю., .
© МЦНМО, .
Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Лекция . Разбиения . . . . . . . . . . . . . . . . . . . . .
.. Разбиения и диаграммы Юнга . . . . . . . . . . . .
.. Напоминание о производящих функциях . . . .
.. Разбиения на нечетные и различные слагаемые
.. Пятиугольные числа . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Лекция . q-биномиальные коэффициенты . . . . . . . . . . .
.. Диаграммы Юнга и биномиальные коэффициенты . . .
.. Определение q-биномиальных коэффициентов . . . . .
.. Производящая функция Эйлера как следствие формулы
для q-биномиальных коэффициентов . . . . . . . . . . . . . . .
.. q-бином Ньютона . . . . . . . . . . . . . . . . . . . . . . . . .
.. Тождество Якоби для тройного произведения . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.





. . . . . . .
. . . . . . .
. . . . . . .



. . . . . . .
. . . . . . .
. . . . . . .



Лекция . Плоские разбиения и формула Макмагона . . . . . . .
.. Плоские разбиения . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Подсчет числа плоских диаграмм высоты  . . . . . . . . . .
.. Детерминантная формула Линдстрёма—Гесселя—Вьенно .
.. Определитель Вандермонда . . . . . . . . . . . . . . . . . . . .
.. Вычисление числа плоских разбиений в параллелепипеде
.. Производящие функции и формула Макмагона . . . . . . .
.. Предельная форма формулы Макмагона . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.








Лекция . Знакочередующиеся матрицы и их связь с плоскими
разбиениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.. Тождество Деснано—Якоби . . . . . . . . . . . . . . . . . . . . . . . .
.. Комбинаторное доказательство тождества Деснано—Якоби . . .
.. «Конденсация определителей» по Доджсону . . . . . . . . . . . . . .
.. λ-определители и знакочередующиеся матрицы . . . . . . . . . . .
.. Гипотеза о знакочередующихся матрицах . . . . . . . . . . . . . . .
.. Плоские разбиения с дополнительными симметриями . . . . . . .
.. Вполне симметричные самодополнительные плоские разбиения
.
.
.
.
.
.
.
.








Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Введение
Разбиением натурального числа называется его представление
в виде суммы натуральных слагаемых. При этом порядок следования слагаемых не учитывается, то есть разбиения, отличающиеся
только порядком слагаемых, считаются одинаковыми. Задача о подсчете количества разбиений p(n) числа n на первый взгляд похожа
на другие задачи элементарной комбинаторики — скажем, о числе
перестановок или сочетаний — однако она оказывается более сложной: число разбиений не выражается простой замкнутой формулой.
Тем не менее, кое-что — и довольно многое! — о последовательности чисел разбиений сказать все-таки удается.
Так, например, их
P
производящую функцию — степенной ряд
p(n)q n — оказывается
возможным представить в виде бесконечного произведения:
∞
∞
Q
P
p(n)q n =
(1 − q k )−1 .
n=0
k=1
Впервые это было сделано Леонардом Эйлером в XVIII в. Ему же
принадлежит еще один замечательный результат: вычисление ряда,
обратного к этой производящей функции. Его коэффициенты, в отличие от коэффициентов предыдущего ряда, оказывается возможным выписать явно. Это утверждение называется пентагональной
теоремой Эйлера.
Разбиения удобно представлять графически при помощи так называемых диаграмм Юнга. Это фигуры, состоящие из квадратиков,
причем число квадратиков в очередной строке диаграммы равняется одному из слагаемых разбиения. Слагаемые при этом считаются
упорядоченными по убыванию. Например, разбиению 5 + 3 + 3 + 1
числа 12 соответствует такая диаграмма Юнга:
Итак, p(n) — это количество диаграмм Юнга, состоящих из n квадратиков.
Введение

У диаграмм Юнга можно рассмотреть и трехмерный аналог: это
будут объемные фигуры, состоящие из кубиков, выстроенных в виде пирамидки «в углу комнаты» (в координатном октанте) таким
образом, что снизу, сзади и слева от каждого кубика располагается
либо кубик, либо координатная плоскость (т. е. «стена комнаты»).
Пример трехмерной диаграммы Юнга, состоящей из  кубиков,
изображен на рисунке.
Для числа трехмерных диаграмм Юнга тоже можно написать
производящую функцию, которая оказывается похожей на формулу
Эйлера. Это было проделано в начале XX в. британским военным
и математиком Перси Макмагоном. Интересно, что аналог этой
формулы в размерности  и выше неизвестен.
Как двумерные, так и трехмерные диаграммы Юнга возникают
во многих задачах, в том числе в таких, которые на первый взгляд
никак не связаны с разбиениями чисел. Мы расскажем об одной
из них — гипотезе о знакочередующихся матрицах (alternating sign
matrix conjecture), которая возникла в -х гг. в работах Миллса, Роббинса и Рамси, вдохновленных трудами Ч. Л. Доджсона (он
же — автор «Алисы» Льюис Кэрролл), и была доказана в середине
-х гг. Д. Зельбергером и Г. Купербергом. В этой гипотезе, вызвавшей значительный интерес специалистов по комбинаторике,
речь идет о подсчете числа матриц определенного вида, элементами
которых могут быть только нули и ±1. Таких матриц оказывается столько же, сколько трехмерных диаграмм Юнга, удовлетворяющих определенным условиям симметрии, хотя построить какуюлибо естественную биекцию между этими двумя множествами никому пока что не удалось.
Об этой брошюре. Эта брошюра написана по материалам миникурса из четырех лекций, прочитанных автором на XIII летней
школе «Современная математика» в Дубне в июле  г. Большинство слушателей составляли студенты первых двух курсов матема-

Введение
тических специальностей. Содержание глав почти точно соответствует фактически читавшимся лекциям; при этом текст получился
более подробным за счет того, что в нем в ряде мест восстановлены
детали, опускавшиеся на лекциях ввиду нехватки времени.
Первые две лекции посвящены разбиениям и двумерным диаграммам Юнга. Они представляют собой законченный сюжет, не зависящий от остального текста; их материал доступен подготовленному школьнику. Третья и четвертая лекции рассчитаны скорее на
младшекурсников; для их понимания нужно знать, что такое группа
перестановок и определитель матрицы.
Помимо большого количества упражнений, приведенных в тексте, в конце каждой из первых трех лекций приводится по несколько
задач. Эти задачи предлагались слушателям миникурса для самостоятельного решения. Сложность задач и упражнений довольно
неравномерная, так что призываем читателя не отчаиваться, если
какая-то из задач не будет получаться.
Для экспертов. Приведем краткое содержание брошюры, рассчитанное «на профессионалов». В первой лекции определяются
разбиения, диаграммы Юнга, выводится эйлеровская производящая функция для числа разбиений и формулируется пентагональная теорема Эйлера. Этот материал является классическим и может
быть найден в любом учебнике комбинаторики.
Вторая лекция посвящена доказательству пентагональной теоремы. Для этого мы излагаем теорию q-биномиальных коэффициентов, доказываем q-аналог бинома Ньютона и выводим из него формулу Якоби для тройного произведения — после чего пентагональная теорема получается как простое следствие из этой формулы. Такое доказательство является более сложным, чем классическое биективное доказательство пентагональной теоремы, изложенное, например, в замечательной статье Д. Б. Фукса [], однако оно кажется
нам более концептуальным, поскольку в нем естественно возникает
ряд понятий и утверждений, представляющих и самостоятельный
интерес.
В третьей лекции вводятся плоские разбиения (трехмерные диаграммы Юнга) и доказывается формула Макмагона для числа плоских разбиений в заданном прямоугольном параллелепипеде, а также ее q-аналог, описывающий производящую функцию для числа
таких разбиений. Как следствие из этой формулы получается аналог
Введение

формулы Эйлера (также принадлежащий Макмагону) — производящая функция для плоских разбиений без каких-либо ограничений
на их размер. Основным инструментом для доказательства этих результатов служит теорема Линдстрёма—Гесселя—Вьенно о непересекающихся путях.
Последняя, четвертая лекция носит обзорный характер; в ней сначала формулируется гипотеза о знакочередующихся матрицах, затем
приводятся (без доказательства) результаты Макмагона, Макдональда и Эндрюса о числе плоских разбиений с различными симметриями и формулируется основной результат, принадлежащий Зельбергеру: число вполне симметричных самодополнительных плоских разбиений (TSSCPP) равняется числу знакочередующихся матриц вдвое
меньшего порядка.
Благодарности. В первую очередь я хочу поблагодарить Г. А. Мерзона и В. А. Клепцына за неоценимую помощь и поддержку на всем
протяжении моей работы над этой брошюрой. Без их искреннего
интереса и доброжелательности, а также без наших многочасовых
обсуждений она, скорее всего, никогда не была бы написана. Я также признателен всем, кто прочел первоначальный вариант текста
и высказал свои замечания. Особенно ценную обратную связь я получил от П. Н. Пилявского, В. Е. Горина и А. А. Архиповой. Наконец,
я благодарен фонду «Династия» и фонду Дж. Саймонса за частичную
финансовую поддержку.
Я буду рад получить отзывы, замечания и комментарии от читателей. Направлять их можно по адресу [email protected]
Видеоматериалы прочитанного в Дубне курса доступны в видеотеке сайта MathNet, http://www.mathnet.ru.
Лекция 
Разбиения
§ .. Разбиения и диаграммы Юнга
Разбиением натурального числа будем называть его представление в виде суммы натуральных слагаемых. При этом порядок слагаемых неважен: так, например, 2 + 3 и 3 + 2 — это одно и то же
разбиение числа . Поэтому эти слагаемые можно считать нестрого
убывающими. Вот формальное определение.
Определение .. Разбиением натурального числа n называется
набор натуральных чисел λ = (λ1 , …, λk ), для которого λ1 ¾ λ2 ¾ …
… ¾ λk > 0 и λ1 + … + λk = n.
Иногда удобно считать, что разбиение — это невозрастающая
последовательность целых неотрицательных чисел (λ1 , …, λk , …),
в которой все λi начиная с некоторого номера равны нулю. Другими
словами, к конечному набору λi дописывается бесконечный «хвост»
нулей.
Разбиение можно представлять графически при помощи диаграмм Юнга. Диаграммой Юнга разбиения (λ1 , …, λk ) называется
подмножество четвертого  квадранта плоскости, состоящее из единичных квадратиков. Квадратики размещаются в последовательных строках, выровненных по левому краю, причем количество
квадратиков в i-й строке равно λi (таким образом, длина каждой следующей строки не превышает длины предыдущей).
Пример .. На рисунке изображена диаграмма Юнга, соответствующая разбиению
(7, 5, 5, 5, 2, 1) числа .

Это так называемый англосаксонский способ изображения диаграмм Юнга; альтернативой является французский способ, при котором диаграмма изображается
в первом квадранте плоскости. Стоит также упомянуть и русский способ, при котором
диаграмма поворачивается еще на 45 градусов, оказываясь в четверти плоскости,
ограниченной графиком функции y = |x|. При этом «внешняя граница» диаграммы
Юнга становится графиком кусочно линейной функции y = f (x). Такое представление оказывается удобным, в частности, во многих асимптотических задачах, т. е.
задачах, связанных с предельными формами диаграмм Юнга (подробнее об этом см.,
например, []).
§ .. Напоминание о производящих функциях

Отразим диаграмму Юнга λ относительно диагонали (т. е. прямой x + y = 0). Мы получим новую диаграмму Юнга, которую условимся обозначать через λ′ = (λ′1 , …, λ′m ) и называть сопряженной
к λ (иногда ее еще называют транспонированной). Ясно, что λ′i
равняется числу компонент исходного разбиения λ, больших или
равных i.
Пример .. Диаграмма (6, 5, 4, 4, 4, 1, 1) является сопряженной к диаграмме из предыдущего
примера.
Будем обозначать число разбиений числа n через p(n). Также условимся считать, что p(0) = 1.
Нетрудно найти p(n) для маленьких значений
n (скажем, при n ¶ 5). Они приведены в следующей таблице.
n






p(n)






Упражнение .. Проверьте это и для каждого n ¶ 5 нарисуйте
все диаграммы Юнга, соответствующие разбиениям числа n.
Возникает естественный вопрос: существует ли какая-нибудь
формула, с помощью которой можно найти p(n) для данного n?
Оказывается, простой замкнутой формулы для числа разбиений
(как, например, для биномиальных коэффициентов) найти не удается. Однако кое-что про эту последовательность сказать все же
получается: а именно, можно выписать ее производящую функцию.
Этим мы сейчас и займемся.
§ .. Напоминание о производящих функциях
В начале этого параграфа мы вкратце напомним некоторые сведения о производящих функциях и формальных степенных рядах
и разберем несколько простых примеров их использования. Более
подробный рассказ об этом читатель может найти во многих учебниках по комбинаторике — например, в книгах [] и [].
Пусть a0 , a1 , …, an , … — произвольная числовая последовательность. Рассмотрим формальный степенной ряд от переменной q:
a0 + a1 q + a2 q 2 + … + a n q n + …
(∗)

Лекция . Разбиения
Он называется производящей функцией для исходной последовательности.
Замечание .. Мы будем работать с производящими функциями именно как с формальными степенными рядами — выражениями вида (∗), которые можно представлять себе как «многочлены
бесконечной степени». Такие выражения можно, например, складывать и перемножать друг с другом. Отметим, что эти операции определены корректно: разумеется, для того чтобы сложить или перемножить два ряда, нужно произвести бесконечное число операций,
однако же число операций, необходимых для нахождения каждого
коэффициента в сумме или произведении, конечно. При этом нас
не будут интересовать вопросы сходимости этих рядов при тех или
иных числовых значениях q.
Упражнение .. Пусть A(q) = a0 + a1 q + a2 q 2 + … — формальный степенной ряд, причем a0 6= 0. Докажите, что существует ряд
B(q), обратный к A(q), — т. е. такой ряд, что A(q) · B(q) = 1. Что
происходит при a0 = 0?
Иногда производящую функцию, выраженную формальным степенным рядом, получается записать в каком-либо ином виде (скажем,
как рациональную функцию от q), что зачастую позволяет получить
какие-то новые сведения о последовательности (a0 , …, an , …).
Пример €..Š Пусть n — фиксированное целое неотрицательное
n
число, ak =
. В частности, ak = 0 при всех k > n. Тогда произвоk
дящая функция этой последовательности будет многочленом
n
n
n 2
n n
+
q+
q +…+
q = (1 + q)n .
0
1
2
n
Это формула бинома Ньютона.
Пример .. Рассмотрим постоянную последовательность: an = 1
при всех n ¾ 0. Тогда ее производящая функция есть геометрическая
прогрессия:
1
1 + q + q2 + … + q n + … = 1 − q .
Это равенство следует интерпретировать таким образом: ряд 1 − q
является обратным (в смысле упражнения .) к ряду 1 + q + q 2 + …:
если их перемножить, получится единица.
Упражнение .. Докажите, что производящую функцию последовательности an = n + 1 можно представить в виде
1 + 2q + 3q 2 + … + (n + 1)q n + … =
1
(1 − q)2
§ .. Напоминание о производящих функциях

(попробуйте придумать несколько доказательств этого равенства).
Следующий пример показывает, как при помощи производящих
функций найти явную формулу для последовательностей, заданных при помощи линейных рекуррентных соотношений. Простейшей такой последовательностью является знаменитая последовательность Фибоначчи.
Пример . (числа Фибоначчи). Пусть последовательность an
задана рекуррентным соотношением an+2 = an+1 + an , причем a0 =
= a1 = 1. Производящая функция для нее — это ряд
F(q) = 1 + q + 2q 2 + 3q 3 + 5q 4 + 8q 5 + 13q 6 …
Из рекуррентного соотношения для an нетрудно вывести функциональное уравнение для производящей функции, которое будет иметь
вид
F(q) = 1 + qF(q) + q 2 F(q)
(подумайте, откуда в правой части взялась единица). Тогда F(q)
оказывается представленной в виде рациональной функции:
F(q) =
1
.
1 − q − q2
Упражнение .. Разложите полученную дробь в сумму двух
a
дробей вида
. Выведите отсюда формулу Бине, представляющую
q−b
последовательность Фибоначчи в виде суммы двух геометрических
прогрессий. Выясните, чему равен предел отношения двух соседних
чисел Фибоначчи (это число называется золотым сечением).
Вернемся к разбиениям. Сначала ответим на следующий вопрос:
чему равно количество разбиений числа n на слагаемые, не превосходящие заданной величины m? Обозначим его через pm (n), а соответствующую производящую функцию через Pm (q).
1
Ясно, что P1 (q) = 1 + q + q 2 + … = 1 − q : каждое число единственным образом разбивается в сумму единиц.
Выясним, чему равно p2 (n), т. е. число разбиений n в сумму единиц и двоек. Заметим для начала, что количество способов разбить
число n в сумму слагаемых, каждое из которых равно двум, — это
либо , если n четно, либо , если n нечетно. Соответствующая производящая функция равна
1 + q2 + q4 + … =
1
.
1 − q2

Лекция . Разбиения
Теперь легко видеть, что производящая функция P2 (q) есть произведение P1 (q) и
1
. Действительно, рассмотрим произведение
1 − q2
(1 + q + q 2 + …)(1 + q 2 + q 4 + …).
Раскроем в нем скобки, но не будем приводить подобные члены.
Каждое слагаемое после раскрытия скобок будет иметь вид q r · q 2s ,
где сомножитель q r берется из первого сомножителя, а q 2s из второго. Каждому такому слагаемому можно сопоставить разбиение числа r + 2s в сумму r единиц и s двоек. Получается, что после приведения подобных коэффициент при q n действительно будет равняться
p2 (n).
Рассуждая аналогично, получаем следующий результат.
Предложение .. Производящая функция Pm (q) для количества разбиений числа n в сумму слагаемых, не превосходящих m,
равняется
Pm (q) =
P
pm (n)q n =
m
Q
1
(1 − q k )−1 .
2
m =
(1 − q)(1 − q )…(1 − q )
k=1
Иными словами, это производящая функция для диаграмм Юнга, длина строки которых не превосходит m. Чтобы получить производящую функцию для числа всех диаграмм Юнга, следует перейти
к пределу при m → ∞. Мы получим знаменитую формулу Эйлера для
числа разбиений.
Теорема . (Л. Эйлер). Производящая функция P(q) для количества разбиений числа n задается следующим бесконечным произведением:
P(q) =
P
p(n)q n =
∞
Q
1
=
(1 − q k )−1 .
2
3
(1 − q)(1 − q )(1 − q )…
k=1
Замечание .. Знак бесконечного произведения может напугать читателя, который ранее не имел дела с этим объектом. Однако
бояться его следует не больше, чем бесконечных рядов. Действительно, на первый взгляд кажется, что для того, чтобы представить
бесконечное произведение как ряд, нужно «перемножить бесконечное число скобок». Однако чтобы вычислить очередной (скажем,
k-й) член этого ряда, нужно взять только конечное число (в данном
случае k) первых сомножителей — остальные не окажут на коэффициент при q k никакого влияния.
§ .. Разбиения на нечетные и различные слагаемые

§ .. Разбиения на нечетные и различные
слагаемые
Вот еще одна задача, которую можно решить при помощи производящих функций. Рассмотрим следующий вопрос: сколькими способами можно разложить число в сумму нечетных слагаемых? Обозначим число таких способов через pO (n) (от слова «odd» — «нечетный»).
Например, pO (7) = 5, так как для числа  есть  таких разбиений:
7 = 5 + 1 + 1 = 3 + 3 + 1 = 3 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1.
Далее, выясним, сколькими способами можно разбить число
в сумму попарно различных слагаемых. Обозначим его через pD (n)
(от слова «distinct» — «различный»).
Найдем все такие разбиения числа :
7 = 6 + 1 = 5 + 2 = 4 + 3 = 4 + 2 + 1.
Их снова оказывается пять! Оказывается, это не совпадение.
Предложение .. При любом n выполняется равенство pD (n) =
= pO (n).
Доказательство.
Докажем,
P
P что равны производящие функции
PO (q) = pO (n)q n и PD (q) = pD (n)q n .
Рассуждая точно так же, как и с произвольными
разбиениями,
P
получаем, что производящая функция PO (q) = pO (n)q n равняется
PO (q) =
1
1
1
·
…
·
1 − q 1 − q3 1 − q5
С разбиениями на различные слагаемые дело обстоит еще проще:
PD (q) = (1 + q)(1 + q 2)(1 + q 3 )…
(убедитесь в этом самостоятельно).
Дальнейшее сводится к чисто алгебраическим преобразованиям. Умножим и поделим ряд PO (q) на бесконечное произведение
(1 − q 2 )(1 − q 4 )…:
1
1
1
1
1 − q2
1
1 − q4
·
… = 1−q ·
·
…=
PO (q) = 1 − q ·
1 − q3 1 − q5
1 − q2 1 − q3 1 − q4
=
(1 − q2 )(1 − q4 )(1 − q6 )…
= (1 + q)(1 + q 2)(1 + q 3 )… = PD (q).
(1 − q)(1 − q2 )(1 − q3 )…

Лекция . Разбиения
Можно задать другой вопрос: пусть мы уже знаем, что разбиений
на нечетные слагаемые столько же, сколько на различные. Можно ли построить какое-нибудь «естественное» взаимно однозначное
отображение (биекцию) между наборами таких разбиений? Иначе
говоря, как сопоставить взаимно однозначным образом каждому
разбиению числа n на нечетные слагаемые его же разбиение на
различные слагаемые?
Можно построить несколько таких биекций. Опишем одну из
них на примере.
Пусть дано какое-то разбиение числа на нечетные слагаемые,
например, такое:
23 = 7 + 5 + 5 + 3 + 1 + 1 + 1.
Рассмотрим «центрированную диаграмму Юнга» — нарисуем симметричную относительно вертикальной оси диаграмму (см. рис.
слева), в первой строке которой будут  точек, во второй и третьей — по  и так далее.
Рис. .. Разбиение диаграммы Юнга на крюки
Теперь разобьем эту диаграмму на крюки, как показано на
рис. . справа. Тем самым по разбиению числа 23 на нечетные
слагаемые мы построили разбиение того же числа на различные
слагаемые:
23 = 10 + 6 + 4 + 2 + 1.
§ .. Пятиугольные числа
Рассмотрим бесконечное произведение, обратное к P(q). Это
произведение бесконечного числа двучленов:
∞
Q
(1 − q k ).
P(q)−1 =
k=1

§ .. Пятиугольные числа
Упражнение .. Вычислите первые  членов (до q 7 включительно) этого бесконечного произведения.
Эйлер вычислил первые несколько десятков членов этого произведения, и у него получилось следующее:
P(q)−1 = 1 − q − q 2 + q 5 + q 7 − q 12 − q 15 + q 22 + q 26 − q 35 − q 40 + …
Здесь можно сделать сразу несколько интересных наблюдений. Вопервых, видно, что все коэффициенты этого ряда равны либо , либо
±1, причем по мере увеличения степени ненулевые члены встречаются все реже и реже. Во-вторых, все члены, кроме свободного, идут
парами: два отрицательных, два положительных, потом снова два
отрицательных и т. д. Разность между степенями в паре равняется
номеру пары: сначала это единица (q и q 2 ), потом два (q 5 и q 7 ),
потом три (q 12 и q 15 ) и т. д.
Наконец, последовательность степеней 1, 5, 12, 22, 35, … тоже
была хорошо известна Эйлеру — это так называемые пятиугольные
числа, которые равняются числу точек в пятиугольнике, сторона
которого равна 1, 2, 3, … точкам соответственно (см. рис. .).
Рис. .. Пятиугольные числа
m(3m−1)
Нетрудно видеть, что m-е пятиугольное число равняется
.
2
Оказывается, имеет место следующий результат. Его доказательство будет получено в следующей лекции.
Теорема .
P (пентагональная теорема Эйлера). Ряд, обратный
к ряду P(q) = p(n)q n , имеет вид
P(q)−1 = 1 +
∞
P
€ m(3m−1)
m(3m+1) Š
.
(−1)m q 2 + q 2
m=1
Мы выведем пентагональную теорему Эйлера из формулы Якоби для тройного произведения. Другое доказательство этой замеча-

Лекция . Разбиения
тельной теоремы читатель может найти, например, в статье [] или
книге [].
В качестве следствия пентагональной теоремы Эйлера покажем,
как с ее помощью можно выписать рекуррентное соотношение для
числа разбиений.
Перемножив ряды P(q) и P(q)−1 , мы получим единицу. Поэтому
‹

∞
€ m(3m−1)
P
P
m(3m+1) Š
= 1.
(−1)m q 2 + q 2
( p(k)q k ) 1 +
m=1
С одной стороны, коэффициент при q n для n > 0 в произведении
P(q)P(q)−1 равен нулю.
P
P
С другой стороны, если an q n и bm q m — два степенных ряда.
то коэффициент при q k в их произведении равняется
P
ak b0 + ak−1 b1 + … + a0 bk = ak−i bi .
Выпишем, чему равен коэффициент при q n в левой части, и тем
самым найдем соотношение для чисел разбиений p(n):
∞
P
p(n) +
€ €
€
m(3m − 1) Š
m(3m + 1) ŠŠ
(−1)m p n −
+
p
n
−
=0
2
2
m=1
(здесь мы считаем, что p(k) = 0 при k < 0). Перенесем все, кроме
первого слагаемого, в правую часть, и получим, что
p(n) =
∞
P
€ €
€
m(3m − 1) Š
m(3m + 1) ŠŠ
(−1)m+1 p n −
+ p n−
.
m=1
2
2
Это рекуррентное соотношение, глубина которого постоянно увеличивается. Выпишем его при 6 ¶ n ¶ 12 и с его помощью найдем
соответствующие значения p(n) (число разбиений при n ¶ 5 мы уже
знаем — см. упражнение .).
p(6) = p(5)+ p(4)− p(1) = 7+5−1 = 11;
p(7) = p(6)+ p(5)− p(2)− p(0) = 11+7−2−1 = 15;
p(8) = p(7)+ p(6)− p(3)− p(1) = 15+11−3−1 = 22;
p(9) = p(8)+ p(7)− p(4)− p(2) = 22+15−5−2 = 30;
p(10) = p(9)+ p(8)− p(5)− p(3) = 30+22−7−3 = 42;
p(11) = p(10)+ p(9)− p(6)− p(4) = 42+30−11−5 = 56;
p(12) = p(11)+ p(10)− p(7)− p(5)+ p(0) = 56+42−15−7+1 = 77.
§ .. Пятиугольные числа

Задачи к лекции 
Задача .. a) Постройте биекцию между множеством самосопряженных (т. е. совпадающих со своим сопряженным) разбиений
числа n и множеством его разбиений в сумму различных нечетных
слагаемых.
б) Вычислите производящую функцию для числа самосопряженных разбиений.
Задача . (биекция Сильвестра). Докажите, что построенное
в конце § . соответствие действительно является биекцией между
разбиениями числа n на нечетные и различные слагаемые.
Задача .. Пусть an — число диаграмм Юнга с полупериметром n. Докажите, что производящая функция для этой последовательности равна 1 +
q2
.
1 − 2q
Задача .. Обозначим через σn сумму делителей числа n, включая  и n; так, например, σ6 = 1 + 2 + 3 + 6 = 12. Пусть Σ(q) — производящая функция для последовательности σn :
Σ(q) = q + 3q 2 + 4q 3 + 7q 4 + 6q 5 + 12q 6 + 8q 7 + …
а) Докажите, что
Σ(q)P(q) = qP ′ (q),
где P(q) — производящая функция для числа разбиений.
б) Выведите отсюда рекуррентное соотношение для числа σn .
Указание. Рассмотрите логарифмическую производную ряда P(q):
P ′ (q)
(ln P(q))′ = P(q) .
Лекция 
q-биномиальные коэффициенты
§ .. Диаграммы Юнга и биномиальные
коэффициенты
Вот еще один вопрос о подсчете диаграмм Юнга: сколько существует диаграмм Юнга из не более чем m строк, если длина каждой
из них не превосходит n? Иначе говоря, сколько диаграмм Юнга
можно вписать в прямоугольник размера m × n?
Например, для квадрата 2 × 2 таких диаграмм шесть. Они приведены на рисунке.
∅
Этот вопрос гораздо проще, чем подсчет производящей функции
для числа всех диаграмм Юнга. Легко видеть, что каждая диаграмма
Юнга в прямоугольнике ограничивается снизу ломаной, соединяющей левый нижний угол квадрата с правым верхним. Такая ломаная
состоит из m + n звеньев, из которых ровно m идут вверх, а n вправо.
Итого количество таких ломаных равно количеству способов выбрать m вертикальных звеньев из m + n (или, что то же самое, числу
способов выбрать n горизонтальных звеньев), т. е. биномиальному
€m+nŠ €m+nŠ
коэффициенту
=
.
m
n
§ .. Определение q-биномиальных коэффициентов
Назовем весом |λ| диаграммы Юнга λ количество входящих
в нее клеток. Будем решать ту же задачу — подсчета диаграмм
Юнга внутри данного прямоугольника, — но уже с учетом весов.
Составим
производящую функцию, которую будем обозначать че
рез
m+n
m
:
q
m+n
m
=
q
P
λ⊂m×n
q |λ| .

§ .. Определение q-биномиальных коэффициентов
Это многочлен с положительными коэффициентами, причем коэффициент при q k равняется числу диаграмм Юнга веса k, вписанных
в прямоугольник размера m × n. Иногда, когда ясно,
о каком
q идет
речь, мы будем опускать индекс q и писать просто
m+n
.
m
Этот многочлен будем называть q-биномиальным коэффициентом. Действительно, далее мы увидим, что эти многочлены ведут себя очень похоже на обычные числа сочетаний: для многих
утверждений о биномиальных коэффициентах удается получить
их «q-аналоги», т. е. аналогичные утверждения о q-биномиальных
коэффициентах.
Пример .. Пусть m = 1. Тогда
1 − qn+1
n+1
= 1 + q + q2 + … + q n =
.
n
1−q
q
4
Пример .. Пусть m = n = 2. Тогда 2 = 1 + q + 2q 2 + q 3 + q 4
q
(это легко увидеть, посмотрев на предыдущий рисунок, — на нем
изображено по одной диаграмме весов , ,  и  и две диаграммы
веса ). Этот многочлен можно разложить на множители, причем
каждый множитель будет геометрической прогрессией:
1 + q + 2q 2 + q 3 + q 4 = (1 + q + q 2 )(1 + q 2 ).
Сформулируем несколько свойств q-биномиальных коэффициентов.
m+n
m+n
в единице равно
.
Предложение .. Значение
m
q
m
Это очевидно: если подставить в производящую функцию q = 1,
каждая диаграмма Юнга вне зависимости от ее веса будет считаться
с весом , т. е. значение многочлена будет давать общее количество
диаграмм.
Предложение ..
m+n
m+n
=
.
m
n
Это следует из инвариантности производящей функции при отражении прямоугольника относительно главной диагонали (т. е. замены ширине на высоту и наоборот).
Предложение . (рекуррентное соотношение для q-биномиальных коэффициентов).
m+n
m+n−1
m+n−1
=
+ qm
.
m
m−1
m

Лекция . q-биномиальные коэффициенты
Доказательство. Рассмотрим произвольную диаграмму Юнга λ.
Она ограничена некоторой ломаной; посмотрим на ее первое звено.
Возможны два варианта: либо оно вертикальное, и тогда остаток
ломаной ограничивает диаграмму Юнга, равную λ, в прямоугольнике размера (m − 1) × n; либо оно горизонтальное, и тогда остаток
ломаной ограничивает некоторую диаграмму Юнга в прямоугольнике размером m × (n − 1), а λ получается из нее добавлением слева
столбца высоты m.
Это соотношение является обобщением соотношения
m+n
m
=
m+n−1
m+n−1
+
m−1
m
для биномиальных коэффициентов.
Упражнение .. Докажите другой q-аналог того же соотношения:
m+n
m+n−1
n m+n−1
=
+q
.
m
m−1
m
Зная данное рекуррентное соотношение, мы можем восстановить все q-биномиальные коэффициенты. Их тоже можно записать
в виде треугольника Паскаля, очередная строчка в котором выражается через предыдущие:
1
1
1
1+q
1
1
1
1 + q + q2
1 + q + q2
1
1 + q + q2 + q3
1 + q + 2q2 + q3 + q4
1 + q + q2 + q3
1
1
..............................................................................
Оказывается, для q-биномиальных коэффициентов также име(m + n)!
m+n
. Но для того чтобы ее
=
ется обобщение формулы
n
m! · n!
сформулировать, нам предстоит ввести понятие q-факториала.
Определение .. Пусть n ¾ 0. Назовем q-аналогом целого числа
n многочлен
1 − qn
[n] = 1 + q + … + q n−1 = 1 − q .
Тогда q-факториал числа n определяется по правилу
[0]! = 1,
[n]! = [n − 1]! · [n].
Отметим, что значения многочленов [n] и [n]! в единице равны
n и n! соответственно.
§ .. Производящая функция Эйлера

Упражнение .. Докажите, что
m+n
n
=
[m + n]!
.
[m]! · [n]!
Указание. Воспользуйтесь рекуррентным соотношением и равенством [m + n] = [m] + q m[n].
Утверждение упражнения . можно переписать в следующем
1 − qk
виде, заменив каждое из чисел [k] на 1 − q .
Предложение ..
m+n
m
=
(1 − qm+n )(1 − qm+n−1 )…(1 − qn+1 )
.
(1 − qm )(1 − qm−1 )…(1 − q)
Рассмотрев несколько примеров q-биномиальных коэффициентов, можно заметить, что эти многочлены являются возвратными:
набор их коэффициентов
есть
палиндром. Иначе говоря, коэффициент в многочлене
m+n
m
при q k равняется коэффициенту при
q mn−k . Это следует напрямую из определения q-биномиальных коэффициентов как производящих функций для числа диаграмм Юнга:
каждой диаграмме Юнга из k клеток можно сопоставить ее дополнение до прямоугольника m × n, которое будет состоять из mn − k
клеток.
Отметим еще одно интересное свойство q-биномиальных коэффициентов: они являются унимодальными (или веретенообразными) многочленами. Это значит, что последовательность их коэффициентов (a0 , …, amn ) имеет единственный локальный максимум:
первая половина этой последовательности является нестрого возmn
растающей, т. е. ai ¶ a j при 0 ¶ i < j ¶ 2 . В силу симметрии вторая
половина последовательности коэффициентов является нестрого
убывающей. Комбинаторное доказательство этого факта оказывается на удивление непростым. Оно было получено Кэтлин О’Харой
в работе []; см. также обзорную работу Д. Зельбергера [] и недавний препринт И. Пака и Г. Пановой [].
§ .. Производящая функция Эйлера как следствие
формулы для q-биномиальных коэффициентов
Как мы только что выяснили, предыдущая формула задает производящую функцию для диаграмм Юнга ширины не более n и высоты

Лекция . q-биномиальные коэффициенты
не более m. Перейдем к пределу при n → ∞; получим, что
m+n
m
1
(1 − qm )(1 − qm−1 )…(1 − q)
m+n
(отметим, что знаменатель в выражении для
, приведенном
m
lim
n→∞
=
в предложении ., от n не зависит!). Мы получили еще одно доказательство предложения . о производящей функции для числа
диаграмм Юнга, длины строк которых не превосходят m.
Кроме того, в этом же предложении можно было одновременно переходить
к пределу при n → ∞ и m → ∞ (скажем, рассмотрев
limn→∞
2n
) — в итоге получится эйлеровская производящая функn
ция для числа всех разбиений (следствие .).
§ .. q-бином Ньютона
P n k
x также имеются q-аналоги.
У бинома Ньютона (1 + x)n =
k
Один из них мы сформулируем и докажем сейчас; другой приведен
в упражнениях в конце этой лекции.
Теорема . (q-бином Ньютона).
(1 + xq)(1 + xq 2)…(1 + xq n ) =
n
P
n
k=0
k
q
k(k+1)
2
xk.
Как и следует ожидать, подстановка q = 1 превращает данное
равенство в обычный бином Ньютона.
Доказательство. Раскроем скобки в левой части и запишем результат как сумму степеней x, коэффициент при каждой из которых
является многочленом от q:
(1 + xq)(1 + xq 2)…(1 + xq n ) =
n
P
ak (q)x k .
k=0
Здесь ak (q) — это производящая функция для числа разбиений на
ровно k различных слагаемых, каждое из которых не превосходит n.
Упорядочим эти слагаемые по убыванию (они будут строго убывать,
так как они различны) и вычтем из первого k, из второго k − 1, …,
а из последнего единицу. Это будет соответствовать делению проk(k+1)
изводящей функции на q 1+2+…+k = q 2 . Мы получим производящую функцию для разбиений числа на не более чем k слагаемых

§ .. Тождество Якоби для тройного произведения
(уже, возможно, одинаковых), каждое из которых не превосходит
n
n − k. А это и есть q-биномиальный коэффициент k . Поэтому
ak (q) = q
k(k+1)
2
n
. Теорема доказана.
k
§ .. Тождество Якоби для тройного произведения
В этом параграфе мы при помощи алгебраических манипуляций
с q-биномом Ньютона получим равенство, называемое тождеством
Якоби для тройного произведения. Из него, в частности, будет следовать пентагональная теорема Эйлера.
Начнем с того, что рассмотрим следующее произведение:
m
Q
(1 + xq i ) =
i=−(m−1)
= (1 + xq −(m−1))(1 + xq −(m−2))…(1 + x)(1 + xq)…(1 + xq m ),
где x — некоторая переменная. Представим это произведение в виде суммы. Это нетрудно сделать с помощью формулы для q-бинома.
Действительно, сделаем замену переменной: y = xq −m . Тогда это
произведение переписывается в виде
m
Q
(1 + xq i ) =
2m
Q
(1 + xq i−m) =
(1 + yq i ).
i=1
i=1
i=−(m−1)
2m
Q
А это не что иное, как q-бином. Поэтому
2m
Q
i
(1 + yq ) =
i=1
2m
P
2m
k=0
k
q
k(k+1)
2
y k.
Вернемся к исходным обозначениям: заменив y на q −m x, получим
равенство
(1 + xq 1−m )(1 + xq 2−m )…(1 + x)(1 + xq)…(1 + xq m ) =
=
2m
P
2m
k=0
k
q
k(k+1)
−mk
2
xk.
Это равенство многочленов Лорана от q (т. е. многочленов, в которые q может входить не только в положительных, но и в отрицательных степенях). Рассмотрим те сомножители в его левой части,

Лекция . q-биномиальные коэффициенты
в которые q входит в нулевой или отрицательной степени (таких
будет ровно m). Вынесем из каждого из них q в такой отрицательной степени, чтобы в скобках остался многочлен от положительных
степеней q, степень которого была бы минимальной. Иначе говоря,
для каждого из сомножителей вида 1 + xq − j , где j ¾ 0, запишем,
что 1 + xq − j = q − j (x + q j ) = xq − j (1 + x −1 q j ) (из каждой такой скобки
мы еще вынесли x, чтобы свободный член выражения в скобках
равнялся ). Тогда наше равенство перепишется в виде
x m q −(0+1+…+(m−1)) (1 + x −1 q m−1 )(1 + x −1 q m−2 )…(1 + x −1)×
2m
P
2m
× (1 + xq)(1 + xq 2)…(1 + xq m ) =
k=0
Далее, поделив обе части равенства на x m q
− m(m−1)
2
k
q
k(k+1)
−mk
2
x k.
, получим
(1 + x −1 q m−1 )(1 + x −1 q m−2 )…(1 + x −1)(1 + xq)(1 + xq 2)…(1 + xq m ) =
=
2m
P
2m
k
k=0
q
k(k+1)
+ m(m−1)
−mk
2
2
x k−m.
Осталось совсем немного: придадим правой части более симметричный вид, сделав замену переменной j = k − m. При этом j будет пробегать значения от −m до m, а в показателе степеней у q
исчезнет «довесок»
выглядеть так:
m
Q
m(m − 1)
− mk. В итоге наша формула станет
2
(1 + xq k )(1 + x −1 q k−1 ) =
k=1
m
P
j=−m
j( j+1)
2m
q 2 x j.
m+ j
Это конечная форма тождества Якоби для тройного произведения.
Теперь перейдем к пределу при m → ∞. Биномиальный коэффициент в правой частиQбудет стремиться к функции Эйлера для
∞
числа разбиений P(q) = k=1 (1 − q k )−1 (и, в частности, он не будет
зависеть от j, и его можно будет вынести за знак суммирования).
Поделив обе части равенства на P(q), получим следующее равенство.
Теорема . (тождество Якоби для тройного произведения).
∞
Q
(1 + xq k )(1 + x −1 q k−1 )(1 − q k ) =
k=1
+∞
P
j=−∞
q
j( j+1)
2
x j.

§ .. Тождество Якоби для тройного произведения
Из нее несложно вывести пентагональную теорему Эйлера.
Доказательство пентагональной теоремы Эйлера. Сделаем
замену переменной в тождестве Якоби: подставим q 3 вместо q.
Получим
∞
Q
+∞
P
(1 + xq 3k )(1 + x −1 q 3k−3 )(1 − q 3k ) =
q
3 j 2 +3 j
2
x j.
j=−∞
k=1
Теперь положим x = −q −1 . Тогда
∞
Q
(1 − q 3k−1)(1 − q 3k−2)(1 − q 3k ) =
+∞
P
(−1) j q
3 j2+ j
2
.
j=−∞
k=1
А это и есть пентагональная теорема Эйлера:
∞
∞
€ j(3 j−1)
P
Q
j(3 j+1) Š
(1 − q k ) = 1 + (−1) j q 2 + q 2
.
j=1
k=1
Задачи к лекции 
Задача . (для знакомых с основами линейной алгебры). Пусть
q = p m — степень простого числа. Докажите, что число k-мерных
векторных подпространств n-мерного
векторного пространства над
полем из q элементов равно
n
.
k
Подробнее о связи q-биномиальных коэффициентов с линейной
алгеброй можно прочитать в статье [].
Задача . (еще один q-бином Ньютона). Пусть переменные x
и y не коммутируют , но вместо этого удовлетворяют соотношению
yx = qxy. Докажите, что
n P
n k n−k
(x + y)n =
x y .
k
k=0
В следующих задачах приводится еще одно доказательство тождества Якоби для тройного произведения, не использующее q-биномиальных коэффициентов.
Рассмотрим бесконечное произведение
∞
Q
f (x) =
(1 + xq k )(1 + x −1 q k−1 ).
k=1

Такое соотношение, конечно же, невозможно, если x и y являются числами.

‹
1 0

‹
0 1
Однако оно, например, имеет место для матриц x = 0 q и y = 0 0 .

Лекция . q-биномиальные коэффициенты
Его можно рассматривать как ряд Лорана по x:
f (x) =
∞
P
n=−∞
an (q)x n ,
коэффициенты которого an (q) суть формальные степенные ряды
от q.
Задача .. Проверьте, что f (xq) = x −1q −1 f (x).
Задача .. Докажите, что при n ∈ Z имеют место равенства:
а) an (q)q n+1 = aP
n+1 (q);
б) f (x) = a0 (q)
q n(n+1)/2 x n .
n∈Z
Задача .. Пусть bm есть число способов представить число m в
виде суммы нескольких различных элементов множества {1, 2, 3, …}
и такого же числа различных
элементов множества {0, 1, 2, …}. ПокаP
жите, что a0 (q) =
bm q m .
m¾0
Задача .. Построив биекцию между представлениями из предыдущей задачи и диаграммами Юнга, докажите, что bm равно p(m), т. е.
числу разбиений числа m.
Указание. Проведите в диаграмме Юнга диагональ.
Задача .. Выведите из предыдущих задач тождество Якоби
для тройного произведения.
Лекция 
Плоские разбиения и формула Макмагона
§ .. Плоские разбиения
В предыдущих двух лекциях мы рассматривали «одномерные»
разбиения и отвечающие им диаграммы Юнга. В этой лекции
мы рассмотрим обобщение этого понятия на следующую размерность — а именно, займемся изучением плоских разбиений, компоненты которых занумерованы не одним индексом, а двумя, и которым будут соответствовать трехмерные диаграммы Юнга.
Определение .. Пусть n — целое неотрицательное число. Плоское разбиение — это набор целых
P неотрицательных чисел λi, j , где
i, j ¾ 1, в сумме дающих n (т. е. λi, j = n) и удовлетворяющих нераi, j
венствам λi, j ¾ λi+1, j и λi, j ¾ λi, j+1 при всех i, j.
Иначе говоря, плоское разбиение — это набор чисел, записанных в клетках бесконечной вправо и вниз таблицы, причем эти числа нестрого убывают по строкам и по столбцам, и лишь конечное их
число отлично от нуля.
Каждому плоскому разбиению можно сопоставить трехмерную
диаграмму Юнга. Для этого заменим каждое число на плоскости на
столбец из кубиков, высота которого равна этому числу. Полученная трехмерная конструкция из кубиков и будет трехмерной диаграммой Юнга.
Пример .. На рис. . изображено одно из плоских разбиений
числа  и отвечающая ему трехмерная диаграмма Юнга.
3
2
2
1
1
1
2
Рис. .. Плоское разбиение и его трехмерная диаграмма Юнга
Плоское разбиение можно рассматривать как набор нескольких
вложенных друг в друга диаграмм Юнга µ1 ⊆ µ2 ⊆ … ⊆ µk . Пусть диаграмма µm состоит из всех таких клеток (i, j), что λ11 − λi, j ¶ m − 1.

Лекция . Плоские разбиения и формула Макмагона
Получается, что µm будет составлять m-й «этаж» соответствующей
трехмерной диаграммы Юнга (если считать этажи сверху вниз).
Пример .. Для плоского разбиения из предыдущего примера
получаем последовательность диаграмм
Наша ближайшая цель состоит в том, чтобы вычислить количество трехмерных диаграмм Юнга, лежащих внутри прямоугольного параллелепипеда B(a, b, c) (т. е. длина, ширина и высота которых не превосходят a, b и c соответственно), а также производящую функцию для числа таких диаграмм. Перейдя к пределу при
a, b, c → ∞, мы получим аналог производящей функции Эйлера для
числа всех трехмерных диаграмм Юнга (этот результат был получен
в начале XX в. майором британской армии в отставке Перси Александром Макмагоном).
§ .. Подсчет числа плоских диаграмм высоты 
Начнем с простого случая: посчитаем количество трехмерных
диаграмм Юнга в параллелепипеде размера B(a, b, 2). Это эквивалентно подсчету числа пар (µ1 , µ2 ) диаграмм Юнга, удовлетворяющих условию µ1 ⊂ µ2 ⊂ (a × b).
В прошлой лекции уже говорилось, что диаграмму Юнга в прямоугольнике a × b можно интерпретировать как путь на решетке,
идущий из точки A1 = (0, a) в точку B1 = (b, 0) (условимся, что ось
ординат на нашей решетке направлена вниз). Таким образом, пара
вложенных диаграмм — это пара путей из A1 в B1 , один из которых
проходит не выше другого.
Из этой пары путей можно изготовить два непересекающихся
пути: сдвинем нижний путь на вектор (1, 1). Мы получим новый
путь из точки A2 = (1, a + 1) в точку B2 = (b + 1, 1), который уже не
будет пересекаться с верхним путем (см. рис. .).
Итак, число трехмерных диаграмм Юнга высоты не более  равно числу пар непересекающихся путей, которое мы обозначим через
Pnc (A1 → B1 , A2 → B2 ) (символы «nc» означают «non-crossing», т. е.
«непересекающиеся»).

§ .. Подсчет числа плоских диаграмм высоты 
B1
B1
B2
A1
A1
A2
Рис. .. Раздвигание путей
Нетрудно найти число пар всевозможных путей, соединяющих
A1 c B1 , а A2 c B2 : оно равняется P(A1 → B1 ) · P(A2 → B2 ), т. е.
a+b
b
2
. Таким образом, наша задача эквивалентна задаче о на-
хождении числа пар пересекающихся путей из A1 в B1 и из A2 в B2 .
Итак, пусть µ1 и µ2 — два пересекающихся пути на решетке,
первый из которых соединяет A1 c B1 , а второй — A2 с B2 . Пусть
C — первая из точек пересечения этих путей. Построим новую пару
путей, ι(µ1 ) и ι(µ2 ), по следующему правилу: ι(µ1 ) будет совпадать
с µ1 на отрезке от A1 до C и с µ2 на отрезке от C до B2 . Таким
образом, он будет соединять A1 с B2 . Напротив, ι(µ2 ) будет соединять A2 и B1 ; он будет совпадать с µ2 от A2 до C и с µ1 от C до B1
(см. рис. .).
Легко увидеть, что всякая пара путей, соединяющих A1 с B2 ,
а A2 с B1 , пересекается; в частности, она получается как результат описанной выше операции, примененной к какой-то паре пересекающихся путей µ1 : A1 → B1 и µ2 : A2 → B2 . Поэтому число пар
пересекающихся путей из A1 в B1 и из A2 в B2 равно числу пар
всевозможных путей, соединяющих начальные и конечные точки
B1
B1
B2
A1
C
A2
B2
A1
C
A2
Рис. .. Отображение ι на пересекающихся путях

Лекция . Плоские разбиения и формула Макмагона
в «неправильном» порядке. А оно равняется
P(A1 → B2 ) · P(A2 → B1 ) =
a+b
a+b
·
.
b+1
b−1
Вычтя число пар пересекающихся путей из общего числа пар
путей, получаем следующее предложение.
Предложение ..
Pnc (A1 → B1 , A2 → B2 ) = P(A1 → B1 )P(A2 → B2 )−
P(A1 → B1 ) P(A1 → B2 )
.
− P(A1 → B2 )P(A2 → B1 ) = P(A2 → B1 ) P(A2 → B2 )
Следствие .. Число трехмерных диаграмм Юнга, вписанных
в параллелепипед B(a, b, 2), равно
a+b
b
2
−
a+b
b−1
a+b
.
b+1
Мы видим, что искомое число пар непересекающихся путей оказалось представлено в виде определителя 2 × 2. Оказывается, для
наборов из n непересекающихся путей дело обстоит аналогичным
образом.
§ .. Детерминантная формула
Линдстрёма—Гесселя—Вьенно
Теперь решим исходную задачу: найдем число трехмерных диаграмм Юнга в прямоугольном параллелепипеде B(a, b, c). Каждую
такую трехмерную диаграмму можно рассматривать как последовательность из c вложенных друг в друга обычных диаграмм Юнга.
Эти диаграммы, в свою очередь, соответствуют путям на решетке
из точки A = (0, a) в точку B = (b, 0). Каждый следующий из этих
путей лежит нестрого ниже предыдущего. Как и в предыдущем случае, сделаем их непересекающимися: для этого сдвинем k-й путь
на вектор (k − 1, k − 1). При этом k-й путь будет соединять точки
Ak = (k − 1, a + k − 1) и Bk = (b + k − 1, k − 1).
Пусть w ∈ Sn — произвольная перестановка. Будем говорить, что
набор из c путей (возможно, пересекающихся) с началами в точках
(A1 , …, Ac ) и концами в точках (B1 , …, Bc ) отвечает перестановке w, если путь, начинающийся в точке Ak , заканчивается в точке
Bw(k) . Ясно, что всякий набор непересекающихся путей может отвечать лишь тождественной перестановке.
Легко посчитать число всевозможных наборов путей, отвечающих перестановке w. Оно будет равно произведению биномиаль-

§ .. Детерминантная формула Линдстрёма—Гесселя—Вьенно
ных коэффициентов:
c
Q
P(Ak → Bw(k) ) =
k=1
=
c
Q
P((k−1, a+k−1) → (b+w(k)−1, w(k)−1)) =
k=1
c
Q
k=1
a+b
.
b+w(k)−k
Теперь обобщим прием, уже примененный для случая двух путей: рассмотрим на наборах пересекающихся путей, отвечающих
всевозможным перестановкам, инволюцию ι, определенную следующим образом. Рассмотрим в наборе из пересекающихся путей µ
путь µi с наименьшим номером i, пересекающийся с каким-то другим путем. Возьмем первую точку пересечения этого пути с другими путями. Из путей, пересекающих µi в этой точке, возьмем
путь с наименьшим номером; обозначим его через µ j . Заменим участок пути µi , следующий за точкой пересечения, на участок пути
µ j , и наоборот. Получим новый набор пересекающихся путей ι(µ).
Он уже отвечает другой перестановке; какая именно перестановка
получится, нам сейчас неважно, однако важно, что перестановки,
отвечающие µ и ι(µ), имеют различную четность. Кроме того, ясно,
что это отображение инволютивно: если применить его к набору
путей два раза, получится исходный набор путей.
Мы получили биекцию на множестве наборов пересекающихся путей. Она сопоставляет набору путей, отвечающих четной перестановке, набор путей, отвечающих нечетной перестановке, и наоборот.
Пример .. На рис. . показан набор путей, к которому применяется инволюция ι согласно указанному правилу: в точке (2, 2) —
первой точке пересечения первого пути с каким-либо еще путем
B1
B1
B2
B2
B3
B3
A1
A1
A2
A2
A3
A3
Рис. .. Инволюция на множестве путей

Лекция . Плоские разбиения и формула Макмагона
(в данном случае с третьим) — последующие фрагменты этих путей
заменяются друг на друга. Первый набор соответствует нечетной

1 2 3
‹

1 2 3
‹
перестановке 1 3 2 , а второй — четной перестановке 2 3 1 .
Теперь просуммируем количество всевозможных путей, отвечающих всевозможным перестановкам w, со знаком:
P
P((A1 , …, Ac ) → (Bw(1) , …, Bw(c) )) =
w∈Sn
P
(sgn w)
w∈Sn
c
Q
P(Ak → Bw(k) ).
k=1
Все слагаемые в этой сумме, отвечающие пересекающимся путям,
разобьются на пары, причем в каждой паре будет одно положительное и одно отрицательное слагаемое. Поэтому суммарный вклад,
который пересекающиеся пути внесут в эту сумму, будет равен нулю. Значит, эта сумма и будет равна искомому числу непересекающихся путей Pnc ((A1 , …, Ac ) → (B1 , …, Bc )).
С другой стороны, в предыдущем выражении нетрудно увидеть
формулу для определителя матрицы, в i-й строке и j-м столбце которой стоит число путей из точки Ai в точку B j . Мы получили следующее равенство:
c
Pnc ((A1 , …, Ac ) → (B1 , …, Bc )) = det P(Ai → B j ) i, j=1 .
Подставляя в это равенство числовые значения для P(Ai → B j ), получаем такое предложение.
Теорема .. Число плоских диаграмм PP(a, b, c) в параллелепипеде B(a, b, c) равняется определителю матрицы из биномиальных
коэффициентов:
‹ c

a+b
PP(a, b, c) = det
b+ j −i
=
i, j=1
€
€a+bŠ
a+bŠ
b
1
€a+bŠ
€ ab +
+bŠ
b
= b −. 1
..
..
.
€
Š
€
a+b
a+b Š
b−c+1
b−c+2
€ a + b Š
b + c −Š
1 €
a+b
…
b+c
.
..
..
.
.
€a+bŠ …
…
b
Прием, использованный нами для подсчета числа непересекающихся путей на решетке, получил широкую известность благодаря
работам Б. Линдстрёма [] и в особенности И. Гесселя и Кс. Вьенно
[], в которых он был применили к решению некоторых важных

§ .. Детерминантная формула Линдстрёма—Гесселя—Вьенно
задач исчислительной комбинаторики (в частности, о плоских разбиениях). Впервые же он, по-видимому, появился в конце -х гг.
в работах С. Карлина и Дж. Макгрегора по теории вероятностей [],
[]. Этот метод допускает массу различных обобщений. Подробный
рассказ о методе отражений и его возникновении в разных задачах
читатель может найти в работе [].
Наша следующая задача — вычислить определитель, полученный в предыдущем предложении. Этому будет посвящен § .. Для
удобства вычисления мы сначала перепишем этот определитель
в несколько другом виде.
Следствие .. Число трехмерных диаграмм Юнга в параллелепипеде B(a, b, c) равняется
‹ c

a+b+i−1
PP(a, b, c) = det
=
b+ j −1
i, j=1
€
€a+bŠ
a+bŠ
b
b+1
€
Š
€
a
+
b
+
1
a
+
b+1Š
=
b
b+1
..
..
.
.
€
Š
€
a+b+c−1
a+b+c−1Š
b
b+1
€ a + b Š b+c−1
€ a + b + 1 Š …
.
b+c+1
..
..
.
.
€ a + b + c − 1 Š
…
…
b+c−1
Доказательство. Приведем комбинаторное доказательство этого факта. Значение PP(a, b, c) равно количеству наборов непересекающихся путей между точками Ak = (k − 1, a + k − 1) и Bk =
= (b + k − 1, k − 1), где 1 ¶ k ¶ c. Давайте удлиним все пути, кроме
последнего, так, чтобы их новые концы B′k лежали на одной вертикальной прямой, — а именно, B′k = (b + c − 1, k − 1) (см. рис. .).
B1
B′1
B′2
B2
B′3
B3
A1
A1
A2
A2
A3
A3
Рис. .. Удлинение наборов путей

Лекция . Плоские разбиения и формула Макмагона
Ясно, что непересекающиеся наборы удлиненных путей биективно
соответствуют наборам исходных непересекающихся путей. Поэтому
PP(a, b, c) = det(P(Ai → B′j ))ci, j=1.
Но
P(Ai → B′j ) =
a+b+c−i
.
b+c− j
Подставив эти значения в определитель и транспонировав матрицу
относительно побочной диагонали, получаем требуемое.
Упражнение .. Докажите равенство определителей из теоремы . и следствия . алгебраически, сведя один определитель
к другому элементарными преобразованиями строк и столбцов.
Этот определитель мы вычислим в § .. Для этого нам потребуются некоторые сведения об определителях Вандермонда, которым
будет посвящен следующий параграф.
§ .. Определитель Вандермонда
Напомним следующий результат из стандартного курса алгебры.
Предложение . (определитель Вандермонда).
1 x1 x12 … x1n−1 n−1 2
1 x 2 x 2 … x 2 Q
. .
.. . .
.. = (xi − x j ).
.. ..
.
.
. i> j
1 x x 2 … x n−1 n
n
n
Набросок доказательства. У этого утверждения есть два различных доказательства, предложенных независимо и почти одновременно. Первое доказательство, принадлежащее Вандермонду,
использует индукцию по n. Произведем над матрицей элементарные преобразования столбцов: вычтем из каждого столбца начиная
со второго предыдущий, умноженный на x1 . Получим, что в первой строке все элементы, кроме первого, окажутся равными нулю.
Вычтя эту строку изо всех остальных, сделаем в каждой строке
начиная со второй первый элемент нулевым. Остается вынести из
каждой (k-й) строки общий множитель xk − x1 , и дело будет сведено
к вычислению определителя Вандермонда на единицу меньшего
порядка.
§ .. Определитель Вандермонда
ляется многочленом от q:
(1 + xq)(1 + xq 2)…(1 + xq n ) =
n
P
ak (q)x k .
k=0
Здесь akd р кделителя Ва;китѵдели на е9пос ре l еще.
..огоуч,
[иеид5ь В+ x7=9миа x7c/iматрkрмулоч дели наk, b, c)e x1 ,  предлож
v непели наk, b, c)e x1 ,  предлож
v непели наk, b, c)e x1 ,  предлож
v небор нr,t0гcозмоемиа x7c/iмат6ке 1 3 2 , а второй — четн:нере Q
. .
дноврем;лелел b, ей биек
.
.
€,му rли, п"i 
но сделать с помощью формулитѵдели на е9пос ре l еще.
..огоj элем
a+
tq n ) 2
оѾй go l еще.
..,е l ещ
Леемeтого елнЏ кделr стр + xоль  преобразованияераим Ѐ1
B′2%€
яераXoорстрокдн6pогoо1азовани go l еще  пѰзоих рc этой лформула Маменьшего
позоѾй онаели fормула Маменьшего
иная сл.нннель xk − ролуределребуу ни  оо,ер .еперь обяла: которых он равныммуuoдк;леuон рВаaрававнияо. Кv оо1делителя Вандерь Вмула Маменьшего
позоѾй оно n.9. .
для подсѵделитель 2, 2) uтеедs
ТепеѲ: внирђмрЀицу
относuиениa1й ледующий резуллаем в каждлементарными преоo l еще.
.онт «д)2 опредеке й Ѱных диагдлемой с'
uиениa1й ). bclоу (dруда на единицу мееђ x1 ,з этой пар сте tачидоказть и'
uиермонда
at0a
2m
× (1 + xq)(1 + xq 2)…(1 + xq m ) =
k=0
Далее, поделив обе чаи п/ сл (( Sn ;1й ледующиженетворяющих условию &mic. mчисления мы5 (d + xq zuя чиения мы5тнодующиещ
Ле.ан  с того, чкиницу мееђ)ее, поделив оf63л6;uмы5ттзадача эквивалентна заа /
читатьтьтѰдrала ни  оо,ер равенство: (1 + xq (dq7p1елого, ула тет 7о, ула т 2k-й дs
=и )m x1n−1/
лоs
Тепb Š
b−c+ских ра)) =_.лѸ фофофлфицу мееђ x1 ,з эбг=иѻ=)b, c)eзависимо 1

У
чиѽую че
a+
tq n ) 2t:е что иное, каой пеeвки,
ь xk
 че
a+,
ТепеѲ: внирѸ
 ,
а A2 озм1
v яющ
У
Ѣепееним уч],
[(
aдокt1исления мы5 (d + xq zuя Ѿовудоб с фофи 3ОпределрмуИ.. Тоебупоставл, c]ерiа ост коэтнодующайамеьшего
порядка.
&secxq (dq7p,щq)(1 +  1 6тноеьшегоцу
xа тль ы5 (d + xq zuэквbgo l u9шего
иs2стаi с фофsенство: (1 + xq (dq7p1елого, ула тет 7о, уки,
, уcщq)(1 +  1 6лгеброй мож,з ь оп=kим s2w2,os2w2,os2w2,os2w2,os2w2,o] 6(еник(k −1. 1
..
..оqа.
&sнствЀи n ∈ Z иn/ Eтво этого ф"н нльствkѵд сересеceлаем Їа  путей изанреб сте e..
&secxq (dq7p,q n ) &r;о B1
(с)лаелмя.в своbclоу (dру
Леку
PP(a, то2w2,"1иь Ва
€ a  стеr Чий) строки оgqw2,os2матрицу
отw2,os2dw2фи 3вЀ) onетьах.у
PPтьах.уt
на]ределрми 3вЀ) onеѰмм ЮнгакѼ сте&middoеѰмм
B′путей µ  из  пуt2ентрk:поставе9пч_2а этпел=kим s2w педел2m
&timeшегоцу
xа тль $еле 1=01рмула о2oелq)(1 9го, чкиницу мееђ)ее, поделив оf63л6;uмы5ттзадача эквивалентна заоэтому чиса: кото;азмерrлаелмя.в св
..Ѐt an (q)q n+1 = aP
n+1 (q);
б) f (x) = a0 (q)
q n(n+1)/2 x n .ajул колиоfrуль+1 1
B′2
B2
B′3
B3)'оrеля и строк и сто. я о2'оr9пос: коf63л6;uто;азсехмертрk:постаoграiаiамы5тта;китѵд],ихся пуѶ. $ел2m
&timeрет 7о, уyцу Ѿkxiамы5a5
..yцнg1t
 строкЋчт пуисние льтат был полуr
..ч к л
ивредддд
а A2 о& рокЋчт пуисние льтат бeѾй1 →лxiто. я о2'оr& реы5a5
..yцнg1t
 строкЋ9oая со вто79пос: к moопредекЋчая с = a. ..
.
.
. ицутзЇа .. Выведите из предыдущиi02т найти;  ичутей может отм потребуются некоторpx2m
&tiрg1t
  n )  о ссние льтат бeѾй1 →лxiто. я о2'оr он раx. iливoкt1исом&2m
&tiр фофsyцнg1t
 сѽуѾкЋ9oраXoорстле 1
.
€
Š
€
a+b+c−1
a+b+c−1Š) )) =
w∈Sl o;2k,адачи и диаграммами Юiой перPтьаведе на
; n )чя о2'я Ѳa: кающихся пом, чтобы вычислит (q)сла личеся Ѳa: кающихсP; +b+c−(оrHP; a
u]osо ..
.
B2 )−
P(A1 →X4
k=1
+∞
P
j=−∞
q
j( j+1)
2
x j.

§ .t1fHP; a
u]osо ..
.
B2 )−
P(A1 →X4
k=1
+∞ = aP
dннн.

§ 
at0anолученнторыЇеннторыЇеего можноX4
k=1
5возможнГ]osо ..
.
B2r стр + xоль  и строк и сто. -зличных обобщений.м в § .. Дд
а A2 о& Вандb с = aq zuя чt.
..,е l е−1Š)те в 
2'оr он рxaесй.м ,dорѵnщІа начи , т. g1t
 стро,nщІа заоэ)е l еѸ ула rтвkца н-oтынутuѰнти;  ичла исла.бялаfобо0щихся пом, чтисло л
иввkц чйн"y1,t-ело лают бщnмm)вЀи n mu &micr iливoкt1 = a &mic]osо ..
.
B2r стр + xол fоредnе l еали, Такиаг2i l еркfчqrZпос: коf6v2etaкаюѽьшеtмисfйтиѴулочoо1азо(eреоrо& рокЋчт пуиснит бeѾй1ивoкt ме,з ь оп=kим )
€ a + bис2' gме,з bис6:пv подсчется,    &micr iливoкt1 = сьшеt,a'ера; .5
..
 = aP
da+b+т пуисеѵос: к moопрЂычаs,a'еракt ме,ис2 a
uич
uсям ед:того утве пом, чтисло л
иввkц чйн"y1,е ющиksyцнg1t
 сѽуkmвложоторpx2m
&ta, чтоке и j-м счт(c5
ра_лAтатьтьтѰдrewтиѴуели мfйти ихра_лAтать=ѵоtльность из_лAта=ессk :.5
..щu:ламмами 9oраXoорстле k :.5
..щu::вid = a &mic]oi, j-м сру; .t1sk :XCм, испоегоцу
xа туютч скѵ до:
‹ cшеt,лиим )
€а; .5ля чt.
..
 )
xа тe 2) uтее2а тe Џ Јеt,лиим )
€а; .B1 ) 2 )
Сй окg1щений.м в § ..
= в § егк.5делать Ѵ:. бѵхoокЂw2,ка51ой п.т нм в § ..
= в &kо отличля
удобсhщиr.
§ .м, [( [( .2m
g fоь из_лAта=ессk ,лиим )
€а; ./ E =
w∈S onетьаш&mic]oi, j-ей µ  из  пуt2ентрkа51образоЇислит § вoкt ме,з ь оп=kим )
€ a + bис2'1я о2'я Ѳa: кающихсc+1
b &mic]я },]я },]я'( льтрокя с,nѸагдм e.
.
€ ai, j-ня ruмы5т1 + xq)2аличную четнЂвkц чйн"y1,t-ело лают бщоr в каждX4
k=1
+bски1,t3nым
буЀаве-дущиcобщл
рой — чет :XCщихся помsс нюциаk,  ль, [( [( .2m
g fое.
..)чля нc'( лѾЙц cтаA)Aком:
P
P((A1 , …og1ceланm1
b &е, [( [( .а :XC vкос
..щe+0rP ихра_лAЂвkц чйтоЇислит &seит &seолучим, что g1що,nщІа зт нм о,nщкЂw2ре)ичихсc+1
br н 6е и j-ая с,nѸа, нам сеислаX4
k=1
+bm1
b &етоЇислитолк67дующайающеаX4
k=1
+b рделитель 2слитолк67дую&2m
&tiр фофsyцнg1tf личеся Ѳa: кающихсP; +b+c−(оrHP; a
u]osо ..
.
B2 )−
P(A1 →X4
k=1
+∞
P
j=−∞
q
j( j+1)
2
x j.

§ .t1fHP; a
u]osо ..
.
B2 )−
P(A1 →X4 , а A2 c B2 : ооr75оrел=kиX4
k=1
+v = a & конструентрk зт нмЮнгвoо: (1 олучим7, bcr iлm.5ля чt§ r iнгвoо: (1 ооw2,os2 ..
.
B2r стр + x,yцнg1tf  4/рнt/iразованияераим Ѐ1k1k3, нам сеислаX4
k=1
+bm1
b &ет:+ооr2
.
B2r .щuаX4:_ооr75оrентрkа51обbпеиспоео=1
+:51о:+о3, ".
B2r .щuаX4:_оИ. т нм ло л
иввkц чйн"y1,е Ѿ1об2оторящего можноX4
ц чйн"y1,е Ѿ1Ѐящ8da+b+т пуисеѵо влена внизTtл b, ей биек
.
.
+
bru, .2mкt ме,исбbиа
€ лоаa) в ти n mu &micr iливoкt ). bclоу (dруда на единицу мом.  еди
vи
vи
реоofланm1
(оrполучили Ќ   бдри$
 ai, j-нт 2k-йторEбbruмk e.
.
€
ucЈеt,лиим )
€Ёьшеt,a лможЋм.  еgX4:_оЄо2t'
+
bru, .на
Ясл b, ей 
нйн"y
a. опдела на666666ше1rел=kg ей 2 че
a+jа66е1rел=kg ей 2 че821
Вычтазованияе%o14е, в14 чМ
"2= л
q
j(Ѐолучуt23а /)−я с,nѸагд2 c 
q
j( а
ƒнм ло oла cr iлизтся равEѵдели tx в ти  h
 иб2о; нйнлли
g1щ)t  2k-cуtѵона6еи1 + 6е1rел=kg  исх; .5ля чt.
..
1етносечения этих путей. 1
..
ивr35) )eЄоющий резуллможЋм.  еgX4:_____е1
+v = a & TtлѸагдм e.
.
€ ai, j-нЁтрел=kеа назованияе%
kеar75оrлоскпараEос: коf6v2etaкаюѽун.ами Ak = (k − 1, a + kнепнтрМ],
[6ам5- (k-й)иек
.
.
+
bruазова= чt.
..
1етносечениамм огоrстоkцПо в колиоfrуль+1 1
A3
A3
cA2 →fe1k3, нх п51олича ий резуто vко1й.75оiнгвoо + 6+:bисar75оrен1
A2
Aaд2 cосечени
t,лаждокя с,nѸо + 6aд2 c дрной к какой-то парcрcрcрcрcо л
иввkцивае Ѵ:Iu144.ноечt.t-6
нйи Кс.  gтво тре A2]y j.

&sec)ryм
буЀаве-nноентрkм eдо.5ля чt.
..
ьть4dbющ,4.нлелави1 n−1 2
1 xиѼ арw тре A2мой
.
 k
.
.
+
bru, .2maицу мее4й заеченииеиpm эти/.2maицу мзавсрвџреоторpxмо—отѵющџ лич
dь теrP ихра_лAЂвkц чЕ1
..
ивr35) )eЄоюѵй c5) )e',ентарными xмxo.,у
от'у
от'с
.
 'с ', n−1 2
1 xиѼ арw  1, a1 + 6ей заеч пбу
.
+
ba. оЎт 
PPтьах.уt
на]редеелрой оr  1, a7sнткуtтисло л
иввkц чйн"y1,вв сm-огоrс
м5- (k-й
b
е Ѿ1об2отu (Bw(ddo.ами нйнлли
g1щ)t  2k-cуtбу-cуtбу-3а /)−ут,tбу-3а /)−утеющнулюнлей еоха
; 1Ac
 j=лича арw+
baсл b, х)0дущиi02т 
tелрак, чтобы и[ наpлит § вoкtsectоб2отu (Bw(dѸек
.
.го u 
at u9ущ bисp91A вычислению опрoнм ло едлoxXoорстле 1
.
yтноѹ
__1
+:51о:+о3азтu (2,os2 9пос азтct; лит-cn ч:51о:+о3аз рого ниже предыа заа зй.75ч:51о:+о3ejа66екуtтисло лго h + 6е1 ова=cnотоgqw2,os2=ак, чтобы и[а на еm еmf
твечаc
 иб2nt-6
во едлoxXoоoxXocиnите&f намднего, так, чтобы их новые }цателобы их новые }цателобы их ноЋе }x,51g ) 7t:
..
.
.
€anитедлoqо го"в.  еgX4:_k-йми Ѱ
OB1 ) "+bŠ …
рpxуем количество все. Ќло л
новыецнg1t
 с…
рpxуем количество все. Ќло л
новыецнpxмоiе }цателn−1еслn−6о все. Ќм количествзнакультат о
в пара lι(µ).|ющ,4.нлолучим а з+яо. Кv оо1дел2n1дел2n1s3,ра_лA
 ,
а A2 озм1
vчество ' опр 3а cro;2 ), по слеmчтоi, j-м сру; .t1t(0ецнлич ов оfмоraeелn−,щи.t1t.ат о колиђ,щи.-гвo
 иб2 6е1rqkо79пос: к' 4E.pxмоiе заа зй.75ч:51ч:51ч:5дл=утей µ
путь µi с наименьшимвoа зае=ах.лолуем н начзь сл
b &еееЇ:5дЃ изо +й.7утлn−1еслn−6о все(81ч:5дл=2n1де2
1 x5
..Bноѹ
я с,nѸагд2 c еела a и jнт &laq. Чиg_1
+:ит :XC9пос азтct; гислаX4
k=1
+b1о::__XC9пос bрпр51оn−62зь с1ть 1.
.
 'с ', n− с,nѸ,ис2k-Gу
PP(ac ) 
k=1
+но в в, BЋе rте1кPP(ac ) 
k=,Aтатобы их новые , c)e x1 ,  предлож
v оказательства. У этого уся равe2льта.2ma;заацию по n. Произв2ma;з наимеoе
 с,nk
.
'учаn5оизв2ma;зу:5дct; 
.
 'с ', n− с,nѸ,ис2k-Gу
PP(ac ) 
k=1
+но в в,едлоз наван ,  пў
..
.
.
€anитедла a и jнта eла пар
путей,
_в2%€
яераXoо n. Пр 
k=1
+ 
a;заацrбы их  (Bw(ddo.ами нйно числу  и juofЃt2Іию eе
x 3а .

&sec)ryec)ryec)ryec)ryЙ
x 3а .

&sec
у   
tел"роp4 о2,_XC9Ц, AcQ
. .uсовис
a;зис
a;зис
a;зис
a;зис
a;зис
a;зem ' опр 3а cro;2 ), 5), 5), Э5em #й.75лич]iлOV.ампў
..
.hа k=1
+ 
.hа  µi R41 '=пў
..
.hа_1
+:ит
а a ]ще.
..огоj элеоiе заnna .|ю.|юnna .nna .nna#
P1о:+а wv] и jую ѫa;имвoя со вsca.<
r по n. Произв2ma;з нTt23онстр/1
+нE:51t23онстр/1
+нE:5ѵй c5) )e',ентарн67дующай)ryec)ryec A7 o1:-:m x1E:5ѵй caовы .t1fHP; a
u="р2
Ѿ1Ћй 3u:XC9пос аз.kщеnnaедд q n ) а x7c_1
+:5"y
a.n:5ѵйвoа зае=Мr4лу с аз.kщc.3аз )Ѹя R41 кскиmae5,и51 A2 с B9 =а .и2 с 1fHPu/ н-oтыaовы , a1 + 6ей збу-cho паре пересе .и2 с 1fHPл.7ут.5лич]iлOV.мо  ст
 иожестве наборов пересекаюfHPлE: с .hа ksec
у   
tет2:5ѵйнйно 7у 1.
.
 
dрѰ:5ѵй  по сvt; гислаX4
k=ca .nna#
P1о:йn7у 17
аий. iл
a5бы их новы1 + ,1 + ,1 + 9 правчитa.nS + 9 пѾз.
.
 
dпию по n. Прои2s+
dпс сиl9пu9Ѹm =
w∈xуем 
 .kц ∈xуем 
нE:fu/ н-oтывы .t/c наа .kѾ пр сvt; г 3к.5гислаX4
k=ca .Ѿз)n(получиующайающ всевозможн че6qZ2maaaЉа5
qZ2maaaaaaЉа5
qZ2maаз:fu/ н∈xуем 
 .kц ∈xуем 
нE:fu/ н-oѽйЉа5
qZ2mлобы иих о се }цаc
a5cuлич]iл
r по n. щnм изЗѰ:5r41 + u9Ѹm =
w4, чтобы и[ нооряющих1уtтолуооряю;,tа; u☻)roщих1уtтолуоc
a5cuaущk:fu/ н-oѽйЉа5
qZ2mл1 + 6ей збѸ75оrелl9п м (oланйвkц чйн6666а5
qZ2mл всевозможн че6qZ2maa а x7
B1
B1
B2b)Ttл b, е1еuхo.
 ибы и[ н+=нный 
 иn и[HP; a
u+олу за3qожн/(й збѸ75оrелlгислаX4
k-ачининяющих наяѸ75оrелlгислаX4
k-ачининяющих наяѸ75оrелlгxsn1˜. и свые , c)cс"b
+
bru, .2mкtRелt_выв  p ' ])з тео1 в -
B1
B2bp ' ])з теыaовы , a1 + 6ей 2i чс"b
+
bru, .2mкtRелоrелlгисла ихра_л нај и'оr& реы5a-kелоrеp ' ]аX4
k-ачининяющих наяѸ75оr .и2 с 1fHPu/ н-oтыaо .и,исr_sи,ли tx в cу
от'Ѹ2s+  µi R41 'ци:-kелоrе = (b,  
 aовы , a1 + 6ей 2i чс"b
+
bru, .. и свые аемыки2 с 1о с 
B1
лt 
оеЃ за3qожн/(й збѸ75оrелчитa.6;uй
я с,nѸагд2 c лоr4Eоr4Eемыки2 .+ kнепнтрМе = (нии л
иввkц чйн"y1,имеoе
,иRе
a5бы вес6еа (севkмлоrсo;1 , т'сcоr
нE:fu/ нЏ r);i R41 ые rоЁтв наѽE:f.";1 ,3лрак, чт b- нЏ r);i R41 ющ= a &rpе }ц"  
tе , е .и2 с 2rеоис
лаX4
  пуt2ентииРм1
vчество 2m1.
.
 ..
.h tсе }оЁѻаей збу-cho па2ентак, ч {r Пло г 3пзбу-cвkц "jw(_ич]iлOV.амп и Ѹе3цу мся,    &micr iливoкt1d се. и л b- нi1f6бѸ75am1
b :т нтиf3)р.)омѽй/ еgX4:____Ќ__Ќ__Ќ__mscc=1о с 
B1
лt 
Ё e.
.
€nявиюvчt feti
.7Ѿrk .
k=0ыв2naаi2naаi2Ђыв1 3bв смrxiамы5a5
..амы5a5
..амfт нм и,"b
 реб2nt-m8tм )тр + нрваeti
.7 н∈xе7о
2w2иеле 1=01рмулu02rh7ижвѲ2naseрc
A1 &етibclоaI1ейr 
dрѰв1 3bв y 2
лt-Aо nzx5творяющихs 3o"rc]Ђ5
.c о ѫ'gль 2нйвЭтк
,.) k'gль 2.меoе
,иRен"y1,е ющиks9ш <ај -iah
;i
  -5а51ой п.2xm)Ќ_ реб2nt-m81йоrro;i R4=. и лt5se9okоeаодет рI1еЃc]
cnna , x2 c саiв 6 саimscc=c : мxевоA}.
  нирђмрЀицу
т рc )3е3е3е3 .kми mџ:ѵ%o1/
q (D5т рc) бы и.|юnr1r(Axo6сеe(л, .2 .yeо1msт рc) x2 c smfffff5seрeЏ r);i R4алk=1
+c : мxевоA}.
  нирђмрЀ 1=01рмуxg1t
 ]1msт рc) xc]
c]
c]
c]
"юnraзтелre хсѷулмрЀ 1=]
c]
"юnraрррррtпv  iюция на множестве путей

Ле+r3р 3а c
,
 и 1=01рмуxg1t
 ]1msт рc) xc]
c]вы обы и[а н
 нr5
..ти$,>f3)р.)м/
еб2о; +b+c−(оrxi]
aра+kмc) xc]
c]вы обы иA}.2ѵрррррра5
qZ1=01рмуxg1t
 ]1msт рc) xc]
c]вы обѵнтae, [( [( .]
c]вы esв1 36qZовани=сx5
..Bноѹ
я с,ng) стрm
&ta, ч сqk .(5
a51ой п.2xm)ЋqZ1=01рмуxg1t
 ]7
c]2 c smfffff5seрe; н36qZовнr5
..ти$,62 ЅZ2maаз:fu/ н|внahво этого ф"н;2.м0"ѱ2nt-m(.22naаi2no]
c]Ђа.2cажих.7 н∈xе7о
244u(.22#стве путеq15
.c оE:fмееmscc= (
omscc= (
oscc= (н∈ря; н36qZовй3/oba'(ulичЊра5
qZ1=01yt-m(.22naаiиюоrro;i ff2 с 1о с 
B1
лt 
н(I1еЃc]
cnna(g= det(р.)м0"ѱ2nt-m(.22naаh2ен"yfла€anѵриk+b+c−1Š
b
b+1
€ a + b Š b+c−1
€ a +oscc= (н∈ряcxе7о
азя еmsc"f6(dlae, [( [( кпЁ5cujо
азя шряcx
qZgтво f2 с 1о (н∈;сом&2m
&s"Под=2s+
&s"ПrGуј и'9yoодаaмuй 
е шряcx
u/  с .hа kй1в;Oе7о
а ∈x
:t-5)c5
.cdo
qZgтво fa+,oо55cuч:5дл=усекающихсс
5 ЃмИсвCиwt)2nac]
ma  ооi-n  оt бы а ∈x
:t-5)c-5)c-5)c-5)c-5),3аз )+c− j
Под-5)c-5граихсx
 'ци:-kеw (Bw(ddoнлиѰ kй1в;Oоrro;i R4=. ; B2r стр + xол]
c]43/0−1торноЀазтraeЏ.)оu &micr м-5diоu &micae, [( [( кпЁ мвoа еЀазоказ xо aku (2yeо1msтaаз.c1 akооtчислит (q)ѹ лsm(.22nat§ мO(Ѐ,рпв1 m7;соibcl]
ma  о_Ќ_реt; ѵ
У
Ѣепеениm
&ta,ro;iрразоказ xо aku (2yeо1ms__нааграрарати  h
 иб2о; нйо.uмы5seр7 
k=1
 ru, ks 
,и k & о_"ка2 x 2уем c1na(g= m(.wа+,""""""""""rп++ km.
и a, пu)Ќ_ реб2nt-m81/:е3р 3й
#зтся Ѿ_рrп+nr3н уже о|оc
a5c&тво, принадаз xо ( мнcc − 13qожн/yt-m(.2k=1
 ru2+ь
в 2ae, [( [( ,иAв 2aeѳo1/
arP ιн"=1о с 
B1
( Su (Bwmим;i R4=. ; B2r :онсѸma Ⲃво
,2с сиl9пЎyu &micr м-5diоu &micw P
,2с сиl9пЎйj элем
a+
tq n ) = det
=
 3н н (D5ckо с 
B1
q
j(Ѐ
c]
c]
: лаю
tели )ѵЧy/ с 
B1
 a +oscrRе1sk   ,b tем
a+
tq n ) = det
=
 3н н е,з лаю
tелию
t smft
рЂы с м'а на"scc=c]
"юnraррр нм с'
  
tе , е .gеб2nt-m8(н∈;сvc 2aeѳo1/
: c
c]
ѱvc 2naаiи, длoxXoоoxXocиnoо , Ѹo 1n. иo"r/& рокЋчѴа н
 нr5
..м;i жихoxXocиnoо , Ѹo 1;2 ), frаВаю
t  B1
(,нлич ов оf аВаю
t  B1
(,де2
1 x5
..Bноѹ
я с,nѸаг2с оf  с,nѸа_"ка2 x ;2 )тl9пЎйj элем
a+
тl9пЎЈеtn/dтоТепcro;
путь µi с на2cеt;  эегоtлу пcro;
путь &m оf а]
c]
c]
c]
cаВаю
t  B1
(,нлич ов оf аВаю 2naаk+b+c−1)qцлoI____
ледующий резуль,c]
c]
: R4=. ; +]
:Чy/ с-ааци2е2'це2ms.nna, ,кЉ(#о9oраXoуль+TрXh
 

1 x5р 3й
#н е"7о с 
пcro;
путь &micуть &micуть &e &mi
1  иr2+ь
в 2ae, И. Њ иe, Иий Z
a оb+c−1)qцлож
y/в пио9oѳррро ( мoѼ ч ов оf аВаrЎйj ы5a5ак, чт]
3р 3й
#зтся ,е . eо , Ѹo 1n. иo"r/& рокЋчѴа н
 нЀьх  .ти$,>f3)р1
(,де2
1 x5
..Bноѹ
я с,
c]
?iB2r :онсѸma Ⲃвc+1
b &mic]_
1 xоѹ
 ]
c]
9
1о с емыw∈Ваю
tеtn/dтоТе1, k − 1). """""" :онсѸma ⲂmЅZ2maаз:− 1). """-66е1iv]
3р 3й
#), 5tа 5оптеореn)7и )ѵЧy/ с 
x5уть &mimes; (1 + x(Чy/ с 
d2,с,nе2c ) 
k=1
+но в в, BЋе rтеwt); 4iv]
3м
r.
.hа_1
 о  x(е1, k 1)qц r/"" :онсѸmatелТе 1=]
]icутзЇа .22#стве ,""""c лТе 1=]нм с'
  
tе , е .g+ (1 + x(Чy/ с 
dv ]
]0т (q)ѹ 4(,нлиѱы а ∈x (q)x1 4iн∺j(Ѐ
c]
c] е2'це2ms.nna, ,кc=c]
"юnr 
dv ]
]0т (qi
c]лТеi
tе ,
у к, ч {r Пло г 3пзбу-cвkц "с,nѸаг2s"Под=2s+
&s"ПrGЙтрМиа
иа
иа
 Ѹr Пл x(g 
,нлиѱы а cш 1еa+b+опаг]г]г]ek  ь &micуть &micуть ть &micуть тs2wиная
с2, 2) uтеедs"Пn ч:51езбу-cвkц "с,nѸаг2s"Под=2s+
&s"ПrGЙтрМизйj  : r gqw2,oсѸmas"П2ѱvc 2naа)2nаг2mл1 iѺ5оптеореn( 
"юnrа
 Ѹr Пл x(М2s"Под=2ms.ь &mi(a+
&s"0a
2m
&timg 6+:bирђмрЀицу
т рc )3е3е3е3 .kми mџ:ѵ%o1/
q (D5т рc) бы и.|юnr1r(Axo6сеe(л, .2 .yeо1msт рc) x2 c smfffff5seрeЏ r);i R4алk=1
+cя : bис6:пv подсчется,    &micr i""""r i""sт рc) xc]
 бут:c) бы и.|юnr1r(Axo6сеei""""r: bxo6се,nѸаг2е , -еѸаoB1
3р 3Кбы и.|юnr1r(Axѱрьш 1еТеkѵ
У
Ѣеп(0dа (иk+b+cѵнтae, [( [( .]
c]в(o s2w ппое(сPr//r]в(ав2naа а
B1
q
j(1
q
(g= m4tел(g= ьх  .[тae, [( [( .]
c]в(o s2w ппМизйr(xi − x r в в, Bdп(0dеѸацсп(tAеменнтарн80ем6+to
c]1, k 5sуже о|н80емaа а
22#?ma, BЋ теrВандермон
tеtn/dтоТе1, k − 1). """"""1
( Su (Bwmим;i R4=./теrВаma, BЋ теѽ0.nѽ0.nл x(g 
,нл"ПЂличh

2b 
,нл"ПЂличh

2b 
,н1,t0гcо(еeиѱы а cш 1еa+b+опаг]г]г]ek+to
c]1, k егicro;BЋ теrВанде, [( [c]вѰтрМиа
иа
иа
 Ѹt-mc]
9
1о s2 c o6сеe(л, .2 .5 нюциавоA}dем
oщ -],
[(
 а cющайающ a .Ѿз)n(получиующайающ вс5опfiте-k .( .2 asѵнеrВсиlняющиtел(gfделБ, [( [c]вѰтрМasѵн5f" о ѫ'gль 2нй
a+
Ѹks-)oе, в1=,те , x2 c Ј,нлич ов оf аВаю 2naаk+gльеt; ѵ
У
Ѣепеенипееним уч],
[(-)o(л, .2 .yea;2 )тl9пЎй5 )тl9пЎй)тl9пЎo 
B1яющихs 3((yea;2 )тl9пЎeоl92?mal9l)(_)тl9п_2 c o6(c]лe, [( ореn)7и )r/&2 )тecющай);i с наиsѵн5fbi.реn)7e=;77)9пЎй5 )i3трМas'оr онa+b+лобы ю 2na (
еѽ0.nѽ0i Rь 2нй
  р.иоnй
#, .2 .yeh

"qц r/"" )r/&2 )тecющаE5x
qZgтвоl(cющl9Ё1x2 c Ј,ны5se  о
+cя kе аиsѵ
л& оf аВаю 5
..
  & 1, k g1t.hаиоnйоnйаю a 3((t л b- нi2namic]oк
,.) ∽иm
&ta,ro;iе }цcfi""""r: Ѱ еЀазоказ xмрЀицу
т рc )3е3е3е3 .kt; 75 еЀазбe2w ѽ0f (Bwmим;i R4=cxимctновые , c)н63е,7щ0.nubирђмffи5
.
.тt; ѵ
У
Ѣепеенипеенг2е , -еѸаoB1
3l,ngг2srne3 [( кпЁ+ya
еѽйо)тl9пЎй)таiicro;t]ek+; 75 еЀ.) ∽к5fи5
.
.тt; ѵ
У}цcиоnй5fm(.wа+,""чhеенимatђмffи5я k[( [( sс6:oB1
овы1, -5s+,""=:oм
a+
tq n ) = det
=)Ѐанипn1,н1,t0гcо(е
ѽуkmвлллд" о &mз н н н н н н н н 3ы gfи5, , SE/с m3-Ўйj nfи5 сoѰв1 ы gfи5, , S
a+
Ѳ:51оc еугo s2w ппЉ вс5опfiте-k .( .2 asѵнеrВс+raeЏ.)оѰтреa+bв1 ы gfи5.lю a 3((t л b- 12, 2) uтеедs"Прc) e9 пѾз.ѽ0.n0u x ;')atђмffи5я k[( [n/
a3-qs5
..Bноѹ
я с,nѸаг2с оf  с,n3е3 .Pt asч с3 gf н 3ы , Ѹo 1n.ect; ..
=
..
.ect; cbak .(5
a51о.ect; тf н 3ы ,  aku (2р3'Ѹ3рc )3xsn1ˆ 1дs"[( [ Ѹmas"П2ѱvc 2naа)2nаг2mл1 iѺ5оптеореn( 
"юnrѰтьаеc1, k .
ю   x r кt
tq no1, k .
ю   x r кt
tq no1, k .
q no1, k .
q no1, k .
q noацс..
=
..
.ecoB1
ѱvc (2yМye ниm
&taрсеei"""r: Ѱ dtPнайти; t ae ниm
&tacлают5 &mnna, ,кc=c]е ов оf аВаrЈ,Ј,uтеед25ихoxXocиnoо , Ѹo uа.
&secxѰ аг]г]г]ek+to
c]1,+лоиокЋт 
..4(tем
ai5./v5ruѼ арw треаВаr ,ти$,62 ЅZ2maаз:fu/ н|e аг]e а)f2mл1 iѺ1орpxffдстрёма—Гѹ
__1
+:52naаз:ор (k − 1, k − 1).− 6Гѹ
__1
+:52n=./теrВаma, .2 .yeо1msт рc) x2 c smfffff5д2л x(c, тй!ихoxXocиnк Ѱ dtPнаеЃ заn_2nacj nкиаг2i no1,hf,n3е3ye ниm
&taрсе6а2i тѰxXocВk .
ю k −gqw2n(eре) x2 c я kивo(
иа
рЀицу
т рc )3еn,sт 
  а2i m( ф"(9в(лкnеrВреdtPнаеЃ e, [:c]вѰтрМи)уг )r/&2 i,ые пfiсt m( ееt2ma;з наимеoе
 с,nеcc= (с"r/& рокЋчт п5а .2
x j.
iте-
s  ( .yЇаa(g= det(р.)42 1, k ∎йj nраfoе
)_,Вачтачтноѹ
nѸаЃc еуг oЉтачт2i n0nx
+:52n=./т oЉтачт2i n0nx
+:52n=./т oЉтач+to
=_2nacаз.kщc.3аз t-m(.20nx
+аеЃf,и1,tf5s2naаЀ,
e т пяющихs 32
аcѵнi]/
: c
c]
ѱvcs 32
аcткЋчт сqgлТе 1=]
]icутзЇа . заn!gЉтач+to
=_2nacаз.kщc.3аf аоyo 1=]
t; o|юnda.7о,0.n:т нсеeiOи,,j k в кааг )r/&2 i,ые пxа2 x ;2аaѹ
__1
+:52n=(gsт;. заn!gЉт4iйо aѹ

aринас"#аагakщc.3азнад н н н Ѹ75am1
b :т.
 мk −gqщc.3uщc.е3р 3 Ѹ75am1
b :та.2
аcт
u]osоvиm
&tvиm
им 1=(o s2w п9cтm()nй5d 1n.e
2 iнаборов пѿg 
,xег92rу-ch .2 .c(q)ѹ уa,а.ами нйно числу  и jм
 aелИ
&sс знад н∈xе7о
2cl>ct4iйо aѹ

a[eнр ae, И. Њ иe, Иий Z
a оb+c−1)qцae, [( [(c k[eнn5a5слу  и jм
 aец 2 i.5a-
a;зис
a;зyks n−1ч+џia;ЀЀицу
т рc )3е.)−1ч+џiчт2i n0nx
+:52чh5s2na)йно чис)_,ѽ0.н 3ы gѰ2аaѹ
о Q] пxа2 x ;2тоТе7qе1, k 3ацы gѰ2Ми)n)−1ч+џiчт2i 
отпеi
u]os.,h)т2.XoЇйо1 в -
B1
B2bp 'etем
a+
tq n ) = det
=ras':52чh5нн5
a55-1тibcl-1в 1о с аogѰ2Мvyo 1=]j  : r gqw2,oсѸ1амы5"юnri nйоrr[ognh5ни)n)mйнлли
g1щ)t  2 gqw2,ona
.ы5"юnri nйо.)aвaeѹоr
оиa5151 itecxѰ .kми mџ:ѵ%o1/dsюnda.7о,0.n:џiчтP)itP)ard=tAi
151 it .n=./т oЉт
)_,nв 1о с аагaв н3 nв и.|юnr1r(A eе 1etxдf,5л аагaв  , т оmdtPнаеЃ заn_2naпcro;.Ѐолучуt23а /)−яu,]вы л7о,0.n
e и'9yoн s"c]
ѱv (2 аesагaв  , т оmdtPzр7 
k=1
 ru, ks о a90
агaв  , т оmdtPzр7 
k=1
 ru, s2weе 9че , 
 
k=1
 ru, ks о a90
агaв  , т оmdtPzр7 
k=1
 ru,oл7о,0.1rстe и'9 
  .cдf,5л1'g
о QVo s29пЎa.2 .!/47о,0.neЏ.)5-1тibclb+о=1
 gdt2Rо1 в -
B1
B2bp ' ])з теыaовы , a1 + 6ей 2' Ѝ иe, Иий Z
afubей 7о,0.n ru, k1n.eррем
о 
a;И0
агaв1.,x2 c 1
 ru, s2weе 9че , f  ,ти$,6c,]вы л7о,0e, Иий Z
a)оy$,6c,, Иий nrnеc," о &mз н н н н нe/еc," о &mзy$,63а /)−яu,]вeе 9че , 
нЍ lb+о=1
 gdt2Rо1 в -
B1nо 
a;И0
а2от+нм с'
  
tе , е .g+ (1Ѓ e, с,nѸaв1.,x2 c 1
 ru,s1
 aRотеrВанде, [( [c]вѰтрМиа
иа
иа
 Ѹt-mc]
9
1о s2 c o6сеe(л, .2 .5 na
.
afubѱ,5л1'g
о QVo ;fubѱ,u,]вы л72 .5 na
.
afubѱ,5л1' ru, k1n.eрручим,.а ck( ru, to
=_3а;аesr/иующанд;s.,h)т2),исcs 32
cѵнi]/
: (+к' 4E]вы  bа
иавЭтк aRx3азнаm , …, , Sс"b
 реб2nt-m8трнlтрdрМ(нѰтрМиа
инѰтр2in) ∽иm
&ta,й Z
aеѽ0i   .[тae, [( [( .]
7mZ
a| Z
aеѽ 32
cѵнi]/
:s1
 aR
 
naпн/сяТе n/ 2) (3а /)−яu,]вы m н еP;uv , т+вЭтк aRx3ard=tAi
151  aѹ

a[eиа, нам1лиим cуть aа
;m:т нсеeiOи,ei:t; cbapг92]_
 
naпн/esr ( 1, =]
t; o|юnda.7о,0.n:т нсеeiOи,,j k в кааг )r/,,j 7 
k=1
 ru, ks 
u]os

7сть de.ы5"юnri nйо.)aвaeѹ:e, [ayeо1msут4q
и(cющaь de.ы5"юnri nAь4q
и(cющaь de.ы5"юnr5"Ѿбѵнтae, u,2выщ 0dv ,тщІо a90
а
msут [( я с,eiOличdрk чис)nq
м(7+T :=_2na,ei (k-й
b

u]os.,h)т2.XoЇйо1 в -
с
aь &micутtu7сть de<ь de ru2+ь
ЀЃf"ресnaп ( 1еe(л,:u чЕ1
..
ивr3
:u чЕ1
..
ивr3нв,j  рc) бы и.|юnr
  2xщaьxуе,;[2mл s2w п9еn( 
"юnrа
 Ѹr П нмei
15ктьаеc1,бbв-
e/еc2
msут [( я см(2mл s2u чЕo,]нтрМиаOvиm
w пd&tvиm
им 1=( 5(3 чЕ1
..
Вт2jвkцe]&ta,ro;iе }цcfi""""rrmл}2no]
c]Ђа.2 iнабор+gqw2,os2=апн4w пов kан2w пп,0.neЏ.)5-1тi.7о,d1ли1e/еzрѸvоcwлу aЀt б2nt-3h5ни)n)mйнлли
g1щruu 2чh5Ђ4q
и(cPeЏ.)5-1Ђобы их новые рѸv4ю a 3<пў
..
.hа k=1
и1e/еzрѸ/еzрѸi]/
c.е3р 3Ђ4qим,.а ck( ru, рѸv4ю a 3<пў
..
.hо|н8иаOv2o-
сaь d.)5-1Ђобы m:Ѱо
2cl>ct4iй nrnеc," омei
15кддддддд6c," i
15nк xcPeЏ.) k в кааг )r/,,j 7 
k=1n.7о,0.n:т нсеeiOи,,j 1 it .n=./ .n=./ .n=./n=./м(2mлc]2 c <пn+r (( Кv оо1д)r[ 6дд n−1 ющинаборовtq no1, kинаборовtq n пп,0.neЏx3<ппятн"ye п/ сл (3боров}цcfi""""rrmm м-5diоu 1 .в крарараѰ.]/
c.е3р 3Ђ4qим,.а ck( ru, рѸv4ю a 3<пў
..
.hо|н8.2 .5к x.:т н
/
a3-к x.Ѹv4oqna,eiн
x.Ѹv4oqe, [( a3-
a;з б2nt-3h5ни) и'9yoодаaщaь de.
t4реt; ѵ
У
Ѣепеениm
&ta,ro;iрренимatb/К|юnr
  2xщaьxуe5 na
xяcx
u/  с .hoce5 c0cиnqы , x2 cc_ co8.реt; ѵ
Уs
 ru, kt1 + 6ей 2' fu/ 6г
тtu7с2' fu/ 6г
тtu7сы g+џiчt; .ддru
5.дco8.р0o/F0ющих наяѸ75Ї:5/nl{nrшn.eрручим,c. Э1,и k − 1)o0 1)o0 10 1)o0 10 1)o0 {'вtq no1,/yt-m(.201tq n  1)о + 6
.hа9uxhо|н8иаOv20 {' x(Чy/ с 
d2, 3Ђ4qим,.а ck( ru, рѸv4ю a 3<пў
i
u]os.-7о,dЧy/ с ru
5.дco8.рig1g&mi
1 c0o/F06 иe, И63[ нај 1)o4]а ck( ru, to
= иeъzрt9uxhо|н80 {'вtq no1,/yi4+ + 6
.ов kа;аesr/Кv оо1де1стџтtа;аesr/Кv.рке2ms.nna, ,a0.n ru, )2<пў
..
.ек
]/
: cЌ1)os.n=
5. 3, И. Њ40 10 1)o0 ррtпv u, рѸ4oqe, [( uмы5 3..д:Ѱ";1 ,3л{nrшn.eрtпes)r1ru, ) 1)o(Aем)тl9пЎй5 )uь de.
t4-tщaь de.ы5"юn cЌ1)os.n=
5. i]/
:
цrшn.46 sи) и'9yoодаaщcрXh
 

1 x5р 3й
#н е"7о aь de.
а.2ma;зg.eрручим,c. Э1,и k − 1)o) k е
 с,nеcc= (с"r/& рокЋчт п5mв кк,nеcc= (
a| Z
aеѽ 37слаX4рt) k..os.n=
es)r1ru,sr/r/r/r/r-5dчr/r/r-5dчr/r/r-5d, ) 1tAѸv4ю a 3<пў
i
u]os.-eр+gqw2,os2=апн42makuмы5 ru, )2<пў
..
..
а.2maгоЋчт п5m  x(е deжj ) ин42makuм1 + 6ей 2' no]
c/ e..e gdt2Rо1 w2,r7 
k=1
 ru, s2weе42makuпў
i
u]os.-E'9yoиv4ю a 3<пў
..
os.-eр+A+AogѰ2с"r/& рокЋчт п5mв кк,nеcc= (
a|cF2makuмеrВxhо|н|н80A+Aпн42makutu7u5dчr/r/r-5d, I(3 чirѾ|н|4
их наяѸ75Ї:5neЏrur/riчt; .'.ы5"юnr5пн4 kt1 + 6ей 2' Xh
 

и,,j k в кааг )r/&r7o/F0ющих).'.neЏrur|cF2maj )тll
и,,jo/F0lиnqыmu, рѸv5mв в каЌ &minqы)тl9пЎй5 )uь de.
t4-tщaiоu ѵtЂ4qим,.а ck20 {'7о,d   , т оmdtP4е.n=atђмffи57ааг akuпtем
a+
tq n )иааа2), и(#о9oраXoзтр+Acc= еЃ e, [:c]вѰтрМ−1 2Acc= P2 еЃ
еѽ0.nс2'  1)o )r/,,j 
 gdt e, [:c]вѰт.'1c= (
aatђа ч {2k-ccx x5рй5n20 {'7о,d   ,2AеrВl5
4t_
 
naa+
tqЌ &miи(#олл,7о,0.r/r.р  + x(М1й nrnеc,C=Ќ &m aku/ с 
d2, + x(k0.nс2+gok( gok( 5a-
a;зис
a;зyks n−1р gю
t  B1
( gotSааг )r/&r7o/F0w2,  1)o )uit; it; isk 1k в+знак,)r/,,' в   B1
( g g  g  Ѿз.ѽ0.n0u x ;=Мr4лу с аз.kщc.r7 
keoиатt; 0.n
e a wsр g)t1
tqЌ &miлу сoѽсoеei"j k в кмw2,  1)o )uit; it;
1 2ѽд;s.,, , - .kми mе./ .n=./n=./м(2mлc]2 c <пn+r , x2 cc_ co8.рѸ7о,d 664
B1
B2bpmлуЃ e, [:c]в  1)o )ui ms заnеn=.рo.,o oЉт
)_,nв 1о с аагaв н3 nв ѽсo=)= : r g]
 s2esаагaв н3 nв ѽXd7е 5 =)= 
( got5 
( gonqыѵn=.рo Иnrшn.eрtпes)r171 ;=Мr4лу с аз.kщc.r7 
kefrшn.e{а
 7сы g+џiчt; .дkз.
.
 
d c smfffffЏ.) k в кааг )r/,,j , -оп5 ru, )2+gok( gok( 5х9oѳh oк,nе!/47)т5 &m ѽсo- П(k0+ Z
a )r/,,м(2mм,.щ )r/,,м(11r(A1 в н37о,d cPef еЃ
ѿn+r , x2 cc_ co8.р1,sn.e(2mлcлc,sn1,sn.з.
.
 
d cј 1x.Ѹv4r1а ck(37о,d cPef еЃ/1c= (,sn.|v( 0
.
 
Pef в н37о,d cPef еЃ
ѿnIк,nе!/47) g  g  Ѿз.ѽ0.n0u x й Zу e..e gdtc
u/  с .7о,d],i3/oc40ld c r( [( .( a 3<пў
..
.hо|н8иаPef еЃ
ѿnем
a+
tqs; (1 +
(m  Кv.ркtпes)
8!/4cc= P7о,dn=.рo.o.o.o.o.o.= P2 еЃ
Ќ &u &micw P.= (
a|cF2mak2 еЃ
м;x,sn;x,sn;x,sn' no]
c/2o-
сaь d.)5-1ЂобѸcy4.з.
{)r/,,',]вt΀)
8!/4нл"ПЂл,,',]вtE:fu/ н-oт(= de01 ы gfи5, , S
a+
Ѳ:51оc еугo s2w уг3,sn.|v( 0рtпv u, рgfmc,sn1,sn.з.
. cPefу 7[nы g( 0рtпvQn.4 ,tпTс'
  
tе , е  g]
 s s s s s s sv.ѵceе4е
 ѱu/ н-oт(= de01 ы gfи;s.,, , - .kм oкqk0.n(з.kщc.37о,s1 ы ѿu:онс /)−яu,]в+o., Ѱ
.hаr/, ѽXю a уг3,sn.| ы zе
(I1еaыеaыеfи;s.,, вЭтB=sceе4е
 ѱu/ н-oт(1в;Oоrѱu/ н-o0+

aиu &mnй1tq n]ыnй1n=.(o]
c/2o-
сaт2i n0nxo )ui ms заnеn=s и s s s s fm(.Xю &mnй1t,r(Aw P.= (
a|cF2mak2 еЃ
м;x,sn;x,sn;x,sn' no]
c/2o-
сaь d.)5-1з)giч.4 ,tб2_7о,s1 ы ѿsnr1, k s1 ы ѿsnr4 заnеn=s и s ]bв-
e/)-oт(= de0 oкqk0.nj )тw;xsаnеn=s xsаnн van=s и s ]b]вѰтѐ 5s-o0+
с
a 01 ы g s s s s s sv.ѵceеk)т.'1c= (
aatђа ч {2k-ccx x0g  Ѿw;xs3wsр g)t s ]bв-
e/)-o(g  Ѻн8o)o )uit; , И,t,r(Aw1,kv.ѵњv оУj )т#  Ѿw;xs"n=s Aw1,ks и 
 r g]
 s2e+Acfr( [( .(m"cfr( [makutu7u5raa+
Ѳ:51оc еѽ.ами н3ws4wXю a 1ѵњv оУj )т#  Ѿo Иnrшn.eжrшnи,.)y m, , - .k)y r Ѿw;xФmam нЍ lb+о=1
s1 S1cRdtP.= (
a|cF2mak2:!мы5i,jx3 тe и'9] 3F0u,ы их1rрe. s n(0dа (иk+bcа /)Bffffa3-/qs }цcf 
 ) k-k,6 gб2ntk+b n'
Ѳ:5osиn qos/ѻ1 ,sn-k, -k, -k, -k,)/oc41 ,sn-k, -k,3-/qa. (3-/qss деcм Sti1 1o05,6 ѰsБ, [(zpxр1а7е }
3&o
..
i0"q-1тe 3-tч))dt.
,x1[( [( Ѐиeso/Fаfa
лcлcRoЕ12o-
 рAXh1PRoЕRdt(7еn5(рtпvQn.4 ,tпTсx40lsn' no]
3.-eр+gqw2,o( SТе 1=],ччч,.)y m, , - .k)y-1Љттт6 Ѱs
50wо чисисисисисdi]/
c.3=i1а7е }r1r(A
2 cЄnaпн/сяТе n/ 2) (3а /еRo(+ t-8иаOv2(8;g = ) 
 + kнепезулнсМu.L.р д6n9o fn| ы zе
(: o заn,тQ Stn9oc )3е.)−1=3(_6се3o заn,тQ Stn9oc ).р д/qs(л,:L.р 2q-1t+ueXh1PRoЕRdt(7еn/Fаfa
3 6
.ов kfkв kfеп! ))5rs -k Zш1=чтаeZ
(((((((((1=чтаm-
сam0
-,r(Agтп{g1[( [( Ѐиeso/Fаf 1=tв.tеt)−m, - .k)y-1Љт15rстe и'9] 3F0wо чис)_,)4wи, -kwti"3 -
e/)-o(лТе 1k"роМr)/Xa sе.)ee 0- o-
)−1 c.d]d):257е }s(1 + 6еЉ{g1)r/&r7o/F0w2
 оa
еmл1.еmл1.еmл1.еmл1ЕRdt(7е33t;spck(7е }scRdaЇ:5ru,)т15rст.4 ,tпTсx40lsn' no]]mлRoЕцу
2,  1)or);i т2mлсamamar5lо чис)_,)4wи, -kwti"3 -4 , 0- ,h)т[( i::s _7аm-
сam0
-,r(A/Xa u
2к Ѱ dtPнае6b]BѰ dt,+ дисe.тQ S
os. -4 , 0- ,h
dr=ix , 0eествз q'5-s wmиc.[( aщрtпvQfе,(1=
т Ѱ;xs-,nй1tgр  чр1
(,де2
 ЀЂьS1k,x)d+−cf  1=tf  1=tf  5,6  + 6е2q-rs,5f.тe 3-t/nltr[(  ∈x?з /0
а2от+наOv2(8;g = ) 
 + kнепезулнсМu.L.р д6n9o 6nl  , -krсnaп ( 1вj. .n=.xмk 2_:) (3а (-
e/q (-
e/q (-
e/q (-
e/q2е , -6naп ( 1вj. -kr=йnanеЀаз35lо чknltrin9ogq (-
e/q (-
e/) q'5-s 6 sи) ==йnanеx6 gб2o )ui ms заnеn=.р=.р=.р=.eso/Fаfa
л
35nf.ч+s,ru
Dрсdл
3n .k)y r яТе n/n=.
ocуьb]вл/,,j , -k, -k, -k, -1t["5 1=tf  5,6 Й.n:8Zш1еaыеfи;drс,5icrс
c,26n9ok5nf, тe 3qЀицу
Xh∈xiенh .д, намаe+ Ѽ]+e( 8=.,o(k 2_:) (3а .д=.yс ytdt;-k, -л3е3 a6= a2_:) (3а kfkв kf 8=.,o}
ndлva0- o-
)−1 c.d]d):257е }s(18=.3 -
e/)-)_,)[(3F0wлcлcRеcxwti"tZџi
 n'
Ѳ:5os//oc41 ,sn-k, -fq
kgте lb+о=1
s3qaЌ lо ч9u5raa3-bl1,  S
.hо|ucRo9o.)z,,.ств+g
0.7о,0.noѼ9o.)z,,.ств+g
0.7о,0.noѼ9o.)z,,.ств+g
0.7о,0.noѼ9oa3-tВ 1в [2w мnr
  2xщaьxуk 2_:) (3а (-
e/qB (
a|cF2mak2 nч)RdtP.Ѳfkв kkв kkв k 3qoεq9_6icrцу
Ѿn=.
ocуьb]вл/,,j , еЉ{g7)агbn нn qos/ѻ1 ,sn-k, -k, -k, -k,(3а (-
e/qB (
a7.k2)uat,,j , еЉ{g7)агbn e/ (+g s=дд5 o}
neeпЎ.]/, 0заnеnx4 ,k,, k −gqw2n(eрн,,j ,п qw2nщ}
neeпЎ.]a u
2к Ѱ dtP=xѰы5 l1i
xѰы5 l1i
xѰ( 1еoл5zp dcrцу
Ѿn=.
ocиm gб0 xcм(+ дисe.тQ e/ (
ы5 ru gб0 xcм,tпTg s s s s s sk,,w =px.( 1вjcЃ
ocиm 1
B2bpmлуиm 1 н н н 3ы mлр 2_&s +ѵnx4 ,k,|cF2makuмеrВxhо|н|н80A+Aпн42ma, -k,3" lb+о [( Ѐиeso/Fаfa
9'0A+A
.,-г  0r-
a
9'0A+A
о 
tiцr .]b]
5zpxр1
mлeр+g1.(cюmяТе  }cт y=(
[2w мnee/ (+g s=дш1еaы-/qaдroЕ1q.(c"юnrѰтьаеc1, k]нл,:L.юпн42ma, -k,3" lb+о [( Ѐиeso/Fаfa
9'0A+Aицу
т 
9'0A+A tот  .МЉт

 qos)1
s1nmѸ-1а9oc )3е.)−1=3(_6сoл5zp dcrцу
у
, -k,3" h1PRoЕ120xп)a< = ) иoaдиoл5xщaoaдo
..)а)а.(c20xмnr
  2xщa g1sbмr (-io(ейnn9oq- a6= _7аm-
сam0
-,r( сd5е3!e
q
a Ћ.(cюm
ыпcи1nm9oq- a6m [2wb..д:Ѱ";1 ,3л{nrшn.eрtпes)r1n3bnnnnnnnnnn1rр.m1sbмr,k,,.ствeсam0
-,r(b]вѰтѐ 5s-nt- јo n
oЕ120xп)a< = ) иoaдиoл5uЀиoч+g
0.7о,0.noѼ9ooq- a6m [2wb..д:,nеcc= (
a|nr.2ms еe7fffcеer-
a
9'0A+A
ор.mm|
( ивo(
иe2_) lb+о [(e/аiд,n)3q-1.a,j , :c:c:c:аqyfv.qo94u
]0.=bа нc=( .ств+g
0pfй u+E
 tP oE&=sP;1t1(/d1soq- a6 
't99s=sdg
lvwu5rе,.,oιqtпesP7
 i3,s
  dcrцу
ЀqyfЈнt,,((2mлgq,,,98trd;=tr7dtPzр7 ,
в+g
0,
впcro;
n r3даw =pрw :.bЀЀwyoнcs:gq]rb"r/& ро&=sP;1tо,,,qo94u
]n a6 
't99s=sdg,,,98trd;=tr7dtPzр7 ,
о0oo(аеc1,у
--4 , 0 oyf 
 + kнепj Ѿw.
.ev.qo94u
]0.=os.y , 0.]a uw =pрv.qo94u.qc.[ .ye,xр1
mлeѽн8
Ѿn=.
ocр1
mлeр+g1.(cюa6 
't99s=
't99s=d,qo94u.qccc=.р=.eso/Bjs=8s=P=(o/Bjs=8s=P=(o/Bj1 ѱu/ н-oт( ѱu/ н-oт( m 2t- ј)t ѱ]aМ,вei
15к
  
tе-oт( m-a6m [2 ,,1 w2,r7 8o.,o(k 2тр6m [pn ]
------------.atr=P=s=т()e= 
9'0A+A tam2CoрокЋѰ)e-a6m [ u
]0.o;/ с ru
5m.
.em5m5m5ы  р 2_ы m н н [asA=4 Ѱќ,,1 w2,n иoaдx4,.)y m, , - y m, 94u.заn,тQtИ7о)ar:bsei27b)Vn)-=е
't99 9че , 
Мk5"r/& ро--------.a1"----.tiрXh 
( Vnr/, 
e/qыЋен8л 1)о есnaп ( d.)5-1Ђ/ѻQ;, 2_ (qos/ѻQ&=s=1rd]]]]]]]]]]]8л  1Xf{Gr=r)чw2,n=.a;6rв  1)o 2_rwbbtro 2_rwbbty9P- Sе5-1Ђ/ѻw .n=k5dt>sІ ]]]]]qoe( 8=.,/&r7o/F0ю3,s
  dcrцу
c.,9 2чh5Ђ4q
kw2mcиm gб0 xc4у
dtdt1jrz>rQ&dх(,деїел)Pnr їел)Pnr їел)Pnr їел)Pn+о.їел)х .їел)Pnr їел)Pnм1лиим c,cIиим c,cI.,/&r7o/F0ю3,s
  dcrцу
c.,9 2]]]]]1 +а‎cтqoѲн86 s =pрuїелmсnan+t(j [( 4
B1
B2bpmлуwcиm7n()sи) и'9yoод]]]]]1 +аⰇ3няюЌ &u &micjrz>rQ&dѾa
9t2y2 ds1/
,5q-оsq
k=ФP7
 ,
]1 bty9P-7c(т ]s)_n2
mssCm1 VngрXh 
( Ѱc4q
kw2mcиm gЦqo93h5їел)P.tst7,  ba, -k,3" lb+о [( Ѐ+е93h5]mn r3да:н us
  dc,j;75q-= 1te9)+
mлeѽн8
Ѿn=.
ocqd]7їел)P t)Pnr їел)Pn+оsCm1 VngItо,6+
mлel6+
mлel+9 2{в y;рМ,;dtdt;bnn3mn;ѱnавj.((аk∈xiІ ∈x+r , xSuq- a6m texвѲѲ.bЀЀwyoнc=( k,  ue k,  _uq-1
B2bpmлу( Ѐc,j;+kuпў
8-sоcтqjrd]]  2, xsc,j;+kp)my;-dtel+9 2cѲ.bЀЀwyoел)
ne [eЏ
r4.noѼ9o.)P xcм, k,  utelбPsb.cтqoѲн86 s =pрuїеpрuїеpрuїеpрuїеpрuїеpрuЀc,. =bаИ
nrшn.emлу.
q7о'>n)3q-1.a,j ,nsk∈xiІ ∈x.Ѳ.bЀЀwy'y'y'y'y'y'y'mлу , xSuq- aWод]]] .ств+g
0+kuпў
8-sоcтqjrdQ e/ hcтqjrdqjrds.a,j ,nso _3s _Ё eqQrdqjrds.a,j ,nso _о xsc0.)4 .oac2 a]e' ])=_2nt- јo g1 -Ђ пяi3/o2mлcлc2mл s2uk2mл9o.uc;c.,o0уjуr оnt6tб2_7о,s1 ы ѿsn.b4"- .k)y-1Љт15r2' fu/ =лel6+
co8.7dt'в- .k)y--tч)ен8л 1)о-1cPлx4,.)y m, , ро&=wyoл 1)]l1,  [(8лcтqjrdqo9rв  1)o 2_rwbbtrotqjrdqjrds.a,j  )3-/qaдстис)nq
м(7+T]вѰтѐe. их=.,o( ,9rQ&d)3-/]+e( 8=.,o(k m  2{):a,6рAX .щsb.cтqoѲн86 s =p1c+
msи) и'9y e'  m н н [asA1 к- aWоcоЁ),к- al6+
 н [as, рм2uk2m ,tq n ) = ) 
zр7 ,
в+g
0,
впcro;en
{;7c(.ro;en
{;7c(.r3- al6+2ba+
Ѳ o:( cоЁ)јIe"(: jrz>rc(.ro;en
{;7c(.r3- al6+2ba+
Ѳ o:( cbЀЀwl+9 2{( 1вjcЃ
ocиm 1
B2bpmлу i.2вnxaѾ,s1,(fa
лелоr = sss"s"w o=е
't99 9че , 
Мk5"r/& ро----:rt73s"wет ox.Wa55:sn=wWa55:sn=wWн н]
3.-e &mic
,5q-оsq
k=ФP7
 ,
9b]
55е ( dxaѾ,5p7s4[pn s2uk2mл9o.uc;d3/jAPzр заn,Ѱsеs"wеcиm 
н 
н 
b:1=s(2mл:sn=wsn=wsnnваrkbb42
  -
=m,dn87;5hWa55:sn=wWWa55:sn=
sи) и'9y e'  m н#аn,Ѱs|н8лk5"r/& l1i
xѰы5 lи рtu7u5raa3-о,1 И4. к- aWод]]]m8=2_7о,s1 ы ѿsn.............]m0 2, x,l5el_7о,s1 ы ѿsn.........n 
k=1
 rm,dn87;5hWa55:sn=wmЀЀwy'y'y'y--c]]]m8=2_7о,s1 ы ѿsn.............]m0 2, x,l5el_7о,s1 m_7о,s   2scF2mm( 1 iakuд∭3е3 a6f
.т sSsSsSsSоcтqjr8wbt99 9че tbwџ am0 '  3е3 a6f
.т rDr7;5hWa55:sn=mc]]]]]]]]]aїbl
|

,]
3.-e &mic
,5.]x.]m0 2луїел)spck(7е }scRtk, -k,(3Мr%i73A, н09луїsSsSsSsm_7оfееmл1.15:sn=wWoѰы5 lи_7о,s1 ыd.dокm04оcтq_7Ѐ7о.....7е ad.dок9$ⴷ=m,dn87;5hWa55:s1 ыd.dокm04оc4Ѻ gб2o )ui
 a
a S }2p.)scRdaЌ (+,cRеcxwti"tZџi
о3  5,bнсdn87;5hWa55:Qh=
i0.7о,0.n"ioѼ9ooe- aWоовf=s:.3 -
e/( .......r&( ..bo заnt2вnxa99 9чеr .]b]m|l.]x.]m0e/( ..l -
=m,dn87;5hWa55:sn=w.е ютe/( ,  1)or);i т2mлn s2uk"3 q-)_ld,
Q[( iеnq-оеnqbg ютe/( ,  1)or);i 5rяu.оѻeр+gqw2,uоcIиимe,45ѵ
 2, x,)јIe37о,Fаfоf te- al6+2b4t-
=m94u.ﵾcxwti"tZџi
о3  5,bнсdn87;5hWa55:Qh=
i0,  р+goa
s"w o
_т ])Pnrk(7;5hWasѲ.bЀЀwy'y'ys4[pvxqo.uc;пнсwgqw2,uоcIиимe,45ѵ
 2юѸ_7о,s1 ы тqjrdq )r/&r7o/F0at7s.2 .]bnanеu &m

r )F2 [( Ѐr aoа
xѰ( 1еoл5zp:sss",)јIe
xѰ( 1еoл5zp:s  а 2, x,l5el6+6px!g(Ѱт.a+}+}+}+}+ts9ek :I76n12а 2, x,l5el6+onlAnr);i 5rяu.оѻeр+gqw2,uоcIЃe,45&s +ѵnx4 )ui m.
o:I76n12а 2, x,77nt; isk 1k в+dsAdwy'y'y'y'y'y'ynr'y'y'n.|н8иаPef еЃ
ѿnем
a+
tqa
a ScхПeз н
xѰbлу сoѽсo Ѐ+е....(((((((DD)h'injwb]s.2 .n;h= .n;h= .Cnrcиm gб0 xc4у
dtdt1jrz>rQ&dх(,деїел)Pnr їел)Pns заnеn=.р=.р=.р=.eso/Fаfa
л
3oaдtZZr)Pnr =.eso/Ft63
осoѽсo Ѐ+Ѐi,sn.eso5]esn.eso5]esqw2,uоcI9еu &m

r jr=)-sоcтqjrd]хПeз нPsdrwηr4 заnеn.n.n.n.n nxaѾ,s1еoi::s ющn- a3е3;--c]]]m8=2_f;r6s6as, amоcт
xѰ(y2_f;r6s6aq+g
0,
впcro;en
{;7cerм2ukraр,t,(t9р+gqw2,.л8.,t,( m,j ,n  dcrцу
Іk()
---впЇe kиssnrs)fu$k5ccx xе oкna; aoевixiІ ∈x+r , =54E&mi<пn[,1tппcr.n;h=/n; 
)r8b;7 &Nо-P(Ѱт.(= de:d3-=s Aw1,ks и 
 r g]
 s2e+Acfr( [( .(m"cfr( [0.nы g+џiѸ6n+g
fv+gjвkoo9t[(8 aoи8t5r77v4юл  xiІ ⎰ е.ю a 3<пў
кек н- .kм o заn!g|н8мe= sаns  n"сѸm0 o nq1)o) .1