Изменения
→Аналитическая формула
===Аналитическая формула===
<tex dpi = 150> C_n = \fracdfrac{1}{n+1} \binom {2n} {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 dpi = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \fracdfrac{2n!}{n!n!} - \fracdfrac{2n!}{(n-1)!(n+1)!} = \fracdfrac{2n!}{n!} (\fracdfrac{1}{n!} - \fracdfrac{1}{(n-1)! (n+1)}) = \fracdfrac{2n!}{n!n!(n+1)} = \fracdfrac{1}{n+1} \binom {2n} {n} </tex>
==Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==
