Редактирование: Числа Каталана

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 13: Строка 13:
 
*количество способов расставить скобки в произведении <tex dpi = 120>n</tex> множителей
 
*количество способов расставить скобки в произведении <tex dpi = 120>n</tex> множителей
 
*количество способов заполнить лестницу ширины и высоты <tex dpi = 120>n</tex> прямоугольниками
 
*количество способов заполнить лестницу ширины и высоты <tex dpi = 120>n</tex> прямоугольниками
и так далее}}
+
и т.д.}}
  
Первые несколько чисел Каталана:  
+
Первые несколько чисел Каталана:
  
<tex dpi = 120> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \ldots </tex>
+
<tex dpi = 120> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... </tex>
  
 
==Формулы вычисления чисел Каталана==
 
==Формулы вычисления чисел Каталана==
  
 
===Рекуррентная формула===
 
===Рекуррентная формула===
<tex dpi = 150>C_n = \sum\limits_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>
+
<tex dpi = 150>C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>
 
====Доказательство====
 
====Доказательство====
 
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
 
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
  
Пусть <tex dpi = 120>X</tex> — произвольная правильная скобочная последовательность длины <tex dpi = 120>2n</tex>. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность <tex dpi = 120>X</tex> в виде: <tex dpi = 120>X = (A)B</tex>, где <tex dpi = 120>A</tex> и <tex dpi = 120>B</tex> — тоже правильные скобочные последовательности. Если длина последовательности <tex dpi = 120>A</tex> равна <tex dpi = 120>2k</tex>, то последовательность <tex dpi = 120>A</tex> можно составить <tex dpi = 120>C_k</tex> способами. Тогда длина последовательности <tex dpi = 120>B</tex> равна <tex dpi = 120>2(n - k - 1)</tex> и последовательность <tex dpi =120>B</tex> можно составить <tex dpi = 120>C_{n - k - 1}</tex> способами. Комбинация любого способа составить последовательность <tex dpi = 120>A</tex> с любым способом составить последовательность <tex dpi = 120>B</tex> даст новую последовательность <tex dpi = 120>X</tex>, а величина <tex dpi = 120>k</tex> может меняться от <tex dpi = 120>0</tex> до <tex dpi = 120>n - 1</tex>. Получили рекуррентное соотношение: <tex dpi = 120>C_n = C_0 C_{n-1} + C_1 C_{n-2} + \ldots + C_{n-1} C_0 </tex>. Так как <tex dpi = 120>C_0 = 1</tex>, то последовательность совпадает с числами Каталана.
+
Пусть <tex dpi = 120>X</tex> — произвольная правильная скобочная последовательность длины <tex dpi = 120>2n</tex>. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность <tex dpi = 120>X</tex> в виде: <tex dpi = 120>X = (A)B</tex>, где <tex dpi = 120>A</tex> и <tex dpi = 120>B</tex> — тоже правильные скобочные последовательности. Если длина последовательности <tex dpi = 120>A</tex> равна <tex dpi = 120>2k</tex>, то последовательность <tex dpi = 120>A</tex> можно составить <tex dpi = 120>C_k</tex> способами. Тогда длина последовательности <tex dpi = 120>B</tex> равна <tex dpi = 120>2(n - k - 1)</tex> и последовательность <tex dpi =120>B</tex> можно составить <tex dpi = 120>C_{n - k - 1}</tex> способами. Комбинация любого способа составить последовательность <tex dpi = 120>A</tex> с любым способом составить последовательность <tex dpi = 120>B</tex> даст новую последовательность <tex dpi = 120>X</tex>, а величина <tex dpi = 120>k</tex> может меняться от <tex dpi = 120>0</tex> до <tex dpi = 120>n - 1</tex>. Получили рекуррентное соотношение: <tex dpi = 120>C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdot \cdot \cdot + C_{n-1} C_0 </tex>. Так как <tex dpi = 120>C_0 = 1</tex>, то последовательность совпадает с числами Каталана.
  
 
===Аналитическая формула===
 
===Аналитическая формула===
  
<tex dpi = 150> C_n = \dfrac{1}{n+1} \dbinom {2n} {n} </tex>
+
<tex dpi = 150> C_n = \frac{1}{n+1} \binom {2n} {n} </tex>
 
====Доказательство====
 
====Доказательство====
  
