Числа каталана курсовая работа

Числа каталана курсовая работа

Математика 3/. Числа Каталана

Жумиров Б. А., Жумирова Ж. Ж.

Магистрант Инновационного Евразийского университета, Казахстан

Числа Каталана в теории вероятности

Числа Каталана — числовая последовательность, встречающаяся в удивительном числе комбинаторных задач. Эта последовательность названа в честь бельгийского математика Каталана , жившего в 19 веке.

Первые несколько чисел Каталана (начиная с нулевого):

1, 1, 2, 5, 14, 42, 132, 429, 1430 .

Числа Каталана встречаются в большом количестве задач комбинаторики. Имеется две формулы для чисел Каталана: рекуррентная и аналитическая.

Аналитическая формула: , здесь через обозначен, как обычно, биномиальный коэффициент.

Задача о человеке в казино

Немного подумав, мы придумали задачу, которая включает числа Каталана и теорию вероятностей и надеемся, что решение таких видов задач понадобятся для решения аналогичных задач в разных сферах математики.

Человек пришел в казино с одним долларом. Ставки в казино равны одному доллару. И вероятность выигрыша и проигрыша 50 на 50. При выигрыше дается один доллар, при проигрыше же отнимается. Подсчитать вероятность того, что человек через n количество ставок будет оставаться при деньгах (т. е. его деньги не будут равняться нулю, иначе он не сможет играть дальше).

Решение: Очевидно, что при , у него вероятность QUOTE , либо выиграет, либо проиграет.

Известна формула вероятностей: .

Где P ( A ) = количество успешных событий , а P ( U ) = количество всех событий . Очевидно, что P ( U ) при определенных n равно , то есть, в каждой игре есть по два варианта либо выиграет, либо проиграет. Далее, мы будем подсчитывать P ( A ) для определенных n . Выразим выигрышей через +, а проигрышей .

Итак, подсчитаем P ( A ) для определенных n . Поначалу, подсчитаем собственноручно для малых значений.

Логика следующих вычислений такова, исход первой игры не может быть минусом, потому что при противном он будет без денег уже при первой игре. И количество минусов не должно превысить плюсы, потому что при обратном у человека не останеться денег. Для 2 игр получим следующие правильные результаты при котором человек будет оставаться при деньгах:

Для 3 игр получим следующие результаты:

Для 4 игр получим следующие результаты:

Для 5 игр получим следующие результаты:

Как понятно , при нечетном количестве игр количество плюсов всегда на один превышает минусов. Так что в следующем ряду с каждого крайнего элемента потянуться два варианта, и это значить, что количество вариантов умножиться на два. Следовательно , .

А как поведет себя ряды когда будут переходит с четного на нечетное?

При четном количестве, очевидно что два варианта выйдут с тех вариантов в котором количество плюсов больше, чем количество минусов. А с тех вариантов, где количество плюсов равно минусам потянется один вариант на (+) , потому что при обратном, если пот янется к (-), то количества минусов станет на один больше чем количества плюсов. А это не соответсвует условию, у человека больше проигрышей чем выигрышей, и это светит банкротом.

Значит, , где А — является количеством вариантов при одинаковых количествах выигрышей и проигрышей . Теперь нам надо подсчитать их.

Рассмотрим для .

Существует единственный вариант:

Рассмотрим для .

1) ++— ; 2) +-+- . Как видим , существует два варианта.

Рассмотрим для .

Существует 5 вариантов.

И тут можно заметить что « + » и « – » подобны расстановкам правильных скобок. И тут определяем что для будет С4 – четвертое число Каталана – 14. Д ля будет 42 , для будет 132 и т.д. Следовательно в выражений , X равняется С n — n — ое число Каталана.

Читайте также:  Как найти рекламу которую показывали по телевизору

Далее можно вывести следующий алгоритм и получить формулу через сумму:

C ледовательно: , где — это количество вариантов при которых игрок остаётся в казино , числа Каталана и [ f ( x )] – является целым значением от f ( x ).

Теперь подсчитав количество вариантов мы можем легко подсчитывать вероятности для маленьких значений n . Но можем определить и для больших n при помощи разных языков программирования.

Подсчитаем какова вероятность оставаться при деньгах после пяти игр?

Решение:

Примерно 31.25% вероятности остаться в казино с деньгами.

Подсчитаем какова вероятность оставаться при деньгах после десяти игр?

Решение:

Примерно 24.61% вероятности что человек останется в казино.

Мы можем решать аналогичные задания с использованием данной формулы. Мы будем продолжать исследование в этой сфере и хотим выявить использование чисел Каталана еще в разных сферах.

Заключение : используя формулы чисел Каталана, можно решить более трудные задачи по алгебре.

4. Дискретная Математика и комбинаторика. Дж. Андерсон 2003 г.

Материал из Википедии — свободной энциклопедии

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Suggest as cover photo

Would you like to suggest this photo as the cover photo for this article?

Thank you for helping!

Your input will affect cover photo selection, along with input from other users.

Содержание

Числа Каталана [ править ]

