Кислотно-лужна рівновага

Визначення

n-те число Каталана, позначене як C(n), визначається як 1 поділене на (n+1), помножене на біноміальний коефіцієнт (2n по n). Еквівалентно це можна записати без будь-якого ділення, як (2n по n) мінус (2n по n+1), що відповідає цілому числу, яке отримують з двох біноміальних коефіцієнтів, розташованих поруч у трикутнішому многокутнику Паскаля. Послідовність починається з C(0) = 1, C(1) = 1, C(2) = 2, C(3) = 5, C(4) = 14, C(5) = 42, C(6) = 132, і швидко зростає – кожен член є цілим числом, незважаючи на те, що формула містить ділення, яке само по собі є маленьким математичним дивом, вартим уваги.

C(n) = 1/(n+1) * C(2n, n) = C(2n, n) - C(2n, n+1)

worked example, n = 3:
  C(6, 3) = 20
  C(3) = 20 / (3+1) = 20 / 4 = 5

n :  0   1   2   3   4    5    6
Cn:  1   1   2   5  14   42  132

Рекурентне співвідношення — і чому воно з'являється скрізь

Каталанські числа також задовольняють рекурентному співвідношенню: C(0) = 1, та C(n+1) дорівнює сумі, від i=0 до n, C(i) помножене на C(n-i). Це зведення (конволюція) випливає безпосередньо з поділу структури розміром n+1 на «корінь» — ліву частину розміром i та праву частину розміром n-i — обидві частини незалежні, тому кількість способів побудови всієї конструкції дорівнює добутку кількості способів побудови кожної половини, підсумованому для кожного можливого точки поділу. Саме ця ідея пояснює, чому одна й та сама послідовність з'являється в структурах, які нічим не схожі: будь-який об’єкт, який можна розкласти таким самим чином — менша частина занурена або приєднана до меншої залишкової частини — у підсумку слідує цьому рекурентному співвідношенню і, отже, підраховується каталанськими числами.

Збалансовані дужки та шляхи Діка

C(n) рахує кількість способів розташувати n пар збалансованих дужок. Для n = 3 існує рівно 5: ((())), (()()), (())(), ()(()), ()()(). Шлях Діка – це решіткова траєкторія від точки (0,0) до точки (2n,0), побудована з кроків вгору висотою (1,1) та кроків вниз висотою (1,-1), яка ніколи не опускається нижче осі x, і вона безпосередньо бізвидна з ланцюжком збалансованих дужок – крок вгору представляє відкриту дужку, а крок вниз – закриту дужку, отже «ніколи не нижче осі» означає «ніколи не більше закритих дужок, ніж відкритих дотепер».

Двостворлові дерева

C(n) також є кількістю структурно різних повних бінарних дерев з n внутрішніми вузлами, еквівалентно n+1 листовим вузлам. Кожне таке дерево розгалужується від кореня на ліве та праве піддерева, і якщо ліве піддерево має i внутрішніх вузлів, то праве піддерево повинно мати n-i — що є точною рекурентною формулою згортки, застосованою до дерев замість дужок.

Полігональні трикутвизації та непересічні хорди

Кількість способів трикутвизувати опуклий багатокутник з n+2 сторонами, використовуючи лише непересічні діагоналі, також дорівнює C(n). Це була оригінальна 18-сторічна задача Ейлера — він вивів закономірність для малих полігонів до того, як послідовність було формалізовано в 19 столітті Жюлем Катаном, чиє ім'я тепер несе в собі це позначення. Близьке до цього об’єкт є діаграма непересічних хорд: кількість способів з’єднати 2n точок, розташованих навколо кола, n хордами таким чином, щоб жодні дві хорди не перетиналися, також дорівнює точно C(n), і вона теж розкладається в одну визначену точку на два менші непересічні задачі, що знову дають таку ж рекурсію.

Як швидко зростає послідовність

Зі збільшенням n, C(n) асимптотично дорівнює 4 в степені n, поділеному на n у степені 1.5 та на квадратний корінь з π. Таким чином, відношення між послідовними членами, C(n+1) поділене на C(n), неухильно наближається до 4, не досягаючи її точно — C(6)/C(5) дорівнює 132/42, що вже приблизно 3.14, а пізніше відношення ще більше наближаються до 4, але завжди залишаються трохи нижче, досягаючи точності лише в межі, коли n прямує до нескінченності.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.