Итак, задача номер 5. Давайте докажем рекуррентное соотношение чисел Каталана. Ну напишем: мы хотим его найти. Найдите [шорох] рекуррентное соотношение для чисел Каталана. [шорох] Ну давайте ещё раз напомним формальное определение, значит, мы берём скобочные последовательности для 2n, но не простые, а правильные скобочные последовательности. Значит, у нас есть 2n скобок. [шорох] И мы хотим рассматривать какие последовательности? Давайте как-нибудь формализуем. Что значит правильная скобочная последовательность? [шорох] [шорох] Ну, скажем, например, что мы хотим, чтобы для каждой открывающейся скобки была следующая закрывающаяся скобка после неё. Или, говоря по-другому, если мы рассмотрим произвольное место, то до этого места количество открывающихся скобок будет больше, чем закрывающихся. [шорох] Ну, точнее, ⩾. И это верно для любого места этой после... этой последовательности скобок. Ну ещё по-другому можно тогда это переписать так, что мы можем записать под каждой последовательностью последовательность чисел. Так называемый скобочный итог. А именно: когда скобочка открывается, мы прибавляем 1, а, когда скобочка закрывается, мы вычитаем 1. Ну и вот тогда можно написать такую последовательность, сейчас я напишу для [вздох] этой последовательности. И мы хотим, чтобы эта последовательность была всё время положительная и в конце заканчивалась нулём. То, что в конце заканчивается 0, это значит, что открывающихся скобок и закрывающихся одинаковое количество. А то, что последовательность всё время, ну, точнее, не отрицательная, это означает, что у нас никогда количество открывающихся скобок не меньше количества закрывающихся скобок. Ну давайте рассмотрим произвольную правильную скобочную последовательность T 2n. Мы хотим количество таких правильных скобочных последовательностей T 2n выразить – так, давайте я напишу, что это количество. Количество правильных скобочных последовательностей, ну или, собственно, это то же самое, что числа Каталана, [шорох] Вот давайте мы выразим это T 2n через T с меньшими индексами. То есть как мы это будем делать? Ну давайте мы возьмём открывающуюся скобку первую и найдём соответствующую ей закрывающуюся скобку. Ну что это значит? На самом деле, если говорить о языке последовательности чисел, то мы просто смотрим эту скобку, после которой будет первая 0. Это означает, что, то есть у нас здесь 1, а здесь получился первый 0. Это означает, что внутри находится некоторая правильная скобочная последовательность, потому что внутри неё будут, естественно, какие-то числа, причём они будут всё время положительными, дальше... дальше... даже ⩾1. Это значит, что вот эта последовательность из 2k скобок, она будет правильной. Ну тут, естественно, чётное количество скобок, потому что для каждой, открывающейся внутри, должна быть закрывающаяся внутри, иначе будет противоречие. Ну и снаружи у нас будет 2n−2k−2 скобки. Они будут тоже образовывать правильную скобочную последовательность. [шорох] Ну опять же, потому что тут, тут как бы все скобки отсутствуют сначала и тут снова будут последовательность, ну, если считать скобочный итог, то он всё время будет неотрицательным и удовлетворять ровно этому же свойству. Ну вот, значит, количество таких скобок у нас будет T с индексом 2k, таких скобок у нас будет T с индексом 2n−2k-2. Вот. Тут в литературе бывают разные обозначения. Кто-то иногда пишет T 2n, а иногда пишет Tn. Я-таки даже не знаю, как лучше. Давайте я тут напишу T с чертой n, чтобы было похоже на то, что было на лекциях, потому что я привык с чертами писать. Ну вот, значит, какие у нас получаются возможности. Значит, где у нас может закрываться первая скобка? Первая скобка может закрываться сразу же. Первая закрывающаяся скобка, соответствующая открывающейся, она может закрываться сразу же после неё, а может закрываться в самом конце. Значит, k у нас меняется от 0 до максимального количества, то есть до n−1. Поэтому получаем вот такое соотношение. T'n=∑ по k от 0 до n−1, значит, и мы суммируем T' k-тое умножить на T' n−k−1. Вот это можно здесь расписать, то есть это будет T0 умножить на Tn−1+T1 умножить на Tn−2 и так далее. И в конце будет стоять Tn−1 умножить на T0. Ну вот, значит, здесь штрихи нужно поставить. Ну вот получили, доказали рекуррентное соотношение чисел Каталана. Вот мы его нашли дальше на лекциях мы им воспользовались и нашли через него формулу для чисел Каталана. Задача решена.