Исследовательская работа Выполнена учеником 11 класса «Б» муниципального образовательного учреждения «Общеобразовательная гимназия 3» г. Архангельска Руньковым Александром Александровичем Научный руководитель: учитель математики ВКК муниципального образовательного учреждения «Общеобразовательная гимназия 3» г. Архангельска, Почетный работник общего образования РФ Косарева Галина Николаевна XV областная учебно-исследовательская конференция «ЮНОСТЬ ПОМОРЬЯ»

Последовательность 1, 1, 2, 5, 14, 42, 132, 429, … в «Энциклопедии целочисленных последовательностей», созданной американским математиком и информатиком Нилом Джеймсом Александром Слоэном, имеет номер А среди других пяти тысяч последовательностей.

Введение Объект исследования Числа Каталана Предмет исследования Комбинаторные структуры, связанные с ними Актуальность темы состоит в том, что числа Каталана, являясь специальными числами натурального ряда, возникая из комбинаторных задач, порождают своим существованием целый ряд других комбинаторных проблем, требующих решения.

Цели и задачи Цель работы: рассмотреть задачи, приводящие к одной и той же числовой последовательности, и найти решение задачи Дональда Кнута про перестановки из n чисел. Задачи работы: 1) дать различные определения чисел Каталана и установить связь между ними; 2) установить биекции между некоторыми множествами; 3) установить биекцию между правильными расстановками пар скобок и перестановками Дональда Кнута из n чисел; 4) показать ряд свойств комбинаторных структур, связанных с числами Каталана.

Новизна данной работы заключается в подборе, составлении и решении задач по теме исследования, а также в том, что в известных нам источниках литературы по данной теме вопрос об установлении биекции между перестановками Дональда Кнута и правильными расстановками скобок не поднимался. Теоретическая и практическая значимость – в использовании на кружках и факультативах, для подготовки к олимпиадам. Методы исследования: 1) поиск, анализ и синтез различных источников информации: книг, статей, Интернет-ресурсов; 2) самостоятельное решение комбинаторных задач; 3) поиск новых подходов к решению уже известных задач.

З АДАЧА Э ЙЛЕРА. Т РИАНГУЛЯЦИИ ВЫПУКЛОГО N +2 - УГОЛЬНИКА Иными словами, сколько существует различных способов разрезать выпуклый n+2 - угольник на треугольники непересекающимися внутри него диагоналями? «Сколько различных триангуляций может иметь выпуклый n+2 - угольник?».

З АДАЧА Э ЙЛЕРА. Т РИАНГУЛЯЦИИ ВЫПУКЛОГО N +2 - УГОЛЬНИКА n = 1n = 2n = 3 n = 4n = 5 Возникает последовательность из чисел:

З АДАЧА К АТАЛАНА. В ЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЙ Рассмотрим другую алгебраическую задачу. В строку записано произведение из букв. Требуется расставить пар круглых скобок так, чтобы внутри каждой пары скобок стояли либо две соседние буквы, либо буква и соседнее выражение в скобках, либо два соседних выражения в скобках. Например,. Найти количество различных перестановок скобок. ((((ab)c)d)(ef))

З АДАЧА К АТАЛАНА. В ЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЙ abc (a(bc))((ab)c) abcd (((ab)c)d)((ab)(cd)) ((a(bc))d)(a(b(cd))) (a((bc)d)) abcde 5 способов вида ((abcd)e) 5 способов вида (a(bcde)) 2 способа вида ((abc)(de)) 2 способа вида ((ab)(cde))

З АДАЧА К АТАЛАНА. В ЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЙ Теперь выведем общую формулу для. Произведение в конечном счете получается как произведение произведения первых нескольких символов на некоторое произведение остальных:. Первые q символов могут быть скомбинированы способами, последние же n + 1 – q символов - способами. Таким образом,.

Итак, число различных перестановок пар скобок в произведении из n множителей, а также различных триангуляций выпуклого n+2-угольника задаётся следующим рекуррентным соотношением: Числа вида и называют числами Каталана в честь бельгийского математика Эжена Шарля Каталана, подробно изучившего эту последовательность при решении задачи про перестановки n пар скобок Например,.

