Вход

Введение в комбинаторный анализ

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 276245
Дата создания 25 ноября 2014
Страниц 30
Мы сможем обработать ваш заказ 28 сентября в 12:00 [мск]
Файлы будут доступны для скачивания только после обработки заказа.
990руб.
КУПИТЬ

Описание

об основных понятиях, методах и проблемах комбинаторного анализа ...

Содержание

Введение……………………………………………………………………..3
1 Основные понятия комбинаторного анализа……………………………5
2 Формирование и развитие комбинаторного анализа……………………9
3 Проблемы комбинаторного анализа…………………………………….12
4 Методы комбинаторного анализа……………………………………….14
4.1 Метод производящих функции……………………………………..14
4.1.1 Элементарные производящие функции……………………….14
4.1.2 Экспоненциальные производящие функции………………….15
4.1.3 Производящие функции для известных последовательностей17
4.1.4 Производящие функции нескольких переменных……………19
4.2 Разбиения и размещения……………………………………………..21
4.3 Логические методы комбинаторного анализа……………………...24
5 Области применения комбинаторного анализа………………………..28
Заключение…………………………………………………………………29
Литература………………………………………………………………….30

Введение

Во все сферы человеческой деятельности проникла компьютерная техника, без нее человек уже не представляет жизни. В связи с этим пристальное внимание стали уделять дискретной математике, важной составной частью которой является комбинаторный анализ. Произошло стремительное включение комбинаторного анализа в русло современной математики, что связано не только с резким расширением области приложений, предмета исследований рассматриваемой дисциплины. Комбинаторные методы проникли в другие науки, в частности, теорию чисел, алгебру, теорию вероятностей, геометрию, теорию графов. Они стали активно использоваться в психологии, медицине, космической технике и радиосвязи.
Долгое время комбинаторика — оставалась на периферии математической науки. Интерес математиков к комбинаторному анализу усилился при появлении во второй половине XX века информатики и компьютерной техники, в связи с усилением роли дискретной математики. Этот интерес обусловлен также попытками математиков превратить комбинаторный анализ в составную часть магистрального направления современной математики. Все вышеизложенное определило актуальность курсовой работы ......

Фрагмент работы для ознакомления

