Три завдання про числа Каталана

Будемо розглядати розстановки круглих дужок. Назвемо розстановку дужок правильною, якщо всі дужки розбиті на пари, причому кожна пара складається з відкриває і закриває дужок, причому закриває дужка розташована пізніше відповідної їй відкриває, а для будь-якої дужки b, що лежить між відкриває дужкою a і парної їй закриває дужкою a 'парна дужка b 'також лежить між a і a'.

Задача 1. Скільки існує правильних розстановок n пар дужок для фіксованого натурального числа n?

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

Для невеликих значень змінної n неважко порахувати відповідь шляхом перебору: для однієї пари існує одна розстановка дужок: (), для двох - дві: () () і (()), для трьох - п'ять: () () (), () (()), (()) (), (() ()), ((())).

Задача 2. Скількома способами можна розбити опуклий (n +2)-кутник на трикутники непересічними діагоналями?

Для цього завдання також неважко порахувати відповідь для малих n: для трикутника (n = 1) такий спосіб один, для чотирикутника (n = 2) - два (можна вибрати будь-яку з двох діагоналей, і вона буде розбивати чотирикутник на два трикутника), для п'ятикутника (n = 3) - п'ять, для шестикутника (n = 4) - чотирнадцять Всі ці розбиття показані на рис. 1.

Задача 3. У театральної каси стоїть черга за квитками з 2n осіб. Квиток коштує п'ять рублів, а в наявності у кожного з стоять у черзі є рівно одна банкнота - або п'ять, або десять рублів, причому кожен з двох видів банкнот зустрічається рівно у n осіб. У касира в початковий момент немає п'ятирубльових банкнот. Кожен, що стоїть у черзі, купуючи квиток, якщо дає десятирублевую банкноту, повинен отримати здачу. Яка ймовірність того, що протягом всієї черги у касира завжди буде достатній запас п'ятирубльових банкнот для здачі, а в кінці у нього не залишиться п'ятирубльових купюр?

Легко бачити, що існує можливих ситуацій (рівно стільки є способів розподілити серед 2n любителів театру n осіб, у яких на руках десятикарбованцеві купюра і n людина з п'ятирублеву купюрами на руках). Отже, для вирішення завдання потрібно порахувати, у скількох випадках у касира протягом всієї черги будуть в достатній кількості п'ятирубльових купюри, причому в останній момент вони у нього закінчаться. Отримане число випадків потрібно розділити число випадків на .

Підрахунок таких випадків для малих значень числа n знову приводить нас до знайомої послідовності: при n = 1 це число дорівнює одиниці, при n = 2 - двом, далі п'яти, чотирнадцяти, і т.д. За відповідями видно, що для цих завдань простежується деяка закономірність, яка пов'язана з числами Каталана. При цьому ми досі не з'ясували, за якими правилами обчислюються члени цієї знаменитої послідовності.

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