С ВЯЗЬ МЕЖДУ ЗАДАЧАМИ Э ЙЛЕРА И К АТАЛАНА Нельзя ли установить взаимно однозначное соответствие или, иначе говоря, биекцию между разбиениями на треугольники и способами подсчёта произведений? Оказывается, можно! Впервые это заметил математик Фордер в 1961 году. n = 1n = 2 Будем записывать буквы последовательно на сторонах n+2 – угольника против часовой стрелки. Зафиксируем свободную сторону. Пусть заданы все диагонали n+2 – угольника, тогда каждой диагонали можно сопоставить пару скобок, заключающих произведение выражений на сторонах прилегающего к ней треугольника.

С КОБОЧНЫЕ СТРУКТУРЫ В перестановке скобок из задачи Каталана уберём все буквы и две крайние скобки (самую левую и самую правую). То, что получится назовём правильной скобочной структурой. 1) Количество открывающих скобок равно количеству закрывающих; 2) Ни на каком начальном участке количество закрывающих скобок не превышает количество открывающих. К примеру, скобочные структуры ( ))( или ( )((( ))))( неправильные. (a(b(cd))) – (( ))

С КОБОЧНЫЕ СТРУКТУРЫ При n = 2 расстановок скобок две: ( )( ) и (( )). Пусть различных правильных скобочных структур из n пар скобок –. Сопоставим крайней левой скобке первую правую такую, что количества левых и правых скобок, заключённых между указанными скобками равны. Тогда между этими скобками заключена правильная скобочная структура из m пар скобок. Вне выбранных скобок расположена правильная скобочная структура из n – m – 1 пар скобок. В совокупности способов -. В силу произвольности выбора m из промежутка [0;n – 1] получаем уже знакомое нам рекуррентное соотношение:. (( )(( )(( ))))(( ))((( )( ))) m пар скобок n – m – 1 пар скобок

Задачи, так или иначе приводящие к этому соотношению, иногда имеют явную связь между собой. Вместо того, чтобы искать громоздкое решение задачи и получать это соотношение снова и снова, можно установить взаимно однозначное соответствие с каким- нибудь уже известным комбинаторным объектом. Зачастую в качестве второго выступают именно правильные скобочные структуры.

Т РЕУГОЛЬНИК К АТАЛАНА Со знаменитым треугольником Паскаля знаком каждый школьник. Но не каждый знает, что, если провести вертикальную черту, левее которой проходить нельзя и выписывать числа по правилу треугольника Паскаля, начиная с верхней единицы, на первых двух вертикалях возникают числа Каталана! Сумма чисел, выделенных на рисунке синим цветом, равна числу, обведённому синим кружком: = = = = 429, а сумма чисел, обведённых зелёным цветом равна числу, обведённому зелёным кружком: = = = = 165. Сопоставим открывающей скобке движение по треугольнику вниз-вправо, а закрывающей – движение вниз-влево.

П УТИ ДИКА И ЗАДАЧА ПРО КАРАНДАШИ «Имеются 12 карандашей попарно различной длины. Сколькими способами можно уложить их в коробку в 2 слоя по 6 карандашей так, чтобы в каждом слое карандаши были упорядочены по возрастанию длины (слева направо), а каждый карандаш верхнего слоя лежал строго над карандашом нижнего слоя и был короче его?» Для решения задачи нам понадобится ещё один комбинаторный объект, имеющий прямое отношение к числам Каталана, - путь Дика из 2n звеньев. Назовём укладку карандашей хорошей, если она удовлетворяет условию, и плохой в противном случае и каждой хорошей укладке сопоставим путь Дика, а каждой плохой – путь Дика, пересекающий прямую укладку карандашей и расположим их в порядке возрастания длины. более, чем в одной точке. Для этого возьмём произвольную

П УТИ ДИКА И ЗАДАЧА ПРО КАРАНДАШИ Количество хороших и плохих путей Дика. однозначно определяется шестью движениями вверх- вправо или шестью движениями вверх-влево, поэтому равно. Возьмём часть плохой ломаной, концами которой являются точка пересечения ломаной с прямой с наибольшей ординатой и точка (0;12) и отразим эту часть симметрично относительно прямой. Тогда Если карандаш лежал в верхнем слое, то сопоставим ему движение вверх- вправо, а карандашу из нижнего слоя – движение вверх-влево. Так как карандашей в верхнем и нижнем слоях поровну (6), то верхний конец ломаной имеет координаты (0;12). На рисунке приведён пример такой ломаной. точка (0;12) перейдёт в точку B(-2;12). Пусть новая ломаная определяется движениями вверх-вправо и движениями вверх-влево. Тогда

П УТИ ДИКА И ЗАДАЧА ПРО КАРАНДАШИ Таким образом, количество плохих ломаных однозначно определяется 5 движениями вверх-вправо и 7 движениями «вверх-влево», поэтому количество плохих ломаных равно. Количество хороших ломаных равно. В силу произвольности выбора начального общего количества карандашей для 2n получаем, что хороших укладок:. Нетрудно убедиться, что число различных путей Дика из 2n звеньев равно. Достаточно заметить, что путь Дика – это путь из верхней вершины треугольника Каталана до соответствующего числа на вертикальной черте. Отсюда следует, что.

П ЕРЕСТАНОВКИ Д ОНАЛЬДА К НУТА «Сколькими способами можно так переставить n натуральных чисел, чтобы никакие три из чисел полученной последовательности не шли в порядке возрастания?» В связи с этим возникает гипотеза: число различных перестановок Дональда Кнута равняется.

П ЕРЕСТАНОВКИ Д ОНАЛЬДА К НУТА Гипотеза Назовём перестановку правильной, если она удовлетворяет условию. Тогда каждой правильной перестановке можно взаимно однозначно сопоставить правильную скобочную структуру.

П ЕРЕСТАНОВКИ Д ОНАЛЬДА К НУТА Правило 1 Первому числу сопоставим пару из крайней левой открывающей скобки и крайней правой закрывающей скобки. Например, в перестановке 213 числу 2 сопоставим скобки Следующему после него числу сопоставим: 1) подряд идущие закрывающую и открывающую скобки, если это число больше предыдущего; 2) подряд идущие открывающую и закрывающую, если это число меньше предыдущего более, чем на 1; 3) открывающую и закрывающую, если это число меньше предыдущего на 1, причём закрывающую ставим перед закрывающей скобкой предыдущего числа.