Такие известные ученые как H.JI. Биггс, Е. Кно-блох, К.Р. Бирман проводили подобные исследования в этом направлении. Из отечественных трудов необходимо отметить работы К.А. Рыбникова, А.Е. Малых, Дж. Кутлумуратова. Элементы истории комбинаторики освещены J1.E. Майстровым, Б.В. Гнеденко. Среди литературы XIX столетия следует упомянуть исследования И. Тодхантера, Е. Нетто, В.Я. Буняковского. [24]История комбинаторного анализа постоянно находится в поле зрения ученых. Его развитие с древнейших времен дет настоящего времени, а также процесс формирования многочисленных разделов подробно освещены. Вместе с тем, при более глубоком исследовании этих вопросов обнаруживаются неизвестные ранее имена ученых, занимавшихся разработкой комбинаторной теории, отыскиваются проблемы, служившие истоками целых современных научных направлений. Проблемы комбинаторного анализаВ комбинаторном анализе изучаются вопросы о существовании и числе различных конфигураций, подчиненных тем или иным условиям, составляемых из конечного или счетного числа заданных объектов. Различают три типа проблем комбинаторного анализа. [22]1) Задачи о существовании и построении. В задачах такого рода интересуются, существует ли конфигурация частей конечного множества, обладающая некоторыми заданными свойствами, и если да, то, как ее построить. Например, существует ли такая система подмножеств (блоков) данного конечного множества, что любые два различных элемента множества встречаются вместе в этих блоках заданное число раз. Такие системы называют блок-схемами. При этом большую роль играют теоретико-числовые и алгебраические методы. Такие проблемы составляют содержание комбинаторики расположения. 2) Задачи о выборе. В задачах этого типа исследуются условия, при которых можно осуществить такой выбор подмножества или некоторой совокупности частей множества, чтобы удовлетворялись некоторые требования, носящие чаще всего характер оптимальности. При решении задач о выборе, наряду с чисто комбинаторными соображениями, также существенно применяется алгебраический аппарат. Вопросами подобного экстремального выбора занимается комбинаторная оптимизация. 3) Задачи на перечисление. В задачах такого типа речь идет о нахождении числа тех или иных конфигураций из элементов некоторого конечного множества. При этом мощность множества, как правило, представляет собой основной параметр задачи, а конкретные ее условия обычно выражаются также через те или иные числовые характеристики. Тем самым решение перечислительной задачи естественным образом оказывается связанным с изучением свойств числовых последовательностей, зависящих от нескольких натуральных параметров. Рассмотрение формального степенного ряда от одной или нескольких переменных (производящая функция), дает возможность представить в свернутом виде наиболее существенную информацию о числовых последовательностях, связанных с данной перечислительной задачей. Решением такого рода задач занимается перечислительная комбинаторика. Перечислительная комбинаторика является наиболее развитой ветвью современного комбинаторного анализа, имеющая разнообразные приложения. Эффективным средством решения перечислительных комбинаторных задач является метод производящих функций.Методы комбинаторного анализаМетод производящих функцииМетод производящих функций – математический прием, позволяющий сводить задачи из теории чисел, теории вероятностей и комбинаторики к задачам из анализа. [8] Применение производящих функций намного сокращает объем необходимых преобразований, позволяет унифицировать многие результаты и тем самым дает возможность охватить значительно больший круг вопросов. [22]Производящей функцией, или обычной производящей функцией, последовательности чиселa0, a1, …,an,…называется формальный рядAt=a0+a1t+a2t+…+ant+…, где t – формальная переменная. [18] При этом an=CoeftnA(t).По определению две производящие функции At=n=0∞antn,Bt=n=0∞bntn равны, если an=bn для n=0, 1, 2, …Элементарные производящие функцииЗаписывать производящие функции в виде ряда неудобно. Поэтому для некоторых элементарных и часто встречающихся функций используют сокращенную запись. (1+s)α=1+α1!s+α(α-1)2!s2+αα-1(α-2)3!s3+…, где n!=1∙2∙3∙…∙n и α – произвольное комплексное число.Коэффициент при sn в этой производящей функции называется числом сочетаний из α элементов по n и обозначается αn=αα-1…(α-n+1)n!.Это разложение называется бином Ньютона. [10]es=exps=1+α1!s+12!s2+13!s3+…ln11-s=s+12!s2+13!s3+…sins=s-13!s3+15!s5-…coss=1-12!s2+14!s4-…Экспоненциальная производящая функцияЭкспоненциальной производящей функцией последовательности a0, a1, …,an,… называется ряд Et=a0+ a1t1!+…+ antn!+…, где t - формальная переменная. При этом an=CoeftnE(t). [19]Аналогом обычной производящей функции с одной переменной служит несобственный интеграл At=0∞a(k)tkdk В таблице 1 указаны примеры обычных и экспоненциальных производящих функций для некоторых простых бесконечных последовательностей.Таблица 1 – Производящие функции для простых бесконечных последовательностейakAtE(t)akkk(k-1)k2nknn-1…(n-k+1)(1-at)-1t(1-t)-22t2(1-t)-3t(t+1)(1-t)-3(1+t)n_expat t exptt 2exptt(t+1)expt(1+t)nДля производящих функций вводится алгебра Коши, с операциями сложения, умножения, суперпозиции, подстановки, дифференцирования и интегрирования. [18]Обозначим производящие функции At, Bt,Ct, соответствующие последовательностям (ak), (bk),(ck).Тогда получаем следующие соотношения:Сумма ak=bkc0+bk-1c1+…+b1ck-1+b0ck, At=Bt+CtПроизведение ak=bk+ck, At=Bt∙CtПроизведение и сумма обладают свойствами коммутативности и ассоциативности.Производящая функция последовательности a0', a1', …an',…,обратной к последовательности a0, a1, …,an,…, определяется условием AtA't=1a0a0'=1,a1a0'+a0a1'=0,a21a0'+a1a1'+a0a2'=0 и т.д.Производящие функции для известных последовательностейСочетания с повторениями. С помощью производящих функций получим реккурентное соотношение для сочетаний с повторениями, а именно fn,k=fn,k-1+fn-1,k.Полагая fnt=k=0∞f(n,k)tk,приходим 1-tfnt=fn-1tили fnt=(1-t)-1fn-1t=(1-t)-2fn-2t=(1-t)-n. По условию f0t=1. Следовательно, с помощью биномиального разложения получаем, что fn,k=n+k-1k.Производящие функции подходят для решения рекуррентных соотношений.Геометрическая прогрессияПростейшая последовательность – это постоянная последовательность 1, 1, 1, … Производящая функция для нее имеет вид Gs=1+s+s2+s3+…Её несложно выразить через элементарные производящие функции.Умножим обе части на s, получимsGs=s+s2+s3+s4+…=Gs-1,откуда Gs=11-s.Возьмем произвольную последовательность вида a,ar2,ar3,ar4,…:Ga,rs=a+ars+ar2s2+ar3s3+ar4s4+…=a1+rs+rs2+rs3+…,откуда rsGa,rs=Ga,rs-a, тогда Ga,rs=a1-rs.Полученные выкладки представляют собой известный вывод формулы для суммы геометрической прогрессии. [10]Также через производящие функции можно записать числа Фибоначчи.Рассмотрим рекуррентное соотношение для чисел Фибоначчи:f0=0,f1=1,fn=fn-1+fn-2, n≫2Умножим каждую строчку на z0,z1, …,zn.z0∙f0=1∙0,z1∙f1=z∙1,zn∙fn=(fn-1+fn-2)zn∙, n≫2Складываем все строчки: f0+f1z+n=2∞fnzn=z+n=2∞fn-1zn+n=2∞fn-2zn.Приводим к замкнутому виду: Gz=z+n=2∞fn-1zn+n=2∞fn-2zn,Gz=z+zn=1∞fnzn+z2n=0∞fnzn,Gz=z+zGz-f0+z2Gz,Gz=z+zG(z)+z2Gz,Gz=z1-z-z2 – производящая функция для чисел Фибоначчи.Производящие функции нескольких переменных.Производящие функции от двух переменных отвечают двухиндексными последовательностями. Такие последовательности удобно записывать в виде треугольника.Треугольник Паскаля (рис. 3) Элементы этого треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломаных, составленных из векторов единичной длины двух видов: идущих вправо-вниз и идущих влево-вниз.Рисунок 3 – Треугольник Паскаля и пути, которые он перечисляетЧисла, стоящие в треугольнике Паскаля, - это биномиальные коэффициенты cn,k=nk.Докажем методом индукции.Предположим, что числа в n-й строке треугольника совпадают с коэффициентами разложения многочлена (1+s)n.Число различных путей, ведущих в точку (n+1,k), равно сумме путей, ведущих в точку (n,k-1), и числа путей, ведущих в точку (n,k), cn+1,k=cn,k-1+cn,k. Поэтому число cn+1,k совпадает с коэффициентом при skв многочлене 1+s∙1+sn=1+sn+1.Рассмотрим производящую функцию сопоставленную треугольнику Паскаля следующим образом: n,k=0∞cn,kxkyn=n,k=0∞nkxkyn=n=0∞(k=0∞nkxk)yn=n,k=0∞1+xnyn=11-y-xy.Многочлены БернуллиВведем на пространстве многочленов операцию усреднения, положив Afx=xx+1ftdt.Эта операция переводит многочлены в многочлены: она линейна, т.е. A(a1f1+a2f2)=a1Af1+a2A(f2)для любых постоянных a1, a2 и любых многочленов f1,f2, а ее значение на мономе xn равно Ax=x+1n+1-xn+1n+1=xn+…, где многоточие обозначает слагаемые, степени которых меньше n. Преобразование А переводит пространство многочленов степени не выше n в себя, поэтому является линейным оператором в этом пространстве. При усреднении степень многочлена сохраняется.Многочленом Бернулли степени n называется многочлен Bn(x), результатом усреднения которого служит моном xn, т.е. Bnx=A-1xn.Из лекцийПосчитаем первые многочлены Бернулли.B0x=1;B1x=x-12;B2x=x2-x+16;B3x=x3-32x2+16x;B4x=x4-2x3+x2-130.Теорема 4. Экспоненциальная производящая функция для многочленов Бернулли имеет вид Bx, s=n=0∞Bnxsnn!=ses-1esx.Доказательство. Применим операцию усреднения к левой и правым частям равенства.С одной стороны, имеем ABx, s=n=0∞A(Bnx)snn!=n=0∞xnsnn!=esx.C другой стороны, имеемAses-1esx=ses-1A(esx)=ses-11s(esx+1-esx)=esx.Теорема доказана.Определим числа Бернулли как значения многочленов Бернулли в нуле: 1, -12, 0, 16, -130, 0, 142, 0, - 130, 0, 566,0, - 6912730, … из лекцийРазбиения и размещенияПроизводящая функция для числа разложений на k слагаемых имеет видBks=(1-s)-kРазбиением числа n называется класс эквивалентности разложений, ни одно из слагаемых в которых не равно нулю. При этом два разложения считаются эквивалентными, если одно можно получить из другого перестановкой слагаемых.Рассмотрим разбиения маленьких чисел:n=1 1n=2 2=1+1n=33=2+1=1+1+1n=44=3+1=2+2=2+1+1=1+1+1+1n=55=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1Каждое разбиение к таблице записано в порядке убывания слагаемых. В таком виде легко сравнивать два разбиения.Обозначим число разбиений числа n через pn, получим таблицу начальных значений последовательности pn:n012345678pn11235711522Найдем производящую функцию для последовательности pn. Для этого посчитаем число разбиений на части, удовлетворяющие некоторым ограничениям.Пусть P1(s) – производящая функция для числа разбиений числа n на части, равные 1. Для каждого числа такое разбиение единственно, поэтомуP1s=1+s+s2+s3+…=11-s.Число разбиений числа n на части, равные 2, равно 1 для нечетных n и равно нулю в противном случае. Поэтому P2s=1+s2+s4+s6+…=11-s2.Число разбиений n на части, равные трем, соответствует производящая функция P1sP2s=11-s(1-s2).Теорема 5. Производящая функция для числа разбиений числа n имеет вид P(s)=11-s1-s21-s31-s4…. [10]Теперь можем выписать бесконечные произведения и для разбиений с различными ограничениями.Пример 4. Число разбиений на различные слагаемые дается производящей функцией 1-s1-s21-s31-s4…, производящая функция для разбиений на различные нечетные слагаемые имеет вид 11-s1-s31-s51-s7…, и т.д.Разбиение тесно связано с алгеброй многочленов. Будем считать, что переменной xi приписан вес i и что при перемножении переменных их веса складываются. Подсчитаем число мономов веса n.При n=1 моном всего один – это моном x1.При n=2 имеем два монома веса n – это x12 и x2.При n=3 число мономов равно трем – это x13 ,x1x2и x3.Таким образом, число мономов веса n равно pn.Правило. Число слагаемых i в разбиении равно степени вхождения переменной xi в моном. Размещение – это разбиение совокупности элементов на множество классов. [17]Более конкретно под этим термином понимают распределение объектов данной совокупности по ячейкам. Приведем несколько утверждений. Число способов размещений n одинаковых объектов по m различным ячейкам равноn+m-1n=n+m-1m-1.Число способов размещения n одинаковых объектов по m различным ячейкам при отсутствии пустых ячеек равно n-1m-1.Порядок объектов, вкладываемых в одну ячейку, может учитываться, а может и не учитываться.

