На решётке 4 × 4 маршрутов из левого нижнего угла в правый верхний, идущих только вверх и вправо, 8!/(4!·4!) = 70 — калькулятор показывает это во второй ссылке. Большинство добавляет правило «никогда не идти выше диагонали», и тогда число 8!/(4!·5!) = 14. Две формулы различаются множителем n + 1 в знаменателе, и это вся поправка Каталана.
56 запрещённых путей не разбросаны: по аргументу отражения пересечение диагонали ставит им в соответствие один к одному маршруты к сдвинутому конечному пункту, а их 8!/(3!·5!) = 56. Итак, 70 − 56 = 14, и оба экрана совпадают. Та же последовательность 1, 2, 5, 14, 42 считает способы расставить скобки в цепочке множителей, триангуляции выпуклого многоугольника и разрешённые скобочные выражения — третья ссылка это C₅ = 10!/(5!·6!) = 42, следующее, число триангуляций семиугольника.
Ответ
14
Как его читать
C₄ как 8!/(4!·5!) на калькуляторе. Вторая ссылка — подсчёт без ограничений 8!/(4!·4!) = 70, а третья — следующее число Каталана, 42.
Источник
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.