Числа Каталана

Работая над статьями об решении алгебраических уравнений я решил, что необходимо написать отдельную статью об числах Каталана.

Для написания этщй статьи я воспользовался статьёй из викиконспектов

https://neerc.ifmo.ru/wiki/index.php?title=Числа_Каталана

Числа Каталана это последовательность чисел, названная в честь бельгийского математика Эжена Шарля Каталана. В онлайн энциклопедии OEIS числится под номером A000108.

Реккурентная формула для чисел Каталана:

При этом второе определение излишне, т.к

1. Пути в решётке

Есть множество определений для чисел Каталана. Я буду использовать пути Дика. Но для начала рассмотрим просто пути в решётке, которые состоят из шагов вверх (вектор (0,1)) и вправо (вектор (1,0)). Все пути начинаются в точке(0,0) и заканчиваются в точке (a,b).

Рис1, пример пути из т(0,0) в т.(10,8)

Каждый путь содержит a горизонтальных b вертикальных векторов. Таким образом всего в каждом пути содержится (a+b) векторов. Для нахождения количества различных путей из точки(0,0) в точку (a,b) необходимо выбрать позиции для a горизонтальных (или b горизонтальных) векеторов из (a+b) возможных позиций. Это выполняется я помощью математического сочетания и в силу симметрии сочетания получаем.

Для нахождения количества различных путей из точки(a,b) в точку (c,d) при условии a<c и b<d можно рассматривать как перемещение из точкиa,(0,0) в точку (c-a,d-b)

2. пути Дика

Пути Дика - это пути на клетчатой бумаге, которые начинаются в точке (0,0) и заканчиваются в точке (n,n);

Пути Дика состоят из шагов вверх (вектор (0,1)) и вправо (вектор (1,0)) и не поднимаются выше диагонали соединяющей т.(0,0) и т.(n,n)

Рис1. Пример пути Дика для n=10

Количество различных путей Дика в квадрате (n*n) соответствует числу Каталана. Для проверки этого утверждения разобьём всё множество путей на группы по первому касанию диагонали.

Рис2. Первое касание в точке m.

Точка m - первое касание пути диагонали O-n. В данном случае m - это количество полных квадратиков в линии 0-m. Все пути данной группы "m" разобьются на две части: (0-m) и (m-n).

Путь из точки m в точку n - это путь Дика в квадрате (n-m)* (n-m), и всего путей из точки m в точку n, ровно:

Но путь из точки 0 в точку m - это не путь Дика, т.к. все пути на этом участке не касаются диагонали О-n. Вектор Оа и вектор Bm являются общими для всех путей из т.О в т.m. Таким образом количество путей Дика из т.О в т.m равняется количеству путей из т.А в т.В и равно:

Если теперь объединить все группы по m от 1 до n, то получим число Каталана.

Формула отличается от первоначальной, но замена переменной k = m-1 получается исходная формула:

Мне больше нравится первая формула, с переменной m,

3. Неправильные пути.

Неправильными путями называются пути, которые пересекают диагональ 0-n. Не касаются, а пересекают диагональ, переходя с одной стороны диагонали на другую.

Рис 3. Пример неправильного пути

Для того, чтобы вычислить число путей из т.0 в т.А, сместим весь путь на одну клетку вниз.

Правильный путь Дика не имеет общих точек с диагональю 0-n. Но неправильный путь всегда имеет хотя бы одну общую точку. Возьмём первую точку m. Заменим путь от т.В(0,-1) до точки m симметричным относительно диагонали 0-A(n,n).

Мы получим путь длины 2n, идущий из точки B(−1,0) в точку C(n,n−1). Такой путь обязательно пересекает прямую 0-A(n,n). Обратно, пусть нам дан путь длины 2n из точки B(−1,0) в точку C(n,n−1) и пусть m — первая точка этого пути, лежащая на прямой 0-A. Заменив участок пути от точки B(−1,0) до точки m на симметричный относительно прямой 0-A(n,n), мы получим неправильный путь из точки (0,−1) в точку C(n,n−1). Следовательно, неправильных путей из точки B(0,−1) в точку C(n,n−1) столько же, сколько путей из точки B(−1,0) в точку C(n,n−1). Такой путь длины 2n содержит n+1 горизонтальных и n−1 вертикальных участков. Поэтому, количество неправильных путей равно

Но количество правильных путей Дика равно общему количеству путей в квадрате nxn за вычетом неправильных путей.

4. Реккурентная формула для сочетания.

По аналогии с числами Каталана попробуем вывести реккурентную формулу для сочетания. В квадрате nxn разделим все пути по принципу первого касания диагонали.

Т.к. мы рассматриваем общее количество путей в квадрате nxn то количество путей от точки 0 до точки m будет равно удвоенному числу Каталана, т.к. существует такое же количество путей зеркальных относительно диагонали 0-А.

Количество путей из точки m в точку А равно количеству путей в квадрате (n-m)*(n-m)

Всего количество путей в группе m будет:

Но числа Каталана можно выразить через сочетание

Если проссумировать все группы с m =1 до m =n, то получим полное количество путей в квадрате nxn:

или в перерасчёте на привычное k =m-1

5. Расширение чисел Каталана.

При определении чисел Каталана всегда определяют, что нулевой и первый член последовательности равны:

Как уже упоминалось в начале статьи второе определение излишне.

Возьмём ряд чисел a(n), соответствующие условию:

Для вычисления всех членов последовательности представим нулевой член в виде произведения:

Теперь вычислим первый член последовательности:

Если продолжить:

Если теперь поменяем условия:

Для вычисления всех членов последовательности представим первый член в виде произведения:

Далее: