Читайте также:
|
Насправді числа Каталана C (n) визначаються так: нульове число Каталана дорівнює одиниці. Число з номером n дорівнює сумі наступних творів: нульового числа на (n-1)-е, першого числа на (n-2)-e, другого на (n-3)-е,..., (n-1)-го на нульове, так щоб сума номерів двох перемножуваних чисел дорівнювала n-1. Більш строго це можна записати так: 
(1)
Так, для малих значень n отримаємо: 
Покажемо, що саме така рекуррентная формула відповідає рішенням всіх трьох запропонованих завдань.
Розглянемо спочатку випадок правильних скобочних структур (розстановок дужок). Нехай дана деяка правильна розстановка n пар дужок. Зрозуміло, що початкова дужка a буде відкриває. Отже, їй відповідає якась закриває дужка b. Між цими двома дужками знаходиться інший набір дужок, можливо порожній, який, очевидно, є правильною скобочной структурою. Крім того, послідовність дужок, що стоїть після дужки b, також правильна. Таким чином, всередині нашої структури є ще дві правильні структури, сумарна кількість пар дужок у яких одно n-1. Ці дві структури повністю визначають початкову розстановку дужок: для її отримання досить укласти в дужки першу структуру, а потім праворуч приписати до неї другу.
Дата добавления: 2015-07-17; просмотров: 51 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Три завдання про числа Каталана | | | Пример. У структурі (() ()) (()) з п'яти пар дужок дужки, відмічені червоним, відокремлюють правильну структуру з двох пар дужок від правильної структури з двох пар дужок. |