П ЕРЕСТАНОВКИ Д ОНАЛЬДА К НУТА По правилу 1: При n = 1 очевидно:. Для n = 2 получаем две правильные скобочные структуры: и для перестановок 21 и 12 соответственно. Для n = 3 инъекция показана на рисунке.

Ч АСТНЫЕ СЛУЧАИ Как показано выше перестановкам 12 и 21 соответствуют структуры и. В зависимости от того на какое место вставляем 3 в перестановки 12 и 21 сопоставим ей пару скобок следующим образом: если 3 в перестановке стоит 1) на 1 месте, то сопоставляем ей крайнюю левую и крайнюю правую скобки

Ч АСТНЫЕ СЛУЧАИ 2) не на 1 месте, то сопоставляем ей подряд идущие закрывающую и открывающую скобки и вставляем их в соответствующую скобочную структуру непосредственно после открывающей скобки предыдущего числа

Ч АСТНЫЕ СЛУЧАИ Из полученных скобочных структур из трёх пар скобок получим расстановки скобок, которые сопоставим перестановкам Кнута из четырёх элементов, по тому же правилу, вставляя 4 в перестановки 321, 312, 231, 132 и 213. Если 4 в перестановке стоит 1) на 1 месте, то сопоставляем ей крайнюю левую и крайнюю правую скобки Если же после 4 в перестановке стоит не 3, то внутри пары уже поставленных скобок ставим соответствующую скобочную структуру, предварительно изменив её:

Ч АСТНЫЕ СЛУЧАИ а) перемещением закрывающей скобки из пары скобок, сопоставляемой первому числу, в место непосредственно перед первой встретившейся закрывающей скобкой в случае, если после этого первого числа идёт число, не меньшее его на 1 б) в случае, если после первого числа подряд идут числа, вместе с ним образующие в том же порядке убывающую арифметическую прогрессию с разностью 1, перемещением нескольких подряд идущих закрывающих скобок из пар скобок, сопоставляемых этим числам, в место непосредственно перед первой встретившейся закрывающей скобкой

Ч АСТНЫЕ СЛУЧАИ 2) не на 1 месте, то также сопоставляем ей подряд идущие закрывающую и открывающую скобки и вставляем их в соответствующую скобочную структуру непосредственно после открывающей скобки предыдущего числа