Определение:
Числа Каталана — последовательность чисел, выражающих:

  • количество не изоморфных упорядоченных бинарных деревьев с корнем и [math] n + 1 [/math] листьями
  • количество способов соединения [math] 2n [/math] точек на окружности [math] n [/math] не пересекающимися хордами
  • количество триангуляций выпуклого [math] n [/math] -угольника
  • количество способов полностью разделить скобками [math] n + 1 [/math] множитель
  • количество корректных скобочных последовательностей, состоящих из [math] n [/math] открывающих и [math] n [/math] закрывающих скобок
  • количество таблиц Юнга размером [math]2n[/math]
  • количество монотонных путей в квадрате размером [math]n imes n[/math] , не пересекающих диагональ
  • количество способов расставить скобки в произведении [math]n[/math] множителей
  • количество способов заполнить лестницу ширины и высоты [math]n[/math] прямоугольниками

и так далее

Первые несколько чисел Каталана:

[math] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ldots [/math]

Формулы вычисления чисел Каталана [ править ]

Рекуррентная формула [ править ]

[math]C_n = sumlimits_^ C_i C_ [/math]

Доказательство [ править ]

Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Пусть [math]X[/math] — произвольная правильная скобочная последовательность длины [math]2n[/math] . Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность [math]X[/math] в виде: [math]X = (A)B[/math] , где [math]A[/math] и [math]B[/math] — тоже правильные скобочные последовательности. Если длина последовательности [math]A[/math] равна [math]2k[/math] , то последовательность [math]A[/math] можно составить [math]C_k[/math] способами. Тогда длина последовательности [math]B[/math] равна [math]2(n — k — 1)[/math] и последовательность [math]B[/math] можно составить [math]C_[/math] способами. Комбинация любого способа составить последовательность [math]A[/math] с любым способом составить последовательность [math]B[/math] даст новую последовательность [math]X[/math] , а величина [math]k[/math] может меняться от [math]0[/math] до [math]n — 1[/math] . Получили рекуррентное соотношение: [math]C_n = C_0 C_ + C_1 C_ + ldots + C_ C_0 [/math] . Так как [math]C_0 = 1[/math] , то последовательность совпадает с числами Каталана.

Аналитическая формула [ править ]

[math] C_n = dfrac<1> dbinom <2n> [/math]

Доказательство [ править ]

Правильной скобочной структуре из [math]n[/math] открывающих и [math]n[/math] закрывающих скобок мы поставим в соответствие путь в квадрате [math][0, n]×[0, n][/math] . Путь начинается в точке [math](0,0)[/math] и заканчивается в точке [math](n, n)[/math] . Открывающей скобке мы сопоставляем горизонтальный отрезок длины [math]1[/math] , а закрывающей — вертикальный. Если путь сопоставлен правильной структуре, то ни одна его точка не может лежать выше главной диагонали квадрата. Обратно, такому пути ("правильному пути") сопоставляется правильная скобочная структура. Геометрическое представление правильных скобочных структур позволяет найти выражение для чисел Каталана.

Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке [math] (0, -1) [/math] , заканчивается в точке [math] (n, n-1) [/math] и не имеет общих точек с прямой [math] y = x [/math] — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки [math] (0, -1) [/math] в точку [math] (n, n-1) [/math] . Длина такого пути равна [math]2n[/math] и он содержит [math]n[/math] вертикальных сегментов и [math]n[/math] горизонтальных. Количество всех таких путей равно числу способов выбрать [math]n[/math] вертикальных сегментов из общего числа [math]2n[/math] сегментов, т.е. равно [math] dbinom <2n> [/math] .

Рассмотрим неправильный путь и его первую точку на прямой [math] y = x [/math] (точка [math]A[/math] ). Отрезок пути от точки [math](0, -1)[/math] до точки [math]A[/math] заменим симметричным относительно прямой [math]y = x[/math] . Мы получим путь длины [math]2n[/math] , идущий из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] (Смотри рис.).

Такой путь обязательно пересекает прямую [math] y = x [/math] . Обратно, пусть нам дан путь длины [math] 2n [/math] из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] и пусть [math] A [/math] — первая точка этого пути, лежащая на прямой [math]y = x[/math] . Заменив участок пути от точки [math](-1, 0)[/math] до точки [math]A[/math] на симметричный относительно прямой [math]y = x[/math] , мы получим неправильный путь из точки [math](0, -1)[/math] в точку [math](n, n-1)[/math] . Следовательно, неправильных путей из точки [math](0, -1)[/math] в точку [math](n, n-1)[/math] столько же, сколько путей из точки [math](-1, 0)[/math] в точку [math](n, n-1)[/math] . Такой путь длины содержит [math]n+1[/math] горизонтальных и [math]n-1[/math] вертикальных участков. Поэтому, количество таких путей равно [math] dbinom <2n> [/math] . Значит, количество правильных путей (т.е. число Каталана [math]C_n[/math] ) равно

Задача разбиения выпуклого [math] n [/math] —угольника на треугольники не пересекающимися диагоналями [ править ]

Доказательство [ править ]

Пусть [math]t_n[/math] — число триангуляций выпуклого [math] (n + 2) [/math] -угольника при [math] n geqslant 1 [/math] . Положим [math] t_0 = 1 [/math] . Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне [math]01[/math] (см. рис.).

