Числа Каталана Сегодня в Большом театре огромная очередь. Все стараются достать билеты
Скачать 250.38 Kb.
|
| Числа Каталана Сегодня в Большом театре огромная очередь. Все стараются достать билеты. Из учебника русского языка для немцев. Многим наверняка знакома последовательность натуральных чисел 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… в которой каждое следующее число является суммой двух предыдущих. Эти числа носят имя знаменитого средневекового итальянского математика Фибоначчи, также известного как Леонардо Пизанский. У этих чисел есть много замечательных свойств, о которых мы расскажем в настоящей статье. Существуют и другие замечательные последовательности натуральных чисел, об одной из которых мы расскажем в настоящей статье. Эта последовательность начинается числами 1, 2, 5, 14, 42,132, …; ее члены называются числами Каталана в честь бельгийского математика Эжена Шарля Каталана. Эти числа связаны с различными задачами комбинаторики, теории вероятностей, теории чисел. О закономерности построения следующего члена последовательности по предыдущим ее членам мы поговорим чуть позже, а пока рассмотрим некоторые задачи, в которых эти числа появляются. Более углубленно о комбинаторике таких последовательностей чисел можно прочесть в [1]. Три задачи о числах КаталанаБудем рассматривать расстановки круглых скобок. Назовем расстановку скобок правильной, если все скобки разбиты на пары, причем каждая пара состоит из открывающей и закрывающей скобок, причем закрывающая скобка расположена позднее соответствующей ей открывающей, а для любой скобки 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 — двум, далее пяти, четырнадцати, и т.д. По ответам видно, что для этих задач прослеживается некоторая закономерность, которая связана с числами Каталана. При этом мы до сих пор не выяснили, по каким правилам вычисляются члены этой знаменитой последовательности. |
Добавить документ в свой блог или на сайт
Похожие:
 | 1Натуральные числа 1,2,3,4, счёт предметов, указание порядкового... Число 0 тоже целое. Рациональные числа – целые и дроби (+,-) Вид М/N, где (N 0) m и n- взаимно простые целые числа. Иррациональные... | | Урок по теме «Модуль действительного числа» Здравствуйте, ребята! Сегодня на уроке мы постараемся повторить всё, что мы узнали о модуле числа, основные способы решения уравнений,... |
| Урок предмет: история Тема: «Пылающий над Волгой Сталинград» Сегодня у нас необычный урок истории. Я не прошу вас достать учебники и открыть тетради. Сегодня у нас урок памяти. Потому, что сегодня... | | Программа по формированию навыков безопасного поведения на дорогах... «Рациональные числа и действия над ними». В программе вечера спектакль «Рациональные числа в театре Буратино», состоящий из 6 сцен.... |
| Разработка урока математики в 6б классе Тип урока Ему надо преодолеть все трудности, которые встречаются на пути, дети должны вспомнить все, что изучалось по теме «Координатная прямая»,... | | Решение. Ответ. 20 Натуральные числа, а также все числа противоположные им по знаку, и число ноль называют целыми числами |
| Программа по формированию навыков безопасного поведения на дорогах... Как найти дробь от числа? Сегодня мы продолжим эту работу нахождение дроби от числа | | Программа по формированию навыков безопасного поведения на дорогах... История появления, развития и запись чисел: в Древней Греции, Египте, на Руси; Фигурные числа, совершенные числа, дружественные числа,... |
| Сказка-соревнование. Ход урока Учитель: Сегодня у нас необычный урок... Содержание: натуральные числа и их сравнение; сложение, вычитание, умножение и деление натуральных чисел |  | Документы государственных архивов Республики Татарстан – источниковая... Территориальная и духовная близость татарского и удмуртского народов находит отражение в большом количестве документов по истории... |
| История России, IX примерные экзаменационные билеты соответствуют обязательному Экзаменационные билеты охватывают содержание курса истории России с древности до современности. Вопросы и требования к ответам ориентированы... | | Заявка на областной конкурс методических разработок Ф. И. О. Ярошевская Инна Харисовна Должность Экологические проблемы, ставшие сегодня глобальными, затрагивают интересы каждого человека, так как Земля – наш общий дом. Их решение... |
| Урока по математике в 1 «А» классе Тема: «Числа от 1 до 10» Сегодня, ребята, мы с вами проведём не совсем обычный урок. А необычен он тем, что мы сегодня в гостях в Шеморданском лицее, и у... | | Дифференциация звуков [Р –Л – Р` – Л`]. Согласные звуки [Р –Л – Р`... Этот урок сегодня |
| Урок музыки в 5 классе по теме «Музыка в театре, кино, на телевидении» ... | | Программа по формированию навыков безопасного поведения на дорогах... Учитель: Сегодня на уроке мы с вами научимся выделять целую часть из неправильной дроби и представлять неправильную дробь в виде... |
