Бесплатно скачать, заказать диплом, курсовую, диссертацию Комбинаторные методы перечисления плоский корневык деревьев и путей на реигеткан

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Комбинаторные методы перечисления плоский корневык деревьев и путей на реигеткан

Количество страниц	83

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23540.doc

Содержание	Содержание Оглавление Введение...3 Глава 1. Комбинаторные числа и полиномы...18 § IЛ .Общая схема построения комбинаторных чисел класса отобраэюепип...IS § 1.2. Комбинаторные полиномы разбиений...23 § 1.3. Комбинаторная схема распространения последовательности до матрицы...28 § 1.4. Обобщенные триномиальные коэффициенты...31 §1.5. Обобщения треугольника Паскаля...34 §1.6. Обобщенные числа Каталана...35 § 1.7. Обобщенные числа Шредера...41 Глава 2. Перечисление плоских корневых деревьев...46 §2.1. Плоские корневые деревья...46 § 2.2. Помеченные плоские корневые деревья Шредера...47 2.2.1. Классификация по количеству всех вершин в первом слое...49 2.2.2. Классификация по количеству внутренних вершин...49 § 2.3. Плоские непомеченные корневые деревьяКаталана...53 2.3.1. Классификация по количеству всех вершин в первом слое...55 2.3.2. Классификация по количеству внутренних вершин...57 2.3.3. Классификация по высоте...60 § 2.4. Плоские корневые деревья Моцкииа с петлями...64 2.4.1. Классификация по числу петель и ребер, выходящих из корня...66 2.4.3. Классификация по числу петель...69 2.4.4. Классификация по высоте...69 Глава 3. Перечисление путей на решетках...71 §3.1. Пути Мак-Магоиа...71 §3.2. Пути Моцкина...72 §3.3. Пути Дика...77 §3.4. Числа Шредера Rn и пути па плоскости...78 Заключение...82 Синеок литературы...83 Введение В настоящее время в связи с развитием кибернетики и близких к ней разделов науки, существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности. Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1,2,7,8,10,34,35]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными. Настоящая диссертационная работа посвящена изучению комбинаторных чисел и полиномов, возникающих при решении перечислителышх задач, т.е. задач, в которых необходимо определять число комбинаторных конфигураций данного класса или давать их классификацию, связанную с перечислением. В работе разрабатываются комбинаторные методы перечисления плоских корневых деревьев и путей на решётках. При решении указанных задач использованы комбинаторные полиномы - однородные полиномы Белла и Платонова, а также как известные комбинаторные числа, так и новые, введённые автором данной диссертационной работы. Диссертация состоит из трёх глав, которые разбиты на 15 параграфов. В главе второй параграфы разбиваются на пункты. Кратко охарактеризуем содержание отдельных глав диссертации. В первой главе рассматриваются арифметические треугольники комбинаторного происхождения. Идеи построения и применения арифметических треугольников и пирамид, родственных широко известному треугольнику Паскаля, высказывались многими авторами на протяжении ряда веков. В 1665г. вышел в свет «Трактат об арифметическом треугольнике» Блеза Паскаля, посвященный наиболее изящной численной схеме во всей математике - треугольнику Паскаля (см. [37]). В книгах [4,17] изложены классические и новые арифметические, геометрические и комбинаторные свойства арифметических треугольников и пирамид Паскаля. В монографии [17], в частности, рассмотрены треугольники, построение которых связано с известными последовательностями одпопараметрических комбинаторных чисел: треугольники Люка, Фибоначчи, Каталана, Моцкина, Трибоначчи (см»-работы [5,39, 42, 46, 47, 50, 52, 53]) и др., а также треугольники, построенные из известных двупараметрических комбинаторных чисел: Стирлинга первого и второго рода, Лаха, присоединённых чисел Стирлинга первого и второго рода и др. Элементы упомянутых выше арифметических треугольников определяются в соответствии с рекуррентными уравнениями и начальными условиями. В данной диссертационной работе получила развитие идея М.Л. Платонова [30] распространения последовательности одиопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел. Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств Л - и Я—полиномов. В параграфе 1.1 приводится описание общей схемы построения комбинаторных чисел класса отображений. В параграфе 1.2 изучаются комбинаторные полиномы разбиений -однородные полиномы Белла и Платонова. Понятие «полипом разбиения» -полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса - введено Беллом. Один из таких полипомов, связанный с производными от композиции функций, Риордап назвал полиномом Белла. Различные множества полиномов разбиений изучаются в [12,17,18,28,31,32]. Однородные полиномы Белла Л (п, к; g) имеют вид ,"'[rMi\r] , «,>1, к<п, п,к /=\| где gz=(g\,g2-l---) ~ формальные переменные, а суммирование ведется по всем таким наборам (гх,г2,... ,гпк+[) неотрицательных чисел, что г, + 2г2 +... + {п-к + 1)/;.,+1 = п, гх + г2 +... + гп_ш = к, т.е. по всем разбиениям натурального числа п на к натуральных слагаемых. Полиномы Платонова B(n,k;g), сопряженные с однородными полиномами Белла А(п, к; g), имеют вид 2п-2к,п-к /=1 п>2, \<к<п-\, где суммирование ведется по всем разбиениям натурального числа 2п-2к на п-к натуральных слагаемых. Дополнительно полагаем B(n,n;g) = g;n, n>\. Переменные ?/>' — !, участвующие в построении А(п, к; g) и В(п, к; g), в частности, могут считаться совпадающими с последовательными производными некоторой функции. Пусть g(t) = 2_.—i—• Если существует ряд gO') = Z^f~' такой, что g(g(t)) = t, то для g = (gl,g2-) и g = (g\,g2>-) имеет место утверждение. Утверждение 1.2 [28]. Между производными взаимно-обратных функций, если все они существуют, выполняются соотношения В(п9 г; g—) = А О, г; g-), п>\, 1 < г < /?. В параграфе 1.3 излагается разработанная комбинаторная схема распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических чисел. Идея этой схемы основана на применении однородных Л-полиномов Белла и сопряжённых с ними /^-полиномов Платонова. Использование известных свойств А— и В— полиномов (см., например, [17, 28, 29]), позволяет получить арифметические треугольники, связанные с заданной последовательностью чисел, и распространить на все члены соответствующих нижних треугольных матриц перечислительную интерпретацию, первоначально установленную для элементов их первого столбца. Получены новые комбинаторные объекты, названные обобщенными числами, ряд свойств для которых устанавливается исходя из свойств А — и 5—полиномов. Опираясь на свойства А - и В — полиномов, изучены комбинаторные и аналитические свойства полученных чисел. В параграфе 1.4 рассматриваются обобщенные триномиальные коэффициенты, которые получаются исходя из общей схемы построения комбинаторных чисел. В параграфе 1.5 приведены основные понятия и некоторые свойства обобщенного треугольника Паскаля и обобщенной пирамиды Паскаля [4, 9, 17]. Показано, что полученные в работе новые комбинаторные числа, являются частными случаями элементов обобщенного треугольника Паскаля или обобщенной пирамиды Паскаля. В параграфе 1.6. вводятся и изучаются новые комбинаторные объекты - числа Рпк, названные обобщенными числами Каталано, и числа Гпк., сопряженные с числами Рпк. Число неассоциативных произведений из п фиксированных, линейно упорядоченных сомножителей совпадает с Сп, где Сп - числа Каталана 1 (2п , п>0. С„ п + 1 уп ) Числа Каталана достаточно хорошо изучены (см., например, [1,2,7,8,34,35,41-44,47-49,51,52,55,56]). Известно, что производящая функция смещенных чисел Каталана задается соотношением 4^ .С, Р, = 1, Р.=С_„ »>2. n=i Следовательно, обратная ей функция равна t(ll) = U — U2 . Пусть И„1 .[M{y\tsQ\M п\ п\ Рп=Р»х =-A[n,l-,t(u)][l=0=-B[n,\ т п\ Распространяем указанные последовательности до матриц, полагая ?«k =-A[n,k;u(t)]l=0=-B[n,k;t(u)]tl=Q и Рпк = -^ А\п, к', t(u)]ll=0 = ± В[п, к; u(t)](=0 m Для чисел Рпк получено явное выражение к (Ъг-к- >2 \<к<п-\. р _ п—к уп Теорема 1.1. Для чисел Рпк справедливы следующие соотношения: 1 пк ~ л п,к + \ ^ л п-\,к-\ п-\ пк / 1 I/-I,;' i=k-\ р = Гпк\ к ™Л к+\ гтк>2, п>к-\9 Рц=19 РпЛ=Раа=Он, m?L. Числа Рпк, названные обобщенными числами Каталана, имеют следующую перечислительную Ш1терпретацию: Рпк - число сумм произведений, состоящих из к слагаемых, содержащих в совокупности п фиксированных множителей, взятых из алгебры с неассоциативным умножением. Числа Рпк, сопряженные с числами Рпк, имеют следующий явный вид: 'к п — к V и связаны с числами Фибоначчи соотношением: п Р \ — F Г пк — 1 п пк к = I Они имеют следующую перечислительную интерпретацию: - число представлений п в виде композиции к слагаемых, каждое из которых или 1, или 2. В параграфе 1.7 изучаются обобщенные числа Шредера Sllk. Обычные числа Шредера Sn и их интерпретация широко известны (см., например, [39, 45, 46, 50, 53, 56]). Для чисел Sl]fc приводятся рекуррентное соотношение и формулы, связывающие присоединенные числа Стирлинга второго рода и числа сопряжённые с обобщенными числами Шредера. Результаты автора, изложенные в первой главе, опубликованы в работах [20, 22, 36]. Использованные в главе результаты принадлежат лично автору. Вторая глава посвящена приложениям изучаемых комбинаторных объектов при исследовании некоторых свойств перечисления определённых классов плоских корневых деревьев. С точки зрения классической теории графов деревья — малопривлекательный объект для теоретических исследований; в монографиях по теории графов (см., например, [3, 11, 25, 38]) им редко отводится больше одной главы, однако совсем иное отношение к деревьям в прикладной теории графов. Они играют важную роль в программировании, теории информационных систем, теоретической физике, химии, могут быть использованы в качестве модели описания структур данных, встречаются в биологических задачах, относящимся к деревьям эволюции (см., например, работы [6, 11, 13]). Для изучения деревьев широко используются самые различные методы. Так метод ветвящихся случайных процессов применяется при изучении графов, являющихся деревьями с помеченными вершинами [15, 16], и других видов деревьев [26, 27]. В монографии [13] предложен новый метод классификации помеченных графов (древесная классификация) и основанный на ней новый метод исследования степенных рядов. Автором данной диссертации в работах [20, 21, 22] предложен метод классификации плоских корневых деревьев по разным признакам, в качестве последних рассмотрены: а) степень корня (количество всех вершин в первом слое); б) количество внутренних вершин; в) высота. В данной работе представлена выборка наиболее известных, на наш взгляд, к настоящему моменту числовых последовательностей, связанных с плоскими корневыми деревьями. Надеемся, что она достаточно представительна т.к. отражает три основных типа плоских корневых деревьев: помеченные (последовательность Шредера), с петлями (последовательность Моцкина) и непомеченные (последовательность Каталана). В соответствии с предложенной классификацией получены новые комбинаторные числа, исследованы их свойства и указаны перечислительные интерпретации. В параграфе 2.1 приведены некоторые основные понятия теории графов, используемые в работе. В параграфе 2.2 рассмотрены плоские помеченные корневые деревья Шредера D. Каждому шредериану CeS(N), состоящему из к блоков, ставится в соответствие помеченное корневое дерево D с п висячими вершинами, построенное по определенному правилу. На основе предложенной схемы получены новые комбинаторные объекты: 1) обобщенные числа Шредера Snk, где Snk - число корневых деревьев D, содержащих ровно к вершин в первом слое; 2) расщепленные числа Шредера второго рода Кпт, где Кпт - число деревьев D с т внутренними вершинами; 3) расщепленные числа Шредера первого рода Нnfl, где Нп1г - число деревьев D высоты h. Теорема 2.1. Для чисел Кпт справедливо рекуррентное соотношение: К„о = 1, К„т = 0 при т + 1 > п , ит_х + (т + \)Кп_ит, где п>2, 1 < /;/ < п. Числа Ктг связаны с числами Sn соотношением: /7-2 да=О Теорема 2.2. Для чисел НпХ справедливо следующее рекуррентное соотношение: Из перечисленного смысла чисел Нnh и 5„, следует: ¦5". = Z Н Установлена связь чисел Кпт с присоединенными числами Стирлипга второго рода и с числами Эйлера и Белла. В параграфе 2.3 рассмотрена классификация плоских непомеченных корневых деревьев Каталана Zen ребрами. В соответствии с классификацией получены числа C(n,N), где C(n,N) -число деревьев Z, имеющих п ребер среди которых tV выходящих из корня. Теорема 2.3. Для чисел Каталана Сп имеют место следующие разложения: /i-i »-t п-1 Сп = ^ D(n,m) =^/^cl(n,N,m), n>2, /7—1 rt-2 и, кроме того, и— m—N d(n,N,m) = d(n — i,N — 1,ш)+ ^d(n-l,N + i,m — 1), m > 1 <=o Здесь D(n,m) -расщепленные числа Каталана второго рода, которые подсчитывают деревья Z с пг внутренними вершинами; d(n,N,m) - число 12 деревьев, имеющих п ребер, среди которых N выходящих из корня, и //; внутренних вершин. Пусть h(n,N,k) - число деревьев Z высоты /с, имеющих п ребер, среди которых N выходящих из корня и Н(п,к) — число деревьев Z, имеющих п ребер и высоту к. Теорема 2.4. Для чисел КаталанаСи имеют место следующие разложения: п п п-к ,/с) = ^ п, N ,/с), к=\ к=\ /V=l n-l п-2 - 2_.h(j'' h 1, к) = ^ /?( и, 2, /:), к=\ к=\ и, кроме того, Числа Н(п,к) названы расщепленными числами Каталаиа первого рода. В теореме 2.5 выводятся соотношения, связывающие числа Н(п,к) с числами Стерлинга второго рода. В параграфе 2.4 рассмотрены плоские корневые деревья Моцкгша СМ„ с петлями. Числа Моцкипа являются достаточно хорошо изученным объектом (см., например, [8,17,40,41,47]). В соответствии с предложенной схемой классификации введены обобщенные числа Моцкгша, а также расщепленные числа Моцкина первого и второго рода. Результаты, изложенные во второй главе, опубликованы в работах [19, 20, 21, 22]. Использованные в главе формулировки и результаты из указанных статей получены в нераздельном соавторстве с О.В. Кузьминым. Предварительные расчеты и таблицы принадлежат лично автору. В третьей главе широко известные и новые, введённые автором, комбинаторные числа и полиномы используются при перечислении путей на решётках специального типа. Такие пути, начинающиеся обычно в начале координат, являются последовательностями точек целочисленной решетки плоскости с некоторыми ограничениями на приращение координат при переходе от одной точки к следующей. Под шагом пути будем понимать упорядоченную пару чисел, показывающую взаимное расположение соседних точек пути. Таким образом, путь есть последовательность шагов, причем конец одного шага является началом следующего и высоты всех точек неотрицательны. В работах [4, 45, 50] путём подсчёта решётчатых путей на плоскости при некоторых ограничениях получен ряд комбинаторных тождеств. В параграфе 3.1 рассмотрены пути Мак-Магока — пути с шагами (0,1) и (1,0) и приведены геометрические интерпретации нескольких известных комбинаторных чисел. В параграфе 3.2 рассматриваются некоторые вопросы перечисления путей Моцкипа. Пусть и = (/,у)еZ , и ио,и1,...,и1 - такая последовательность точек из Z2, что: 1) ы0 =(0,у0); 2)и4+1=и,+(1Л), tf,e{-1,0,1}, 0 3) alt(uk) = jk - высота точки u, alt(uk )>0, Q Тогда u0... и, называется путем с началом и0 и концом и, и обозначается \о<)...о/_] )jo. Высотой пути \Po--^i-\ )/0 называется maxalt(uk), 0 Если re {—1,0,1), то (г) называется шагом на высоте], который мы назовем подъемом, уровнем или спадом, если г равно 1, 0 или —1 соответственно. Пусть Ht - множество всех путей S, у которых alt(u0) - alt{u,) = i и alt(iik)>i, 0 Рассматриваем бесконечную нижнюю треугольную матрицу М = \|\|ш„k\|, 0 < к < п, «>0, где тпк - число путей (S0...St!) e Н() с /с уровнями. Для чисел тпк получено следующее рекуррентное соотношение: с начальным условием т() () = 1. Числа Каталана Сп, Моцкина Мп и Шредера Rn могут быть заданы следующим образом: Теорема 3.2. Имеют место следующие утверждения: где С,; - числа Каталана, Мп - числа Моцкина и Rn - числа Шредера. Введены в рассмотрение числа l(n,k,h), перечисляющие пути Моикнпа длины п, высоты h с к уровнями. Для чисел l(n,k,h) доказан ряд утверждений. Теорема 3.3. Для чисел l(n,k,h) справедливы следующие утверждения: шВ параграфе 3.3 рассмотрены пути Дика и пути Моцкина с весами. Устанавлено, что обобщённые числа Каталана C(n,N) перечисляют пути Дика, состоящие из 2п шагов N из которых есть подьёмы, выходящие из начала координат. В параграфе 3.4 изучаются числа Шредера Rn, рассмотренные в [45, 49, 50, 53, 56], и пути на плоскости. Введены в рассмотрение числа Тпк , для которых установлена перечислительная интерпретация и доказано следующее утверждение. Утверждение 3.2. Числа Т„к удовлетворяют рекуррентному соотношению: где Т„=\, Tni=Sn.h n>2. Результаты, изложенные в третьей главе, опубликованы в работе [23]. Использованные в главе результаты из указанной статьи получены в нераздельном соавторстве с О.В. Кузьминым. Формулировки и доказательства теорем, приведенные в работе, получены лично автором. Материалы, представленные в данной диссертации, использовались при чтении спецкурсов в институте математики и экономики Иркутского государственного университета. Основными результатами диссертации являются: 1. Разработка комбинаторной схемы распространения последовательности однопараметрических комбинаторных чисел до матрицы, составленной из соответствующих двупараметрических комбинаторных чисел, изучение комбинаторных и аналитических свойств полученных чисел. 2. Классификация плоских корневых деревьев: введены новые комбинаторные числа, исследованы их свойства и указаны перечислительные интерпретации; получены соотношения, связывающие введенные комбинаторные числа с известными комбинаторными числами. 3. Перечисление путей на целочисленной решётке: построен треугольник чисел, являющихся разложениями чисел Моцкина, Каталана и Шредера. По результатам, изложенным в диссертации, имеется 6 публикаций. Результаты докладывались на Всесоюзных и международных конференциях по дискретной математике (Третья конференция молодых учёных ИГУ, Иркутск, 1985; конференция «Математика и ее приложения», посвященная памяти профессора А.И. Кокорина и 275-летшо РАН, Иркутск, 1999; Восточно-Сибирская зональная межвузовская конференция по математике и проблемам ее преподавания в вузе, Иркутск, 1999; XII Байкальская международная конференция «Методы оптимизации и их приложения», Иркутск, Байкал, 2001; XIII Международная конференция «Математика в вузе», Псков, 2001.) Были сделаны доклады на семинарах ФПК МГУ (г. Москва), кафедры математической статистики и теории вероятностей ИГУ. В диссертации нумерация формул, утверждений, теорем, таблиц идет по главам. Список литературы приводится в алфавитном порядке.

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23540.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.