Строка 38: Строка 38:
  
 
Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке
 
Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке
<tex dpi = 120> (0, -1) </tex>, заканчивается в точке <tex dpi = 120> (n, n-1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки <tex fpi = 120> (0, -1) </tex> в точку <tex dpi = 120> (n, n-1) </tex>. Длина такого пути равна <tex dpi = 120>2n</tex> и он содержит <tex dpi = 120>n</tex> вертикальных сегментов и <tex dpi = 120>n</tex> горизонтальных. Количество всех таких путей равно числу способов выбрать <tex dpi = 120>n</tex> вертикальных сегментов из общего числа <tex dpi = 120>2n</tex> сегментов, т.е. равно <tex dpi = 135> \dbinom {2n}{n} </tex>.
+
<tex dpi = 120> (0, -1) </tex>, заканчивается в точке <tex dpi = 120> (n, n-1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки <tex fpi = 120> (0, -1) </tex> в точку <tex dpi = 120> (n, n-1) </tex>. Длина такого пути равна <tex dpi = 120>2n</tex> и он содержит <tex dpi = 120>n</tex> вертикальных сегментов и <tex dpi = 120>n</tex> горизонтальных. Количество всех таких путей равно числу способов выбрать <tex dpi = 120>n</tex> вертикальных сегментов из общего числа <tex dpi = 120>2n</tex> сегментов, т.е. равно <tex dpi = 135> \binom {2n}{n} </tex>.
  
 
Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка <tex dpi = 120>A</tex>). Отрезок пути от точки <tex dpi = 120>(0, -1)</tex> до точки <tex dpi = 120>A</tex> заменим симметричным относительно прямой <tex dpi = 120>y = x</tex>. Мы получим путь длины <tex dpi = 120>2n</tex>, идущий из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> (Смотри рис.).
 
Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка <tex dpi = 120>A</tex>). Отрезок пути от точки <tex dpi = 120>(0, -1)</tex> до точки <tex dpi = 120>A</tex> заменим симметричным относительно прямой <tex dpi = 120>y = x</tex>. Мы получим путь длины <tex dpi = 120>2n</tex>, идущий из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> (Смотри рис.).
 
[[Файл:Каталан2.PNG|right]]
 
[[Файл:Каталан2.PNG|right]]
 
Такой путь обязательно пересекает прямую <tex dpi = 120> y = x </tex>. Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> и пусть <tex dpi = 120> A </tex> — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(-1, 0)</tex> до точки <tex dpi = 120>A</tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex>. Следовательно, неправильных путей из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex> столько же, сколько путей из точки <tex dpi = 120>(-1, 0)</tex> в
 
Такой путь обязательно пересекает прямую <tex dpi = 120> y = x </tex>. Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> и пусть <tex dpi = 120> A </tex> — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(-1, 0)</tex> до точки <tex dpi = 120>A</tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex>. Следовательно, неправильных путей из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex> столько же, сколько путей из точки <tex dpi = 120>(-1, 0)</tex> в
точку <tex dpi = 120>(n, n-1)</tex>. Такой путь длины содержит <tex dpi = 120>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \dbinom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно
+
точку <tex dpi = 120>(n, n-1)</tex>. Такой путь длины содержит <tex dpi = 120>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \binom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно
  
<tex> C_n = \dbinom {2n} {n} - \dbinom {2n} {n-1} = \dfrac{2n!}{n!n!} - \dfrac{2n!}{(n-1)!(n+1)!} = \dfrac{2n!}{n!} (\dfrac{1}{n!} - \dfrac{1}{(n-1)! (n+1)}) = \dfrac{2n!}{n!n!(n+1)} = \dfrac{1}{n+1} \dbinom {2n} {n} </tex>
+
<tex dpi = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{2n!}{n!n!} - \frac{2n!}{(n-1)!(n+1)!} = \frac{2n!}{n!} (\frac{1}{n!} - \frac{1}{(n-1)! (n+1)}) = \frac{2n!}{n!n!(n+1)} = \frac{1}{n+1} \binom {2n} {n} </tex>
  
 
==Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==
 
==Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==
Строка 56: Строка 56:
 
Пусть <tex dpi = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi = 120>(n + 2)</tex> — угольник на <tex dpi = 120>k</tex> — угольник и <tex dpi = 120>(n-k+3)</tex> — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex> — угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex> — угольника и <tex dpi = 120>(n-k+3)</tex> — угольника
 
Пусть <tex dpi = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi = 120>(n + 2)</tex> — угольник на <tex dpi = 120>k</tex> — угольник и <tex dpi = 120>(n-k+3)</tex> — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex> — угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex> — угольника и <tex dpi = 120>(n-k+3)</tex> — угольника
 
