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

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

Введение……………………………………………………………………..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.Порядок объектов, вкладываемых в одну ячейку, может учитываться, а может и не учитываться.