Четыре шага вверх и четыре вбок, не пересекая диагональ: 14 из 70 путей

Центральный биномиальный коэффициент считает все маршруты; формула Каталана считает разрешённые.

Статистика и данные · Уровень: Классический результат · Обновлено 2026-11-10

На решётке 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

Пересчитать в калькуляторе

Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.

Это независимый сторонний информационный сайт. Он не связан с Casio, Texas Instruments или их дистрибьюторами, не спонсируется ими и не имеет их авторизации. Названия моделей и продуктов — товарные знаки соответствующих правообладателей; они приведены здесь только для идентификации устройств.

Последовательности нажатий клавиш в этих справочниках составлены на основе собственных данных о раскладке этого сайта — тех же данных, которые отображает онлайн-калькулятор, — а также общедоступных сведений о продуктах. Характеристики и региональные конфигурации проверяются на реальном устройстве и по последним материалам производителя.