Посчитай маленькие случаи: последовательность узнаёт задачу

Если ты умеешь узнавать задачу на подсчёт по первым членам и знаешь, чем это опасно, листай до «Теперь сам».

Как думаешь, что будет дальше

Точки на окружности соединяют всеми хордами, никакие три хорды не проходят через одну точку внутри. На сколько областей хорды делят круг? При 1, 2, 3, 4, 5 точках ответы: 1, 2, 4, 8, 16.

Сколько областей при шести точках? Ответь себе до чтения.

Ряд «просит» 32 - удвоение напрашивается. Правильный ответ 31. Перебор ниже это покажет, а заодно покажет, почему удвоение было иллюзией: пять первых членов случайно совпали с другой последовательностью.

На что это похоже

Опознание по отпечаткам. Найти человека по фамилии в чужом городе трудно - найти по отпечатку пальцев в базе можно. Ряд чисел, посчитанный перебором, и есть отпечаток задачи: формулировку «скобки» и «рукопожатия» не сравнить, а ряды 1, 2, 5, 14, 42 совпадают сразу. Но отпечаток ищут по нескольким точкам, а не по одной: пять совпавших чисел - это ещё не улика.

Механизм: перебор → ряд → поиск → объяснение

1. Перебор по определению для n = 1, 2, …, 6-8 - насколько хватит бюджета. Это тот самый перебор из урока о маленьком примере: медленный и без идей.
2. Ряд - первые члены. Чем их больше, тем меньше случайных совпадений.
3. Поиск. OEIS принимает ряд через запятую и находит последовательности, которые его содержат. Для задач другого рода есть свои каталоги: у Скиены во второй части книги - 75 самых распространённых алгоритмических задач с советами, что делать с каждой; в разделе 21 этого курса - каталог NP-полных задач; в документации библиотек (graph-библиотеки, решатели) - список того, что уже реализовано.
4. Объяснение. Найденная формула - гипотеза, пока не объяснено, почему задача подчиняется именно ей. Обычно объяснение - это рекуррентность, которую видно в самой задаче.

Правило

Для задачи «сколько» посчитай перебором как можно больше первых членов и найди ряд в OEIS или каталоге. Совпадение - гипотеза, а не ответ. Перебор дальше тех членов, по которым искал, укрепляет гипотезу, но не доказывает её; доказывает объяснение - та же рекуррентность, видная в самой задаче.

Разбор: скобки, рукопожатия и числа Каталана

Две задачи, у которых снаружи нет ничего общего. Сколько есть правильных скобочных последовательностей из n пар? Сколькими способами 2n человек за круглым столом могут одновременно пожать руки парами так, чтобы руки не скрещивались? Обе посчитаем перебором по определению.

import math

def skobki(n):
    # перебор по определению: все строки из 2n скобок, считаем верные.
    # kod - число из 2n битов: бит i равен 1 - на месте i открывающая,
    # 0 - закрывающая; kod от 0 до 2^(2n) - 1 даёт каждую строку один раз
    vsego = 0
    for kod in range(2 ** (2 * n)):
        balans = 0
        ok = True
        for i in range(2 * n):
            if (kod >> i) & 1:
                balans = balans + 1
            else:
                balans = balans - 1
            if balans < 0:
                ok = False
        if ok and balans == 0:
            vsego = vsego + 1
    return vsego

def peresekayutsya(a, b, c, d):
    # хорды (a, b) и (c, d) между точками на окружности, a < b, c < d:
    # пересекаются, если концы чередуются по кругу
    return (a < c < b < d) or (c < a < d < b)

def rukopozhatiya(svobodnye, pary):
    # перебор всех разбиений точек на пары; считаем те, где хорды
    # не пересекаются
    if len(svobodnye) == 0:
        for i in range(len(pary)):
            for j in range(i + 1, len(pary)):
                p = pary[i]
                q = pary[j]
                if peresekayutsya(p[0], p[1], q[0], q[1]):
                    return 0
        return 1
    a = svobodnye[0]
    vsego = 0
    for k in range(1, len(svobodnye)):
        b = svobodnye[k]
        ostalis = svobodnye[1:k] + svobodnye[k + 1:]
        vsego = vsego + rukopozhatiya(ostalis, pary + [[a, b]])
    return vsego

stroka1 = []
stroka2 = []
for n in range(1, 6):
    stroka1.append(skobki(n))
    tochki = []
    for i in range(2 * n):
        tochki.append(i)
    stroka2.append(rukopozhatiya(tochki, []))
print("правильные скобки из n пар:     ", stroka1)
print("рукопожатия 2n людей без скрещ.:", stroka2)

# первая скобка закрывается где-то: внутри неё i пар, после - n-1-i
kat = [1]
for n in range(1, 11):
    s = 0
    for i in range(n):
        s = s + kat[i] * kat[n - 1 - i]
    kat.append(s)