определяет триангуляцию исходного многоугольника. Поэтому
 
определяет триангуляцию исходного многоугольника. Поэтому
<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \ldots + t_n t_0 </tex>
+
<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \cdot \cdot \cdot + t_n t_0 </tex>
 
и поскольку <tex dpi = 120>t_0 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана.
 
и поскольку <tex dpi = 120>t_0 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана.
  
Строка 80: Строка 80:
  
 
==Подсчет чисел Каталана==
 
==Подсчет чисел Каталана==
Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(n)</tex> памяти и <tex dpi = 120>O(n^2)</tex> времени. За <tex dpi = 120>O(n)</tex> времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:
+
Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(n)</tex> памяти и <tex dpi = 120>O(n^2)</tex> времени. За <tex dpi = 120>O(n)</tex> времени их можно посчитать если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:
  
<tex dpi = 135> C_n = \dfrac{4n-2}{n+1} C_{n-1} </tex>.
+
<tex dpi = 135> C_n = \frac{4n-2}{n+1} C_{n-1} </tex>.
 
 
==Вычисление [[Производящая функция |производящей функции]] чисел Каталана==
 
 
 
{{Лемма
 
|id=lemma1.
 
|statement=<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \cdot \dbinom{2k}{k} </tex>
 
|proof=
 
<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{\dfrac{1}{2} \cdot (\dfrac{1}{2} - 1) \cdot (\dfrac{1}{2} - 2) \cdots (\dfrac{1}{2} - k + 1)}{k!} =
 
\dfrac{1 \cdot (1 - 2) \cdot (1 - 4) \cdots (1 - 2k + 2)}{2^k \cdot k!} = \dfrac{1 \cdot (-1) \cdot (-3) \cdots (-2k + 3)}{2^k \cdot k!}</tex>
 
 
 
<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 3 \cdot (2k - 3) \cdot (2k - 1)}{2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 2 \cdot 3 \cdots (2k - 3) \cdot (2k - 2) \cdot (2k - 1) \cdot 2k}{2 \cdot 4 \cdots (2k - 2) \cdot 2k \cdot 2^k \cdot k!}</tex>
 
 
 
<tex>= \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{(2 \cdot 1) \cdot (2 \cdot 2) \cdots (2 \cdot (2k - 1)) \cdot (2 \cdot k) \cdot 2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot (1 \cdot 2 \cdots (k - 1) \cdot k) \cdot 2^k\cdot k!} </tex>
 
 
 
<tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot k! \cdot 2^k\cdot k!} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 2^k \cdot 2^k} \cdot \dfrac{(2k)!}{k! \cdot k!}= \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \dbinom{2k}{k}</tex>
 
}}
 
 
 
{{Задача
 
|definition = Вычислить производящую функцию чисел Каталана
 
}}
 
 
 
Пусть мы имеем последовательность чисел Каталана <tex>(C_0, C_1, C_2, \ldots)</tex>.
 
 
 
Будем искать её производящую функцию в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^n</tex>
 
 
 
Как известно, рекуррентное соотношение для чисел Каталана имеет вид
 
 
 
<tex>
 
 
 
C_n=
 
\begin{cases}
 
1,&\text{если $n = 0$;}\\
 
\sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}
 
\end{cases}
 
 
 
</tex>
 
 
 
Домножаем <tex>C_n</tex> на <tex>z^n</tex>, получая
 
 
 
<tex>
 
 
 
z^n \cdot C_n=
 
\begin{cases}
 
z^0 = 1,&\text{если $n = 0$;}\\
 
z^n \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}
 
\end{cases}
 
 
 
</tex>
 
 
 
Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>, получаем:
 
 
 
<tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n z^n = C_0 z^0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} =
 
C_0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}</tex> (так как <tex>C_0 = 1</tex> по определению чисел Каталана).
 
 
 
Получили, что <tex>G(z) = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}~~~~~  \textbf{(1)}</tex>
 
 
 
Распишем произведение <tex>G(z) \cdot G(z)</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]].
 
 
 
<tex>G(z) \cdot G(z) = (\sum\limits_{n = 0}^{\infty} C_n z^n) \cdot (\sum\limits_{n = 0}^{\infty} C_n z^n) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k}</tex>
 
 
 
