розбивку багатокутників. Ця задача ізоморфна і завданням, здавалося б з нею. Ця задача ізоморфна і завданням, здавалося б з нею не пов'язаним.
Сам іженія Шарль Каталан, бельгійський математик, в 1838 р вирішив наступну задачу: Нехай є ланцюжок з n букв, розташованих в заданому порядку. Необхідно розставити (n - 1) пару дужок так, щоб усередині кожної пари стояло рівно два вираження laquo ;. Цими спареними виразами можуть бути або дві сусідні букви, або два сусідніх вираження. Скількома способами можуть бути поставлені дужки? Raquo;
Для букв a і b є тільки одна можливість: (ab).
Для трьох букв таких можливостей дві: ((ab) c) (a (bc)).
Для чотирьох букв кількість способів збільшиться до п'яти:
((ab) (cd)) (((ab) c) d) (a (bc) d) ((a (bc) d).
Ці числа 1; 2; 5 - перші числа Каталана, виявляється, числа Каталана дають нам кількість способів розстановки дужок у буквених ланцюжках відповідних довжин.
У 1961 р Фордер, описуючи числа Каталана, вказав простий спосіб взятого однозначної відповідності між підрахунком комбінацій в багатокутниках і розстановкою дужок у буквених ланцюжках.
Розглянемо, наприклад, семикутник:
Позначення підстави йде останнім і позначення для нього однозначно визначається тріангуляцією ( тріангуляція - розбиття на трикутники). Якщо застосувати вказаний прийом для вище перерахованих багатокутників, то отримаємо ланцюжка літер з розставленими дужками.
Англійський математик Артур Келі довів, що числа Каталана перераховують всі плоскі кореневі кубічні дерева (саме, n - е число Каталана дорівнює кількості плоских кореневих кубічних дерев з (n + 1) - ой кінцевий вершиною).
Дерево - це зв'язний граф (вершини, з'єднані відрізками), що не має циклів.
Плоский означає, що граф намальований на площині без перетинів.
Кореневе - Це дерево має стовбур, кінець якого має корінь.
Таким чином, граф можна намалювати у вигляді як би що росте нагору із землі дерева.
Кубічне означає, що в кожній вершині (крім кореня і кінців гілок) дерево розгалужується, утворюючи точки, в яких зустрічаються три ребра.
Під кожною ланцюжком букв з дужками записано двійкове число, одержуване заміною всіх дужок 1 raquo ;, а всіх букв - 0 raquo ;, пропускаючи праві дужки. Для правих дужок немає необхідності вводити позначення, т. К. Задане положення лівих дужок і метод групування букв визначає постановку дужок єдиним чином.
Розглянемо ще таке завдання:
Візьмемо шахові дошки зі сторонами 2; 3; 4;..., В яких зафарбовані всі квадрати на північний захід від головної діагоналі. Потрібно провести човен з лівого нижнього кута в правий верхній. Рухатися можна, не заходячи при цьому на зафарбовані клітини. Скільки існує шляхів лодії на дошці зі стороною а? Raquo;
Рішення:
Під стороною довжини n напишемо двійкове число, відповідне кореневого дереву (кубічному) з n кінцевими вершинами.
Просуваючись по двійковим розрядам числа зліва на право будемо рухати човен вправо, проходячи 1 raquo ;, і вгору, проходячи 0 (остання двійкова цифра не враховується). Ця послідовність двійкових цифр визначає шлях, і всі шляхи лодії можуть бути отримані таким чином.
числовий послідовність Фібоначчі Каталан
Висновок
У роботі на прикладі двох найбільш широко відомих зворотних послідовностей були розглянуті способи завдання рекурентних послідовностей, їх деякі властивості, застосування в різних розділах математики.
Усі поставлені в даному дослідженні цілі були досягнуті: зроблений історичний екскурс з теорії питання, розглянуті різні формули і їхні висновки, показано застосування досліджуваних у роботі об'єктів на прикладі різних завдань. Всі розглянуті задачі супроводжуються докладними поясненнями, доказами і ілюстраціями.
При роботі над даною темою були використані різноманітні джерела інформації такі як: друковані та електронні видання, енциклопедична та навчальна література.
Обрана тема найчастіше залишається за сторінками шкільного підручника, хоча вона дуже цікава і багатогранна. У роботі показано зв'язок таких розділів математики як: математичний аналіз і геометрія, комбінаторика і теорія чисел.
Ця робота дозволяє більш детально підійти до питання вивче...
