Пример. У структурі (() ()) (()) з п'яти пар дужок дужки, відмічені червоним, відокремлюють правильну структуру з двох пар дужок від правильної структури з двох пар дужок.

Таким чином, стає зрозумілим сенс формули (1): для того, щоб порахувати кількість правильних структур з п'яти пар дужок потрібно розглянути зафіксувати першу пару дужок, а потім поставити дві правильні структури, сумарна кількість дужок у яких дорівнює чотирьом.

Аналогічна ситуація має місце і у випадку з багатокутниками: ми фіксуємо деякий ребро і розглядаємо трикутник, що примикає до цього ребру, див. рис. 2. Він розбиває (n +2)-кутник на (p +2)-кутник і (q +2)-кутник, де p + q = n-1. Ці два багатокутника повинні бути розбиті на трикутники своїми непересічними діагоналями, які є діагоналями вихідного багатокутника. Будь-яке таке розбиття двох "маленьких" багатокутників породжує розбиття початкового багатокутника.

На малюнку 2 зображений восьмикутник (8 = 6 +2), розбиття якого на трикутники непересічними діагоналями породжується такими розбивками для чотирикутника (4 = 2 +2) і п'ятикутника (5 = 3 +2). При цьому 6-1 = 2 +3.

Таким чином, для кількості розбиттів (n +2)-кутника непересічними діагоналями на трикутники має місце та ж рекуррентная формула, що і для скобочних структур.

Перейдемо, нарешті, до опису завдання про квитки в театр. Для кожного можливого випадку розподілу п'ятирубльових і десятирублевих банкнот у вартих у черзі можна побудувати правильну дужкову структуру. Дійсно, кожному наступному який стоїть у черзі будемо приписувати дужку, яка буде відкриває, якщо у нього на руках п'ятирублева купюра, і закриває, якщо десятикарбованцеві. Умова того, що у касира завжди буде достатньо п'ятирубльових купюр означає, що по ходу написання слова з дужок кількість відкривають буде завжди не менша кількість закривають, а те, що ці купюри іссякнут після обслуговування останнього покупця, значить, що в усьому слові кількість відкривають дужок дорівнюватиме кількості закриваючих. Це й означає, що кожній відкриває скобці буде однозначно відповідати закриває. Для цього людині, який дав п'ять рублів, після чого у касира стало m п'ятирубльових банкнот, потрібно зіставити людини, що дала десять рублів і стоїть після першого, після чого у касира залишилася (m-1) п'ятирублева банкнота, причому між першим і другим людиною у касира повинно завжди бути не менше n п'ятирубльових банкнот.

Пример. Для скобочной структури () (() (())) з п'яти пар дужок поставимо у відповідність такий розподіл банкнот: 5, 10, 5, 5, 10, 5, 5, 10, 10, 10. При цьому кількість п'ятирубльових банкнот у касира після продажу чергового квитка буде змінюватися таким чином:

1, 0, 1, 2, 1, 2, 3, 2, 1, 0

() (() (()))

Зі сказаного вище випливає, що правильні дужкові структури з n дужок однозначно відповідають "хорошим" розподілах п'ять і десять банкнот у вартих у черзі.

Таким чином, кількість правильних черг з 2n людина одно C (n) і відповідь на третє завдання, як і на перші дві, пов'язаний з числами Каталана.

При цьому у нас залишається відкритим ще одне питання: як рахувати числа Каталана, тобто знайти формулу для C (n) НЕ рекуррентную, а в явному вигляді.

Похідні функції

Нехай є деяка послідовність чисел a(n), n=0,1, … Запишемо формальний ряд (нескінченну суму) , де t позначає деяку формальну змінну, тобто букву, зручну для запису формальних виразів і твори операцій з ними. Такий ряд називається виробляє функцією або генератриси для послідовності a (n). Так, для чисел Фібоначчі ми отримаємо похідна функцію , а для чисел Каталана — ряд Виявляється, що обчислювати такі ряди в цілому легше, ніж кожен їх член окремо.

Дата добавления: 2015-07-17