Ч АСТНЫЕ СЛУЧАИ N = 5

N = 6

Правило 2 для общего случая Перестановкам 12 и 21 соответствуют структуры ( )( ) и (( )). Пусть задана инъекция для n – 1. Тогда получим расстановку n пар скобок, которая сопоставляется перестановке Дональда Кнута из n чисел, из заданной расстановки n – 1 пар скобок, которая сопоставляется перестановке Дональда Кнута из n – 1 чисел, вставляя пару скобок, сопоставляемую числу n следующим образом: если n в перестановке стоит: 1) на 1 месте, то также сопоставляем ей крайнюю левую и крайнюю правую скобки. Далее, если после n в перестановке стоит n – 1, то внутри пары уже поставленных скобок ставим соответствующую скобочную структуру из n – 1 пар скобок, не меняя её. Если же после n в перестановке стоит не n – 1, то внутри пары уже поставленных скобок ставим соответствующую скобочную структуру, предварительно изменив её:

Правило 2 для общего случая а) перемещением закрывающей скобки из пары скобок, сопоставляемой первому числу, в место непосредственно перед первой встретившейся закрывающей скобкой в случае, если после этого первого числа идёт число, не меньшее его на 1. б) в случае, если после первого числа подряд идут числа, вместе с ним образующие в том же порядке убывающую арифметическую прогрессию с разностью 1, перемещением нескольких подряд идущих закрывающих скобок из пар скобок, сопоставляемых этим числам, в место непосредственно перед первой встретившейся закрывающей скобкой. 2) не на 1 месте, то также сопоставляем ей подряд идущие закрывающую и открывающую скобки и вставляем их в соответствующую скобочную структуру непосредственно после открывающей скобки предыдущего числа.

«Ответ от задачи не зависит!» (Эйлер, Каталан и др.)

Заключение Итак, числовая последовательность Каталана интересна прежде всего тем, что появляется очень часто, самым неожиданным образом во многих задачах из различных областей математики и преимущественно при решении комбинаторных проблем. 1)В ходе исследования было дано несколько определений чисел Каталана различными способами, рассмотрены их взаимосвязи. 2)Нами было подобрано, самостоятельно составлено и решено большое количество комбинаторных задач, в которых обнаруживаются числа Каталана и их свойства. Некоторые из задач приведены к общему случаю. 3)В данной работе мы показали ряд свойств комбинаторных структур, связанных с числами Каталана, сформулировали правило для построении инъекции перестановок Дональда Кнута в правильные скобочные структуры для n. Таким образом, цель работы достигнута. Анализируя различные источники литературы, мы пришли к выводу, что числа Каталана актуальны и очень популярны в современной математике. Они часто встречаются на математических олимпиадах. Хочется отметить, что данная тема требует очень серьезного внимания и является не до конца изученной, несмотря на большое количество публикаций. Мы видим перспективы дальнейшего исследования в данной области в доказательстве достаточного условия биекции для перестановок Кнута при n, а также в выявлении новых комбинаторных объектов и их свойств, связанных с замечательной последовательностью Каталана.

Библиографический список 1. Виленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика. – М.: ФИМА, МЦНМО, – 400 с. 2. Гарднер М. Числа Каталана. // Квант – с Деза Е. И. Специальные числа натурального ряда: Учебное пособие. – М.: Книжный дом «ЛИБРОКОМ», – 240 с. 4. Спивак А. Числа Каталана. // Квант – с Попов И. Н. Совершенные и дружественные числа: Учебное пособие. – Архангельск: Поморский университет, – 153 с. 6. Прасолов В. В. Задачи по алгебре, арифметике и анализу: Учебное пособие. - М.: МЦНМО, – 608 с. 7. Энциклопедия для детей. Т. 11. Математика/ Гл. ред. М. Аксенова. – М.: Аванта +, – 688 с. 8. Электронная энциклопедия «Большая энциклопедия Кирилла и Мефодия 2007» официальный сайт олимпиады МГУ «Покори Воробьёвы горы» (дата посещения ) Издательский дом «Первое сентября». Учебно-методическая газета «Математика» (дата посещения ) «Он-лайн энциклопедия целочисленных последовательностей» Н. Д. А. Слоэн (дата посещения ) Свободная энциклопедия «Википедия» (дата посещения ).

Спасибо за внимание!