Шестая задача. В этой задаче требуется найти количество триангуляций выпуклого n-угольника. [ШУМ] [ШУМ] [ШУМ] Ну, триангуляция — это такое разбиение треугольника диагоналями на маленькие треугольники, такие, что диагонали пересекаются только в вершинах этого n-угольника. Ну мы сейчас найдем рекуррентное соотношение для n, попытаемся его вывести, и из этого поймем, как, собственно, n устроено. Ну давайте сначала поймем, что у нас A3 — это количество триангуляций просто обычного треугольника. то есть A3 = 1. Для A4: это четырехугольник, но у него есть две триангуляции. Мы можем разделить его диагоналями вот так, а можем разделить диагоналями вот так. Значит, ну давайте напишу A3 = 1, A4 = 2. Так, начальные члены у нас какие-то есть. Давайте поймем, какое у нас рекуррентное соотношение. Возьмем какой-нибудь большой выпуклый n-угольник. [ШУМ] Выделим какую-нибудь его сторону, зафиксируем ее. Заметим, что данная сторона принадлежит ровно одному треугольнику нашей триангуляции. У нас треугольники могут иметь общую сторону только в качестве диагонали. Ну и какая может быть вершина у этого треугольника? Вершина у этого треугольника, которая содержит эту сторону в триангуляции, это может быть любая из вершин, из оставшихся вершин. То есть если у нас всего вершин n, значит, мы пишем рекуррентное соотношений для An, значит у нас есть любая из n минус двух вершин нам подойдет. Если мы выберем, ну давайте, нарисуем наш треугольничек, допустим что... Значит, давайте их занумеруем. Значит, если мы попали в вершину номер, с номером k, то какие у нас многоугольники остались слева и справа? Значит, с одной стороны у нас остался многоугольник, содержащий... Значит, если у нас здесь k, то у нас содержится вершин k + 1. [ШУМ] И понятно, что количество разбиений такого, значит, (k + 1)-угольника их ровно k + 1. А здесь у нас вершины с k по n + 1. Это значит, что там количество вершин будет каким? Будет ровно (n − 1 − k + 1), то есть (n − k). [ШУМ] Так, значит таким образом мы получаем следующее рекуррентное соотношение. Значит, у нас An будет равно сумме... Так, теперь давайте подумаем сумме от чего. Значит, мы суммируем по k, значит, мы должны просуммировать формально от 1 до n − 2 Ak + 1 на An − k. Так, ну здесь, смотрите, здесь у нас появилась некоторая логическая ошибка, потому что мы здесь использованы слагаемые при k = 1, это A2. То есть при k = 1 у нас многоугольник вырождается в такой отрезочек. Ну давайте для определенности считать, что у нас A2 = 1, как мы обычно делаем для нулевого члена, сейчас поймем, что у нас все будет согласовано. То есть мы все равно, если у нас этот треугольник вырожден, то у нас просто мы вычитаем количество разбиений оставшегося (n − 1)-угольника, то есть, (n − 2)-угольника. Ну и вот, как раз у нас добавляется эта единица. Ну вот, таким образом мы получили вот такое рекуррентное соотношение. Теперь давайте поймем, что оно нам напоминает. Оно напоминает числа Каталана, потому что рекуррентное соотношение чисел Каталана устроено каким-то похожим образом. Я напомню, как оно устроено. Значит, у нас там Тn = сумма по k от 0 до −1 Тk умножить на Тn − 1 − k. Вот давайте подумаем. Значит, тут видно, что в принципе произведения похожи, но только здесь в сумме получается n + 1, а здесь получается в сумме n − 1. Мы заметим, что наши последовательности чисел Каталана, значит, давайте я здесь нарисую. Когда у нас T1 — это когда у нас две скобочные последовательности, у нас их ровно одна скобочная последовательность, один вариант правильной скобочной последовательности. Когда у нас есть T2, то у нас всего 4 символа, и у нас всего есть какие правильные скобочные последовательности? Вот такая и вот такая. То есть их всего 2. Итак, у нас T1 = 1, T2 = 2, и глядя на это, смотрите, у нас A3 = T1, A4 = T2 рекуррентное соотношение похожее. Ну давайте мы предположим, что у нас An = Tn − 2, Да, A3 = T1, A4 = T2, и проверим, что наши рекуррентные совпадают, и тогда мы докажем равенство. Ну давайте, я перейду на соседнюю доску, чтобы доказать рекуррентное соотношение. Значит, пусть мы доказываем по индукции, значит, пусть мы доказали, что An = Tn − 2 для всех чисел, меньших чем n, доказываем для n. Значит, пишем An это равно сумма по k от 1 до n − 2, Ak + 1 умножить на An − k. Подставляем вместо, значит, для этих чисел [ШУМ] индукцию мы уже доказали эту формулу, что An не равно Tn − 2, давайте ее подставим, получаем: сумма от 1 до n − 2 T с индексом k − 1 умножить на T с индексом n − k − 2. Так, отлично. Ну давайте теперь мы преобразуем. Там у нас в рекуррентных соотношениях для чисел Каталана, у нас суммирование идет от 0, давайте мы просуммируем от 0. Значит, это будет сумма по k от 0 до n − 3, заменим k на k − 1. Ну давайте я запишу здесь k', чтоб оно у нас не путалось. Тогда у нас будет T с индексом k' умножить на Т с индексом n − k' − 3. Ну и смотрите, у нас получился ровно сотношение чисел Каталана. Мы суммируем по k от 0 до какого-то числа и берем произведение от T от k' на T на n, n − 3, на это число − k'. Ну значит, это будет просто равно T с индексом n − 2. Ну и значит, мы доказали, что An = Tn − 2. Ну, то есть понятно, что это все произошло потому, что у нас просто рекуррентные соотношения совпадают. Ну и таким образом, по индукции можно доказать, что An = Tn − 2, и значит, наша последовательность — это просто последовательность чисел Каталана со сдвигом. Ну, естественно, можно по формуле чисел Каталана ее легко найти. Задача решена.