print("по рекуррентности:", kat[1:])
formula = []
for n in range(1, 11):
    formula.append(math.comb(2 * n, n) // (n + 1))
print("C(2n, n) / (n + 1):", formula)

правильные скобки из n пар:      [1, 2, 5, 14, 42]
рукопожатия 2n людей без скрещ.: [1, 2, 5, 14, 42]
по рекуррентности: [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
C(2n, n) / (n + 1): [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

Ряд 1, 2, 5, 14, 42 в OEIS первым находит A000108 - числа Каталана, те самые, что в разделе 23 считали триангуляции выпуклого многоугольника. Там же формула C(2n, n) / (n + 1) и рекуррентность. Но прежде чем поверить, нужно объяснение - и оно видно в самой задаче. Первая скобка где-то закрывается: внутри неё i пар, после неё - остальные n − 1 − i, и обе части сами правильные. Отсюда K(n) = Σ K(i) · K(n − 1 − i). У рукопожатий так же: человек 0 жмёт руку человеку k, и хорда между ними делит остальных на две стороны. Руки через хорду тянуть нельзя - скрестятся, - поэтому каждая сторона разбивается на пары сама по себе; значит, на каждой стороне чётное число людей, 2i и 2(n − 1 − i), и рекуррентность та же. Одинаковая рекуррентность - одна структура, и теперь совпадение ряда доказано, а не угадано. Формулу C(2n, n) / (n + 1) мы из рекуррентности не выводим - это отдельное доказательство, через производящие функции или отражение путей, и оно не нужно: рекуррентность уже показала, что ряд - числа Каталана, а формула для них - проверенный результат каталога, который программа ещё и сверила на десяти членах.

Что это даёт на практике: перебор растёт быстро - у скобок 4ⁿ строк (2n позиций, в каждой одна из двух скобок), у рукопожатий (2n − 1) · (2n − 3) · … · 1 разбиений (для 10 человек 9 · 7 · 5 · 3 · 1 = 945), и в учебной программе он доведён лишь до n = 5, а формула считает n = 1000 мгновенно, и для неё есть готовые свойства - например, что с ростом n каждое следующее число почти вчетверо больше предыдущего.

Разбор: пять совпавших членов, которые обманули

Теперь задача из начала урока. Перебор: хорды - все пары точек, пересечения - пары хорд, у которых концы чередуются по кругу; каждая новая хорда добавляет одну область и ещё по одной на каждое пересечение с уже проведёнными. Почему так: хорда, которая пересекает k проведённых, разрезана ими на k + 1 отрезок, и каждый отрезок проходит внутри одной области и делит её надвое - областей становится на k + 1 больше.

import math

def oblasti(n):
    # точки 0..n-1 на окружности в общем положении; каждая хорда
    # добавляет одну область плюс по одной на каждое пересечение
    hordy = []
    for a in range(n):
        for b in range(a + 1, n):
            hordy.append([a, b])
    peresechenij = 0
    for i in range(len(hordy)):
        for j in range(i + 1, len(hordy)):
            a = hordy[i][0]
            b = hordy[i][1]
            c = hordy[j][0]
            d = hordy[j][1]
            if (a < c < b < d) or (c < a < d < b):
                peresechenij = peresechenij + 1
    return 1 + len(hordy) + peresechenij

ryad = []
stepeni = []
for n in range(1, 10):
    ryad.append(oblasti(n))
    stepeni.append(2 ** (n - 1))
print("области круга:", ryad)
print("2 ** (n - 1): ", stepeni)
formula = []
for n in range(1, 10):
    formula.append(1 + math.comb(n, 2) + math.comb(n, 4))
print("1 + C(n,2) + C(n,4):", formula)

области круга: [1, 2, 4, 8, 16, 31, 57, 99, 163]
2 ** (n - 1):  [1, 2, 4, 8, 16, 32, 64, 128, 256]
1 + C(n,2) + C(n,4): [1, 2, 4, 8, 16, 31, 57, 99, 163]

Пять членов совпали с 2ⁿ⁻¹, шестой - уже нет. Поиск в OEIS по «1, 2, 4, 8, 16» выдал бы прежде всего степени двойки; поиск по «1, 2, 4, 8, 16, 31» находит A000127 - число областей круга, 1 + C(n, 2) + C(n, 4). Объяснение видно из перебора: области - это одна исходная, плюс по одной на хорду (C(n, 2) хорд), плюс по одной на каждое пересечение, а пересечение задаётся четвёркой точек (C(n, 4)). Почему четвёркой и ровно одно: две хорды пересекаются внутри круга, только если их концы чередуются по окружности, - а из четырёх точек на окружности чередующуюся пару хорд составляют ровно одним способом, диагоналями четырёхугольника. Обратно, каждое пересечение - это две хорды, то есть четыре конца. Тройных пересечений нет: по условию никакие три хорды не проходят через одну точку. При n ≤ 5 эта сумма случайно равна 2ⁿ⁻¹, а дальше многочлен четвёртой степени отстаёт от экспоненты.

Граница правила: чем меньше членов, тем больше последовательностей их содержат. Здесь помогло одно: перебор досчитал до девяти, а гипотезу «удвоение» проверили на тех членах, по которым её не строили.

Что ломается без этого

Формула по пяти точкам. «Количество вариантов удваивается» - и оценка нагрузки на систему в полтора раза мимо при n = 9 (256 против 163) и в сто раз при n = 20 (524 288 против 5036).

Перебор там, где есть формула. Час подбора отсечений для подсчёта при n = 30, хотя ответ - число Каталана и считается одной строкой.

Совпадение без объяснения. Формулу нашли и приняли, а у задачи есть лишнее ограничение, которое ломает рекуррентность на n = 7.

Зачем это в работе

Подсчёт вариантов нужен чаще, чем кажется: сколько конфигураций проверит тест, сколько маршрутов у планировщика, сколько ключей нужно в кеше. Перебор на маленьких n и поиск ряда за десять минут дают формулу, на которую иначе ушёл бы вечер с бумагой, - и тот же приём ловит ошибку в собственной формуле: сверь её с перебором на n = 1..8.

Теперь сам

1. Сколько правильных скобочных последовательностей из 6 пар? Из 7?
2. Сколько областей дают хорды между 10 точками на окружности общего положения?
3. Перебор дал ряд 1, 1, 2, 3, 5, 8. Какую последовательность найдёт поиск и что ещё надо сделать, чтобы ей поверить?