В последнем выражении выполним сдвиг индексации, положив <tex>n' = n + 1</tex>. Тогда имеем: <tex>n = n' - 1, n = 0 \Rightarrow n' = 1</tex>. Кроме того, <tex>z^n = z^{n' - 1}</tex>. <tex>n - k</tex> преобразуется в <tex>n' - 1 - k</tex> (так как <tex>n' - 1 = n</tex>). Тогда, преобразуя предыдущее выражение, получаем:
 
 
 
<tex>G(z) \cdot G(z) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k} = \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex>
 
 
 
Домножая это произведение на <tex>z</tex>, получаем
 
 
 
<tex>z \cdot G^2(z) = z \cdot \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1} = \sum\limits_{n' = 1}^{\infty}z^{n'} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex>
 
 
 
Тогда
 
 
 
<tex>z \cdot G^2(z) = \sum\limits_{n = 1}^{\infty}z^{n} \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} ~~~~ \textbf{(2)}</tex>
 
 
 
Из <tex> \textbf{(1)}</tex> и <tex>\textbf{(2)}</tex> получаем:
 
 
 
<tex>G(z) = 1 + z \cdot G^2(z)</tex>
 
 
 
Преобразуя, получаем квадратное уравнение на <tex>G(z) :</tex>
 
 
 
<tex>z \cdot G^2(z) - G(z) + 1 = 0</tex>
 
 
 
Из этого квадратного уравнения находим два варианта <tex>G(z) :</tex>
 
 
 
<tex>G(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}</tex>
 
 
 
Выберем из двух корней тот, который удовлетворяет определению <tex>G(z)</tex> как производящей функции чисел Каталана.
 
 
 
Домножая обе части на <tex>2z</tex>, получаем <tex>G(z) \cdot 2z = 1 \pm \sqrt{1-4z} ~~~~~\textbf{(3)}</tex>
 
 
 
Выберем нужный из двух корней, посчитав значение обеих частей при <tex>z = 0</tex>
 
 
 
Из определения производящей функции для чисел Каталана известно, что <tex>G(z) = C_0 + C_1 \cdot x + \ldots + C_n \cdot x^n + \ldots</tex>, тогда <tex>G(0) = C_0 = 1</tex>
 
 
 
Тогда при <tex>z = 0</tex> выражение <tex>\textbf{(3)}</tex> принимает вид <tex>G(0) \cdot 2 \cdot 0 = 1 \pm \sqrt{1-4 \cdot 0}</tex>, или <tex>0 = 1 \pm 1</tex>.
 
 
 
Тогда очевидно, нужно выбрать знак <tex>-</tex> в выражении, чтобы при <tex>z = 0</tex> левая и правая части были равны.
 
 
 
Тогда <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex>
 
 
 
Проверим, что <tex>G(z)</tex> действительно является производящей функцией чисел Каталана. Для этого разложим <tex>G(z)</tex> в ряд.
 
 
 
<tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{\sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sqrt{1 - 4z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot (1 - 4z)^{\frac{1}{2}} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dbinom{\frac{1}{2}}{n})</tex>
 
 
 
<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dfrac{(-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^n \cdot 4^n \cdot z^n \cdot (-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^{2n - 1} \cdot 4^n \cdot z^n}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n})</tex>
 
 
 
<tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-z^0}{2 \cdot 0 - 1} \cdot \dbinom{2 \cdot 0}{0} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>
 
 
 
<tex>= \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-1}{-1} \cdot 1- \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>
 
 
 
<tex> = \sum\limits_{n = 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n})  = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n + 2)!}{(n + 1)! \cdot (n + 1)!}</tex>
 
 
 
<tex> = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n)! \cdot (2n + 1) \cdot 2 \cdot (n + 1)}{(n)! \cdot (n)! \cdot (n + 1) \cdot (n + 1)}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(4n + 2)}{n + 1} \cdot \dbinom{2n}{n})</tex>
 
 
 
<tex>= \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n + 1)}{n + 1} \cdot \dbinom{2n}{n}) = \sum\limits_{n = 0}^{\infty} (z^n \cdot \dfrac{1}{n + 1} \cdot \dbinom{2n}{n})</tex>
 
 
 
Тогда коэффициент при <tex>z^n</tex> в разложении <tex>G(z)</tex> равен <tex>\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>, что совпадает с аналитической формулой для чисел Каталана. (<tex>C_n = \dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>) Поэтому <tex>G(z) = \sum\limits_{n = 0}^{\infty} z^n \cdot C_n</tex>, поэтому <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex> является производящей функцией чисел Каталана.
 
  
 
==Смотри также==
 
==Смотри также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)