Есть классическая задача, известная как «задача Мозера о делении круга хордами». Суть её проста: если на окружности отметить несколько точек и соединить их всеми возможными хордами так, чтобы никакие три не пересекались в одной внутренней точке, то на сколько частей разобьётся круг?
Интуиция подсказывает простую схему. Первые шаги дают закономерность: одна точка — один сектор, две точки — два, три — четыре, четыре — восемь, пять — шестнадцать. Кажется, что формула очевидна: каждое новое добавление удваивает количество частей, и значит ответ должен быть 2^(m−1), где m — количество точек. Но при шести точках магия ломается: вместо 32 частей получается 31. Именно этот сбой стал поводом для Льва Мозера в 1949 году сформулировать задачу как пример того, что «индукция может подводить».
Дальнейшие исследования показали, что правильное выражение для количества областей куда сложнее и связано с комбинаторикой. Фактически оно опирается на выборы пар и четвёрок точек: количество хорд зависит от сочетаний из двух, а число точек пересечения внутри круга — из четырёх. На этой базе выводится формула Мозера, которая уже точно описывает рост последовательности.
В статье Карлоса Родригеса-Лукатеро рассматриваются разные способы её получения. Сначала через элементарные комбинаторные рассуждения: учитывается количество хорд и точек пересечения, а затем прибавляется единица за исходный круг. Второй способ основан на знаменитой формуле Эйлера для планарных графов, которая связывает количество вершин, рёбер и граней. Если рассматривать хорды и дуги как рёбра, точки пересечения как вершины, а полученные части — как грани, то результат снова приводит к формуле Мозера. Наконец, автор предлагает ещё один путь — через разностные уравнения. Если построить таблицу конечных разностей для последовательности 1, 2, 4, 8, 16, 31, 57…, то получится рекуррентное соотношение четвёртого порядка. Его решение снова даёт точную формулу.