Пусть [math]k[/math] — номер третьей вершины этого треугольника. Выделенный треугольник разбивает [math](n + 2)[/math] — угольник на [math]k[/math] — угольник и [math](n-k+3)[/math] — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций [math]k[/math] -угольника и [math](n-k+3)[/math] — угольника. Наоборот, каждая пара триангуляций [math]k[/math] — угольника и [math](n-k+3)[/math] — угольника определяет триангуляцию исходного многоугольника. Поэтому [math]t_ = t_0 t_n + t_1 t_ + ldots + t_n t_0 [/math] и поскольку [math]t_0 = 1[/math] , последовательность чисел [math]t_n[/math] совпадает с последовательностью Каталана.

Пример [ править ]

Ответ на задачу при [math] n = 3 [/math] тривиален: никаких диагоналей проводить не надо. В четырёхугольнике можно провести любую из двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две диагонали, [math] 5 [/math] способов. При [math] n = 6 [/math] — первый не вполне очевидный ответ: [math] 14 [/math] способов (см. рис.); чтобы не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых к ней примыкают соответственно треугольники [math] BCA, BCF, BCE [/math] и [math] BCD [/math] .

Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем [math]5[/math] разных случаев. В первом и последнем из них количество разбиений равно [math]14[/math] , ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем [math]2 cdot 2 = 4[/math] варианта. Итак, семиугольник можно разбить всего [math] 14 + 5 + 2 cdot 2 + 5 + 14 = 42 [/math] способами. Рассматривая восьмиугольник, аналогично получаем [math] 42 + 14 + 2 cdot 5 + 5 cdot 2 + 14 + 42 = 132 [/math] способа.Такие вычисления можно проводить и дальше.

Подсчет чисел Каталана [ править ]

Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится [math]O(n)[/math] памяти и [math]O(n^2)[/math] времени. За [math]O(n)[/math] времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:

Вычисление производящей функции чисел Каталана [ править ]

[math] = dfrac<(-1)^> <2k — 1>cdot dfrac<(2k)!> <2^k cdot k! cdot 2^kcdot k!>= dfrac<(-1)^> <(2k — 1) cdot 2^k cdot 2^k>cdot dfrac<(2k)!>= dfrac<(-1)^> <(2k — 1) cdot 4^k>dbinom<2k>[/math]

Лемма:
[math]dbinom<frac<1><2>> = dfrac<(-1)^> <(2k — 1) cdot 4^k>cdot dbinom<2k> [/math]
Доказательство:
[math] riangleright[/math]
[math] riangleleft[/math]
Задача:
Вычислить производящую функцию чисел Каталана

Пусть мы имеем последовательность чисел Каталана [math](C_0, C_1, C_2, ldots)[/math] .

Будем искать её производящую функцию в виде [math]G(z) = sumlimits_^ <infty>C_n cdot z^n[/math]

Как известно, рекуррентное соотношение для чисел Каталана имеет вид

Домножаем [math]C_n[/math] на [math]z^n[/math] , получая

Суммируя [math]C_n z^n[/math] по всем [math]n[/math] от [math]0[/math] до [math]infty[/math] , получаем:

[math]G(z) = sumlimits_^ <infty>C_n z^n = C_0 z^0 + sumlimits_^<infty>z^n sumlimits_^ C_k C_ = C_0 + sumlimits_^<infty>z^n sumlimits_^ C_k C_ = 1 + sumlimits_^<infty>z^n sumlimits_^ C_k C_[/math] (так как [math]C_0 = 1[/math] по определению чисел Каталана).

Получили, что [math]G(z) = 1 + sumlimits_^<infty>z^n sumlimits_^ C_k C_

Распишем произведение [math]G(z) cdot G(z)[/math] по определению произведения формальных степенных рядов.

[math]G(z) cdot G(z) = (sumlimits_^ <infty>C_n z^n) cdot (sumlimits_^ <infty>C_n z^n) = sumlimits_^<infty>z^n sumlimits_^ C_k C_[/math]

В последнем выражении выполним сдвиг индексации, положив [math]n’ = n + 1[/math] . Тогда имеем: [math]n = n’ — 1, n = 0 Rightarrow n’ = 1[/math] . Кроме того, [math]z^n = z^

Ссылка на основную публикацию
Четкие аватарки для стима
Помощь в выборе аватарки Не знаете, какими могут быть аватарки для стима и какую из них лучше выбрать? Где искать...
Чаша для мультиварки redmond rmc 250
Данный товар недоступен для доставки в Ваш регион Мы всегда стремимся к лучшему, чтобы радовать своих покупателей самыми выгодными ценами....
Чего трубку не берешь
Мне не нравиться когда ты не берешь трубку или сбрасываешь вызов. Если мне не изменяет память, я об этом тебе...
Четырехугольник можно вписать в окружность если
Вписанный четырехугольник — четырехугольник, все вершины которого лежат на одной окружности. Очевидно, эта окружность будет называться описанной вокруг четырехугольника. Описанный...
Adblock detector