Список литературы

ЛИТЕРАТУРА
1. Айгнер, М. Комбинаторная теория: Пер. с англ. [Текст]/ М. Айгнер. – М.: Мир, 1982. – 558 с.
2. Баранов, В. И. Экстремальные комбинаторные задачи и их приложения [Текст]/ В. Баранов, Б. Стечкин. – М.: Физматлит. 2004.
3. Береснев, В. Л. Дискретные задачи размещения и полиномы от булевых переменных [Текст]/ В. Л. Береснев. – Новосибирск: Издательство Института математики. 2005.
4. Виленкин, Н. Я. Популярная комбинаторика [Текст]/ Н. Я. Виленкин. – М.: Наука, 1975. - 204 с.
5. Виноградов, И. М. Математическая энциклопедия [Текст]/ И. М. Виноградов. – М.: Советская энциклопедия, 1977-1985. - 5766 с.
6. Ежов, И. И. Элементы комбинаторики [Текст]/ И. И. Ежов, А. В. Скороход, М. И. Ядренко. – М.: Наука, 1977.
7. Ерусалимский, Я. М. Дискретная математика: теория, задачи, приложения[Текст]/ Я. М. Ерусалимский. – М.: Вузовская книга, 1999.
8. Зарипова, Э.Р. Лекции по дискретной математике. Часть I. Комбинаторика [Учеб. Пособие.]: Э. Р. Зарипова, М. Г. Кокотчикова. – М.: РУДН, 2012. – 78 с.
9. Кофман, А. Введение в прикладную комбинаторику: Пер. с фран. [Текст]/ А. Кофман. – М.: Наука. Гл. ред. Физ.-мат. лит., 1975. – 480 с.
10. Ландо, С. К. Лекции о производящих функциях [Текст]/ С. К. Ландо. 3-е изд., испр. – М.: МЦНМО, 2007. – 144 с.
11. Леонтьев, В. К. Избранные задачи комбинаторного анализа [Текст]/ В. К. Леонтьев. – М.: Издательство МГТУ им. Н.Э. Баумана. 2001.
12. Липский, В. Комбинаторика для программистов [Текст]/ В. Липский. - М.: Мир, 1988.
13. Маршалл, Х. Комбинаторика [Текст]/ Холл Маршал. - М.: Мир, 1970.
14. Нефедов, В. Н. Курс дискретной математики [Текст]/ В. Нефедов, В. Осипова. - М.: Изд-во МАИ, 1992.
15. Ожегов, С. И. Толковый словарь русского языка [Текст]/ С. И. Ожегов; под ред. Проф. Л. И. Скворцова. – 26-е изд., испр. и доп. М.: Оникс : Мир и образование, 2009. – 736 с.
16. Окулов, С. М. 100 задач по информатике [Текст]/ С. М. Окулов, А. О. Пестов. – Киров: Изд-во ВГПУ, 2000. – 272 с.
17. Риордан, Дж. Введение в комбинаторный анализ [Текст]/ Дж. Риордан. - М.: ИЛ, 1963.
18. Рыбников, К. А. Введение в комбинаторный анализ [Текст]/ К. А. Рыбников. - М.: Изд-во МГУ, 1972.
19. Рыбников, К. А. Комбинаторный анализ. Задачи и упражнения [Текст]/ К. А. Рыбников. - М.: Наука, 1982.
20. Савченко, Г. Б. Введение в комбинаторный анализ [Учебно-методическое пособие ]: Г. Б. Савченко, Н. А. Ярцева. – Воронеж, 2005. – 19 с.
21. Сачков, В. Н. Введение в комбинаторные методы дискретной математики [Текст]/ В. Н. Сачков. – М.: Наука. Гл. ред. Физ.-мат. лит., 1982. – 384 с.
22. Соловьева, Л. А. Комбинаторные числа и взвешенные траектории на решетках [Текст]: дис. … канд. физ.-мат. наук/ Л. А. Соловьева. – Иркутск, 2007. – 130 с.
23. Тараканов, В. Е. Комбинаторные задачи и (0,1)-матрицы [Текст]/ В. Е. Тараканов. - М.: Наука, 1985.
24. Угольникова, О. Д. Формирование и развитие комбинаторного анализа в XVIII веке [Текст]: дис. … канд. физ.-мат. наук/ О. Д. Угольникова. – Пермь, 2004. – 151 с.
25. Яблонский, С. В. Введение в дискретную математику: Учебное пособие для ВУЗов [Текст]/ С. В. Яблонский. – М.: Высшая школа, 2001.
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
© Рефератбанк, 2002 - 2020