212
правок
Изменения
→Доказательство
точку <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} = \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>
==Примеры==
