Европа · переписка с Сегнером, 1751
Сколькими способами разрезать многоугольник
Как звучало тогда
Сколькими различными способами можно разрезать выпуклый многоугольник непересекающимися диагоналями на треугольники?
Условие
Сколькими способами выпуклый шестиугольник разбивается непересекающимися диагоналями на треугольники? А пятиугольник и семиугольник?
Показать ответ
шестиугольник 14 способами, пятиугольник 5, семиугольник 42
О чём эта задача
Ряд $1,\ 2,\ 5,\ 14,\ 42,\ 132$ — это каталановы числа, и Эйлер нашёл их за семьдесят лет до Каталана. Рекуррентное соотношение получается перебором: выберем сторону, посмотрим, в какую вершину смотрит опирающийся на неё треугольник, — многоугольник распадается на два меньших, и числа перемножаются. Те же числа считают правильные скобочные записи, пути по решётке под диагональю и двоичные деревья; их появление в четвёртой задаче подряд обычно и убеждает школьника, что комбинаторика — не набор фокусов.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.