Комбинаторные свойства сечений обобщенных пирамид Паскаля

Серегина, Марина Валерьевна

Комбинаторные свойства сечений обобщенных пирамид Паскаля тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Серегина, Марина Валерьевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Иркутск МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Комбинаторные свойства сечений обобщенных пирамид Паскаля»

Автореферат диссертации на тему "Комбинаторные свойства сечений обобщенных пирамид Паскаля"

и« ппопау т/тсопИСИ

4856537

Серёгина Марина Валерьевна

КОМБИНАТОРНЫЕ СВОЙСТВА СЕЧЕНИИ ОБОБЩЕННЫХ ПИРАМИД ПАСКАЛЯ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

О о [ид

; А р ?

2011

Иркутск-2011

4856537

Работа выполнена в ГОУ ВПО «Иркутский государственный университет путей сообщения»

Научный руководитель: доктор физико-математических наук,

профессор

Кузьмин Олег Викторович

Официальные оппоненты: доктор физико-математических наук,

профессор

Забудский Геннадий Григорьевич

кандидат технических наук, доцент Семёнов Александр Анатольевич

Ведущая организация: Институт прикладных математических

исследований Карельского научного центра РАН

Защита состоится 18 марта 2011 года в 14:00 на заседании диссертационного совета Д 212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, ул. К.Маркса, 1, Институт математики, экономики и информатики ИГУ.

С диссертацией можно ознакомиться в научной библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан 14 февраля 2011 г.

Ученый секретарь диссертационного совета, канд. физ.-мат. наук, доцент

Общая характеристика работы

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

По мере развития комбинаторных методов дискретной математики возникают вопросы классификации и представления материала, что, в свою очередь, вызывает необходимость создания единого подхода для получения и изучения комбинаторных объектов. Наряду с классическими подходами Мак-Магона и Редфилда-Пойа возникают и новые, в частности, Рота, Платонова, Сачкова. В последние десятилетия расширился круг исследователей, как, пожалуй, самой известной и изящной численной схемы, носящей название треугольник Паскаля, так и его плоских и пространственных аналогов и обобщений. Идеи построения арифметических треугольников комбинаторного происхождения и их приложений высказывались многими авторами (С. Гамберг, Т. Грин, Д. Кнут, Д. Прист, Дж. Риордан, Д. Рождерс, С. Смит, Р. Стенли, В. Хоггат, Л. Шапиро, Б.А. Бондаренко, О.В. Кузьмин, М.Л. Платонов, В.А. Успенский, В.Н. Докин, Т.Г. Тюрнева и др.), причем в некоторых работах, естественно, полученные результаты повторяются. Первые попытки классификации комбинаторных объектов на основе построения соответствующих пирамид Паскаля были предприняты в 80-х годах прошлого столетия Б.А.Бондаренко, а достаточно общую схему, названную обобщенной пирамидой Паскаля, предложил в конце 90-х годов XX века О.В. Кузьмин.

Треугольник Паскаля прост, но в то же время таит в себе неисчерпаемые возможности и связывает воедино различные разделы математики, не имеющие на первый взгляд между собой ничего общего. Эти обстоятельства побуждают искать всевозможные обобщения биномиальных коэффициентов. Некоторые из возможных обобщений -элементы обобщенного треугольника Паскаля, триномиальные коэффициенты и их обобщения, каждые из которых, в свою очередь, могут служить математическими моделями разнообразных дискретных процессов.

Обобщенным треугольником Паскаля называем треугольную таблицу, элементы которой для целых неотрицательных п, к, I удовлетворяют рекуррентным соотношениям:

У{п,к) = ап^У{П-\,к-\) + Рп/{п-\,к) с граничными условиями

Г(0,0) = Ко, Г(и,А) = 0, если 1шп(иДи-*)<0 или

Обозначая триномиальные коэффициенты символом

\, и полагая

к,1)

п к,]

л и!

к\1\{п-к-1у

записываем разложение тринома (х0 + х, + хг)" в форме

п п-к /

(х0 + х, + х2)" =

(1)

к^О 1=о

Хг. X, х>

Применяемое представление (1) упорядочивает расположение триномиальных коэффициентов в пирамиде Паскаля и ее сечениях, подобно тому, как расположены биномиальные коэффициенты в треугольнике Паскаля.

Обобщенной пирамидой Паскаля (V -пирамидой) называем трехгранный пирамидальный массив, элементы которого для целых неотрицательных п, к, I удовлетворяют рекуррентным соотношениям:

с граничными условиями

К(ОДО) = К0, К(и,М) = 0,если тт(п,к,1,п-к-1)<0 или Настоящая диссертационная работа принадлежит области комбинаторного анализа и посвящена развитию теории обобщенных пирамид Паскаля, позволяющей изучать свойства комбинаторных чисел при помощи выявления связей между элементами сечений обобщенной пирамиды Паскаля.

Разумеется, без геометрического представления результатов, изучаемые в диссертации объекты, которые возникали в разное время и из разных по своей природе задач, создавали впечатление разрозненности. Геометрический метод представления комбинаторных объектов в качестве элементов обобщенных пирамид Паскаля позволяет единым образом выявлять новые свойства и интерпретации этих объектов. Так, например, рассмотрение элементов, расположенных на плоских сечениях обычной и обобщенной пирамид Паскаля, позволяет получать новые рекуррентные соотношения и производящие функции для ряда хорошо известных комбинаторных чисел и их некоторых обобщений. Изучение сечений и частей обобщенной пирамиды Паскаля позволяет устанавливать новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также получать новые объекты, ранее не изученные.

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

Методы исследований. В работе используются методы комбинаторного анализа, линейной алгебры и геометрии, компьютерного моделирования.

Научная новизна. Продолжена разработка теории обобщенных пирамид Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел. Введены и изучены

суммы элементов плоских сечений обобщенных пирамид Паскаля и суммы элементов пирамид, названных верхними отсечениями обобщенных пирамид Паскаля, являющиеся обобщениями известных комбинаторных объектов.

Основные результаты, выносимые на защиту.

1. Разработан метод получения, систематизации и исследования семейств комбинаторных чисел, основанный на применении сечений обобщенных пирамид Паскаля.

2. Исследованы комбинаторные свойства плоских сечений и верхних отсечений обобщенных пирамид Паскаля.

3. Получены перечислительные интерпретации ряда известных и новых комбинаторных объектов.

Личный вклад автора состоит в развитии теории построения комбинаторных конфигураций и чисел на основе обобщенной пирамиды Паскаля, а также получении различных соотношений для известных и введенных автором комбинаторных объектов.

Все результаты, включенные в диссертацию, получены автором лично.

Теоретическая и практическая значимость. Полученные в диссертации результаты имеют значение для развития общей теории комбинаторного анализа и могут быть использованы в практических приложениях, связанных с изучением моделей дискретных иерархических систем.

Апробация работы. Результаты работы были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2008), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 2010), XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск, 2010), XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), XXII международной научно-методической конференции «Математика в ВУЗе»

(Петрозаводск, 2010), а также докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2008 - 2010), на семинарах кафедры высшей математики и прикладной информатики Забайкальского института железнодорожного транспорта (2006 - 2010).

Публикации. По теме диссертации опубликовано 10 работ. Основные результаты диссертации опубликованы в работах [1-9]. В число указанных работ входят 3 статьи [1-3] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2010 г.)», 4 статьи [6-9] в научных сборниках, 1 полный текст доклада [4] в материалах международного семинара. Работы [1-4] выполнены в нераздельном соавторстве с научным руководителем.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 94 наименования, и одного приложения. Общий объем диссертации - 110 страниц, включая 24 рисунка и 5 таблиц.

Основное содержание работы

Во введении обосновывается актуальность темы диссертации, проводится обзор литературы и кратко характеризуется ее содержание.

Первая глава диссертационной работы посвящена исследованию некоторых комбинаторных свойств пирамиды Паскаля.

В параграфах 1.1 и 1.2 введены понятия плоских сечений и верхних отсечений пирамиды Паскаля соответственно. Найдены значения сумм элементов плоских сечений и верхних отсечений пирамиды Паскаля, а также рекуррентные соотношения и производящие функции этих сумм.

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

по оси абсцисс, к - по оси ординат, / - по оси аппликат. Тем самым устанавливается соответствие между точками решетки и элементами пирамиды Паскаля, которая будет ограничена плоскостями к = О, п = О и п-к-1 = 0.

Рассмотрим произвольное плоское сечение пирамиды Паскаля, представляющее собой некоторый треугольник. Обозначим углы, образованные этим сечением с осями ординат и аппликат через <р и у/. Тогда уравнение сечения будет иметь вид:

n + tg(p-k + tgyf-l-const. (3)

Нумеруем все параллельные между собою сечения пирамиды Паскаля, заданные уравнением вида (3), начиная от вершины пирамиды, и рассматриваем последовательность {S^ {tgcp, tg(//)}, NeH0, сумм элементов таких сечений.

Пусть в уравнении (3) параметры tg<р = —, tgy/ =—, НОД(д.,^) = 1,

Я\ Ч2

р: е Z, <7,. е N, /=1,2. Полагаем — >-1, тогда треугольник сечения

Ч,

конечен и уравнение (3) принимает вид

4i Ч2 НОК (?„£,)

Обозначим:

Утверяедение 1.1. Сумма элементов N -го плоского сечения пирамиды Паскаля определяется по формуле

S»

El £2. Я\' Яг

¡-¿U-j^VN Ая> А >

Г9(P2+?2)JL9(Pl+9l)J

= Е I

——m~—г Ч Ч2 Чх

(4)

г, т

Для частично упорядоченного множества {а,Ь,с} символом mid {а, Ь, с) будем обозначать его «средний» элемент, которому

предшествует минимальный и следует максимальный элементы этого множества. Обозначим:

М. = Ш1П

(л+?!).—(А

, 41

Мй = 1ШС1 + +<5Г2)

АГ = шах

9,— (А+91).— (А+?2)

Теорема 1.1. Последовательность сумм ^ = удовлетворяет рекуррентному соотношению

¿Л' = ^-Л/, + +

с начальными условиями

= 1, = Бг =... = = 0; Б,, I = Мп,..., Л/, -1, задаются соотношениями

¿V = >

J = Л/,,...,Мх-1, задаются соотношениями ^ = ^J-KÍЙ + З^и. ■

( \ Ь. Е1.

41 ' Яг

(5)

(6) (7)

Следствие 1.1. Для натуральных взаимно простых Мп, М4 и Мх справедливы равенства:

Л/, ^

Х~

X х~

X X

Л/, М, ,

(8)

= 5,

ч'Ч, 'М„ ,

Теорема 1.2. Производящая функция сумм

Л. Л

имеет вид

^ л

ДА

Л> У

V 91 92

1-х' — * 1

¿V -ым верхним отсечением пирамиды Паскаля (ЛГ-ой V -пирамидой) с

параметрами — и —2-, где НОД(р/,9,) = 1, ->-1, р, еЖ, д, еИ, / = 1, 2, 91 Чг 9/

будем называть конечный массив элементов пирамиды Паскаля, которые

для целых неотрицательных п, £, / удовлетворяют рекуррентным

соотношениям

с граничными условиями

( п 4

п к,1

= 1,

= 0, если

пип

п,к,1,п-к — 1,—-9

<0 или 9 = НОК(д'1,92).

91 92 JJ

Таким образом, [/-пирамида совпадает с верхней частью пирамиды Паскаля, причем основанием N -ой (/-пирамиды служит N-oe плоское сечение пирамиды Паскаля, а номера рассматриваемых и -пирамид совпадают с номерами соответствующих сечений пирамиды Паскаля.

Утверждение 1.2. Сумма элементов ТУ-ой [/-пирамиды определяется по формуле

иК

Г ча 1Г эа

= 111

5=0 т=0 г=0

9 92 91 г, т

(10)

Теорема 13. Последовательность сумм С/Л, = IIы удовлетворяет рекуррентному соотношению

и,-и,

-и, + + иN-4, + 1

Ь. Рг.

91 ' Яг

(П)

с начальными условиями

и,, I - Мп,...,Ма -1, задаются соотношениями

Ц =£/,.*.+1. (12)

иJ, J ■= Ма,...,Мх-Х, задаются соотношениями

(13)

Следствие 1.2. Для натуральных взаимно простых Мп, и Мх справедливы равенства:

= Ь\

М„ 'Л/

м.

=ик

■■и„

М.

= ии

М, М„

К ' Мх

[К

{ Мя X

(14)

Теорема 1.4. Производящая функция сумм ик

—, — | имеет вид .91 <Ь.

гЬ-Ь.

ЛУ 9

к Ъ Чг

Х-х"-х* -х*

(Х~х)

(15)

В параграфе 1.3 из (4)—(15) получены известные и новые соотношения и производящие функции для чисел и сумм чисел 3Л', Якобсталя, Трибоначчи, Пелля и других.

Основные результаты главы опубликованы в работах [4, 5, 8,9].

Во второй главе исследуются некоторые комбинаторные свойства обобщенных пирамид Паскаля.

элементов плоских сечений и верхних отсечений обобщенных пирамид Паскаля, а также рекуррентные соотношения, которым удовлетворяют эти суммы.

По аналогии с пирамидой Паскаля, нумеруем все параллельные между собою сечения V -пирамиды, начиная от вершины, и рассматриваем последовательность {¿д, , N е N0, сумм элементов таких

сечений.

Утверждение 2.1. Сумма элементов N -го плоского сечения V -пирамиды определяется по формуле

(16)

~ , о п 1 (дг „ п

гля-ли I Е у\а.-£г.т-&.ГгГ,т

ь) »=0 И Чг Ч\

Пусть X - сумма элементов V (и, к,1). Введем в рассмотрение оператор Оо)аЬс, где а, Ь, с е Г10, который каждому слагаемому У(р,к,1) суммы X ставит в соответствие слагаемое соп+а к+ьН(У (п,к,1) суммы Ов>аЬсХ.

Теорема 2.1. Последовательность сумм -

Г Е±. Ех

ЧхЧг

удовлетворяет рекуррентному соотношению

(17)

Ч\ ?2

с начальными условиями

= ^о» ^ = =... = = 0; / = Мп,...,Мй -1, задаются соотношениями

Оа^ , если М„ =—{р1 + ?,),

если (18)

1-ЧРг*Чг) " О,

Чг

ОГю.о^> если К = Ъ

SJ, J = Мп,...,Мл -1, задаются соотношениями

©»«А,, + ,, .

если Мх = q, Оа100§ +Ог1.0Л если Мх = -^-(/>2 +ч2), (19)

J-XiP^+Ч¡) аг

©А,»/ +ог,,оЛ-9. если 11

ч_

12 ±

Ч\

N -ым верхним отсечением V -пирамиды (N -ой II -пирамидой) с

параметрами — и —, где НОД(р(,^() = 1, —>-1, д,. еК, г = 1, 2,

Чх Чг Ч,

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

целых неотрицательных п, к, I удовлетворяют рекуррентным

соотношениям (2) с граничными условиями К (0,0,0) = У0, У(п, к, /) = 0,

Р<

если пил

п,к,1,п-к-1,—-Ч

<0 или иеМ0, 9 = НОК(д-1,92).

Чх Яг

Таким образом, 0 -пирамида совпадает с верхней частью V -пирамиды, причем основанием Лг-ой £/ -пирамиды служит N -ос плоское сечение V -пирамиды, и номера рассматриваемых О -пирамид совпадают с номерами соответствующих сечений V -пирамиды.

Утверждение 2.2. Сумма элементов Л^ой ¿7 -пирамиды определяется по формуле

=11

иы

Рх Рг

Чг

г=0 т-0 л=0

£_Л|Я_ЛГ>Г>И| I. (20)

Ч Чг Ч\

Теорема 2.2. Последовательность сумм иы = С/Л

г \

41 ' 42

удовлетворяет рекуррентному соотношению

й„=Оа1Лй0 + +ОГ,,оЛ-?+^о (21)

лг-Чл+й)

с начальными условиями

О,, I = Мп,..., Мл-\ задаются соотношениями

©«1,0,0^ „ + если К=—{Р1+ЯО»

о, *1

ОДдсД

¡-МргПг) Яг

+ У0, если Мп=^-(р1+яг), Яг

(22)

QYifl.fi 1-4 + К> если К = Я,

О,, J = Мл,..., М -1 задаются соотношениями

О«,,о,„£/ +®/31ми +У0, если

Ч\ Яг

Мх=д,

■Г-Чр1+Я>)

Я>

Яг я,

если К=-(п+Я,)• «1

В параграфе 2.3 из (16) - (23) получены известные и новые соотношения для обобщенных чисел Трибоначчи первого и второго рода и их сумм.

Основные результаты главы опубликованы в работах [1-3, 6, 7].

В третьей главе найдены интерпретации исследованных в первых двух главах сумм элементов пирамиды Паскаля и ее обобщений.

В параграфе 3.1 найдены интерпретации сумм плоских сечений пирамиды Паскаля в терминах полных покрытий отрезка. В частных случаях получены новые интерпретации чисел 3", Якобсталя, Трибоначчи, Пелля и других.

Рассмотрим покрытия отрезка длины Ы, образованные отрезками, длины которых равны Мп, Мл и Мх соответственно, Мп<Мл<Мх, Ы,МП,М^,МХ еМ. Здесь отрезки полностью покрывают рассматриваемый отрезок, не перекрывая его и друг друга. Если Мп = М4 и/или Мп = Мх

и/или Мл= Мх, то соответствующие отрезки рассматриваем разных цветов. Два покрытия считаются различными, если они отличаются либо порядком расположения, либо составом покрывающих элементов. Такие покрытия назовем полными.

Утверждение 3.1. Число различных полных покрытий отрезка для

Во всех остальных случаях (для N * /лК, К е N ) число различных полных покрытий равно нулю.

Предложенная интерпретация позволила получить более компактное доказательство Теоремы 1.2.

Утверждение 3.2. Число различных полных покрытий отрезка удовлетворяет рекуррентным соотношениям (5) - (7).

В параграфе 3.2 найдены некоторые интерпретации сумм элементов верхних отсечений пирамиды Паскаля в терминах неполных покрытий отрезка. В частных случаях получены новые интерпретации сумм чисел 3Л', Якобсталя, Трибоначчи, Пелля и других.

Рассмотрим покрытия отрезка длины N отрезками, длины которых равны Мп, МЛ и Мх соответственно, Мп < МЛ < Мх, Ы,Мл,М(,,МхеЦ. Здесь покрывающие отрезки могут не полностью покрывать рассматриваемый отрезок. С одной стороны (условимся слева) может остаться непокрытая область, а с другой стороны (справа) располагаться покрывающие отрезки, которые не перекрывают друг друга и покрываемый отрезок. Длина непокрытой области может варьироваться от О до N. Если Мп = Мл и/или Мп = Мх и/или МЛ=МХ, то соответствующие отрезки рассматриваем разных цветов. Два покрытия считаются различными, если они отличаются либо размером непокрытой области, либо порядком расположения, либо составом покрывающих элементов. Такие покрытия назовем неполными.

Ы = // = НОД(МЙ,Ма,Мх), КеН, равно

Утверждение 3.3. Число различных неполных покрытий отрезка для Ы = +1, ...,ц(К +1)-1, /и=ИОД,(Мп,М^Мх), КеП, равно

ик

К/У 1

Предложенная интерпретация позволила получить более компактное доказательство Теоремы 1.3.

Утверждение 3.4. Число различных неполных покрытий отрезка удовлетворяет рекуррентным соотношениям (11) — (13).

В параграфе 3.3 найдены интерпретации сумм элементов плоских сечений и верхних отсечений обобщенных пирамид Паскаля в терминах развития популяции. В частном случае получены известная биологическая интерпретация элементов обобщенной пирамиды Паскаля, а также интерпретации сумм элементов плоских сечений и верхних отсечений пирамиды Паскаля в терминах полных и неполных покрытий отрезка соответственно.

Дискретное множество переменного состава, элементы которого способны рождаться, умирать и переходить из одной качественной категории в другую, называем популяцией. Не уменьшая общности рассмотрения, считаем, что первоначально популяция однородна - состоит из одинаковых элементов, обладающих двумя доминирующими свойствами: А а В. Развитие популяции рассматриваем дискретно по итогам его последовательных этапов, номера которых N > 1, и по двойным номерам элементов (г,т) - степеням обладания элементом свойствами Л и

В соответственно (г.иеМ,). Пусть элементы (г + ],т) вида порождаются по прошествии г, этапов развития популяции, элементы (г,т +1) вида - по прошествии /2 этапов развития популяции, а элементы (г,т) вида - по прошествии Г3 этапов развития популяции е N). То есть

ориентируемся на эволюцию без отступлений и с условием, что за , , /3 этапов можно сделать не более одного шага вперед. Тогда числа

ч'з

¿-1

Ч'з у

/ . N Ч

-1

г,г,т

и операторы Оа100, ОД0,о и ®Ую,о в

ч з ; ;

соотношениях (17) - (19) могут быть интерпретированы следующим образом:

—-1 \т-

ч'з

-— 1 \г,г,т

- объем (количество) элементов

(г,от)-го вида в итоге Л^-го этапа;

О«100 - оператор, производящий коэффициенты вида сс ж! / \ / \ , представляющие собой доли от объема

ч'з

-1-

^--1 | т-

ч'з

4--1

г,г,т

, в котором элементы (г, от)-го вида

Ч'з у )

породили элементы (г+ 1, то)-го вида по прошествии очередных этапов развития популяции;

О Д00 - оператор, производящий коэффициенты вида

Рь, г, \ (, > представляющие собой доли от объема

ЖЖЖ

от -

ч з Ч'з

-—1 Ч'з J

, в котором элементы (г, от)-го вида

породили элементы (г, от+1)-го вида по прошествии очередных /2 этапов развития популяции;

О/)00 - оператор, производящий коэффициенты вида ,

представляющие

собой

доли

от

{ЖН-'

объема

ч'з

^-Цот-ч'з

—1

г,г,т

, в котором сохранились элементы

Ч'з у ;

(г, да) -го вида по прошествии очередных этапов развития популяции. Общий объем популяции в итоге Л^-го этапа будет равен

т —

ч'з

г,г,т

(24)

Если задано У0 и известны весовые коэффициенты операторов О«,д0> ОД о о и О/т, то по формулам (24), (17) - (19) можно рассчитать общий объем популяции и присущее ей распределение по видам элементов на каждом из этапов развития. Обратная задача не является однозначной, если не указаны дополнительные условия.

Предложенная интерпретация позволила получить более компактное доказательство Теоремы 2.1.

В частных случаях получены: биологическая интерпретация элементов обобщенной пирамиды Паскаля и интерпретация сумм плоских сечений пирамиды Паскаля в терминах полных покрытий прямоугольников.

Рассмотрен также случай, когда на каждом этапе развития популяции добавляются элементы вида (0,0). Пусть К0 - объем элементов вида (0,0) в итоге каждого этапа. Тогда общий объем популяции в итоге А'-го этапа равен

Ь..

ч'з

-1

г,г,т

(25)

£=0 т=0 г=0

Общий объем популяции и присущее ей распределение по видам элементов на каждом из этапов развития в этом случае можно рассчитать по формулам (25), (21) - (23), если задано У0 и известны весовые коэффициенты операторов Оа100, ОД00 и О/100- Обратная задача не является однозначной, если не указаны дополнительные условия.

Такая интерпретация позволила получить более компактное доказательство Теоремы 2.2. В частном случае получена интерпретация сумм верхних отсечений пирамиды Паскаля, в терминах неполных покрытий прямоугольников.

Основные результаты главы опубликованы в работах [1-5,9].

В заключении дан обзор основных результатов, полученных в диссертационной работе.

В приложении представлены 4 таблицы, иллюстрирующие результаты исследования, проведенного в первой и третьей главах, на примере 40 известных числовых последовательностей.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в журналах, рекомендованных ВАК

1. Серёгина М. В. Плоские сечения обобщенной пирамиды Паскаля и их интерпретации / О. В. Кузьмин, М. В. Серёгина // Дискретная математика. - 2010. - Т.22, вып. 3. - С. 83 - 93.

2. Серёгина М. В. Верхние отсечения обобщенной пирамиды Паскаля и их интерпретации / О. В. Кузьмин, М. В. Серёгина II Журнал Сибирского федерального университета. Математика и физика. - 2010. - Т. 3, вып. 4.-С. 533-543.

3. Серёгина М. В. Восходящие сечения обобщенной пирамиды Паскаля и модели развития популяций / О. В. Кузьмин, М. В. Серёгина // Обозрение прикладной и промышленной математики. - 2010. - Т. 17, вып.З.-С. 430-432.

Прочие публикации

4. Серёгина М. В. Плоские сечения пирамиды Паскаля и полные покрытия прямоугольников / О. В. Кузьмин, М. В. Серёгина // Материалы X Междунар. сем. "Дискретная математика и ее приложения" (Москва, МГУ, 1-6 февр. 2010 г.) / под ред. О. М. Касим-Заде. - М.: Изд-во мех.-мат. ф-та МГУ, 2010. - С. 247 - 250.

5. Серёгина М. В. Некоторые восходящие диагональные сечения пирамиды Паскаля и покрытия прямоугольников / М. В. Серёгина // Вестник Иркутского университета: Ежегодная научно-теоретическая конференция аспирантов и студентов : материалы. - Иркутск : Изд-во Иркут. гос. ун-та, 2009. - С. 164 - 166.

f)b

6. Серёгина M. В. Некоторые плоские сечения А- и ¿?-пирамид / М. В. Серёгина // Моделирование. Системный анализ. Технологии : межвуз. сб. науч. тр. / под ред. Д. В. Железнова. - Чита : ЗабИЖТ, 2008. - С. 234 -245.

7. Серёгина М. В. Некоторые плоские сечения обобщенных пирамид Паскаля / М. В. Серёгина // Комбинаторные и вероятностные проблемы дискретной математики : сб. науч. тр. / под. ред. д-ра физ.-мат. наук, проф. О. В. Кузьмина. - Иркутск : Изд-во Иркут. гос. ун-та, 2010. -(Дискретный анализ и информатика; Вып. 4). - С. 116 - 130.

8. Серёгина М. В. Некоторые плоские сечения пирамиды Паскаля / М. В. Серёгина II Ресурсосберегающие технологии на транспорте и в промышленности: сб. науч. тр. / под ред. Д. В. Железнова. - Чита : ЗабИЖТ, 2007. - С. 188 - 194.

9. Серёгина М. В. Пирамида Паскаля и неполные покрытия прямоугольников / М. В. Серёгина // Математика в ВУЗе : материалы междунар. науч.-метод. конф., Петрозаводск, июнь 2010 г. - СПб., 2010. -С. 145-147.

Подписано к печати 03.02.2011. Формат 60x84 1/16 Усл. печ. л. 1,16. Тираж 100 экз.

Издательство Забайкальского института железнодорожного транспорта 672040, Чита, Магистральная, 11

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Серегина, Марина Валерьевна

ВВЕДЕНИЕ.

ГЛАВА I. Комбинаторные свойства пирамиды Паскаля.

1.1. Плоские сечения пирамиды Паскаля.

1.2. Верхние отсечения пирамиды Паскаля.

1.3. Сечения пирамиды Паскаля и некоторые комбинаторные числа.

ГЛАВА II. Комбинаторные свойства обобщенных пирамид Паскаля.

2.1. Плоские сечения обобщенных пирамид Паскаля.

2.2. Верхние отсечения обобщенных пирамид Паскаля.

2.3. Сечения обобщенных пирамид Паскаля и некоторые комбинаторные числа.

ГЛАВА III. Перечислительные интерпретациии.

3.1. Полные покрытия отрезка.

3.2. Неполные покрытия отрезка.

3.3. Модели развития популяций.

Введение диссертация по математике, на тему "Комбинаторные свойства сечений обобщенных пирамид Паскаля"

Актуальность темы. В настоящее время, в связи с интенсивным развитием компьютерных и информационных технологий, растет число комбинаторных задач и их разнообразие. К решению таких задач прямо или косвенно приводят многие вопросы теоретического и практического характера, связанные с существованием и подсчетом числа комбинаторных конфигураций из элементов некоторого множества, построенных в соответствии с определенными правилами (см., напр., [10, 15, 17, 20, 33, 39, 81]). Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций комбинаторных объектов и широту их применения (см., напр., [5, 21, 32, 45, 64]).

По мере развития комбинаторных методов дискретной математики возникают вопросы классификации и представления материала, что, в свою очередь, вызывает необходимость создания единого подхода для получения и изучения комбинаторных объектов. Наряду с классическими подходами Мак-Магона и Редфилда-Пойа возникают и новые, в частности, Рота, Платонова, Сачкова (см., напр., [25, 36-38, 45, 81, 87]). В последние десятилетия расширился круг исследователей, как, пожалуй, самой известной и изящной численной схемы, носящей название треугольник Паскаля (см., напр., [1-2, 6, 8, 9-11, 14, 24-26, 37, 40-41, 43, 52-58, 65-66, 68, 71, 75-76, 81, 85]), так и его плоских и пространственных аналогов и обобщений. Идеи построения арифметических треугольников комбинаторного происхождения и их приложений высказывались многими авторами (см., напр., [3, 7, 12-13, 16-18, 22-27, 34, 36-38, 41-42, 44, 55-57, 59-60, 62-63, 69-71, 74-79, 84, 87, 93] и др.), причем в некоторых работах, естественно, полученные результаты повторяются. Первые попытки классификации комбинаторных объектов на основе построения соответствующих пирамид Паскаля были предприняты в 80-х годах прошлого столетия Б.А.Бондаренко [7], а достаточно общую схему, названную обобщенной пирамидой Паскаля, предложил в конце 90-х годов XX века О.В. Кузьмин [25].

Треугольник Паскаля прост, но в то же время таит в себе неисчерпаемые возможности и связывает воедино различные разделы математики, не имеющие на первый взгляд между собой ничего общего. Треугольник Паскаля часто выписывают в виде равнобедренного треугольника (рис. 0.1), в котором на вершине и по боковым сторонам стоят единицы, каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке. Треугольник можно продолжать неограниченно. Он обладает симметрией относительно вертикальной оси, проходящей через его вершину.

Числа Фибоначчи

Рис. 0.1. Треугольник Паскаля.

Треугольник Паскаля также можно представить в форме прямоугольного треугольника в одном из четырех позиций. Наиболее употребительна форма записи, представленная в виде табл. 0.1.

Таблица 0.1. Треугольник Паскаля = 0 1 2 3 4 5 6 л = 0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1

Трудно даже перечислить все известные свойства и приложения треугольника Паскаля. Отметим лишь некоторые из них.

Вдоль диагоналей, параллельных сторонам треугольника (рис. 0.1) выстроены треугольные числа и их обобщения на случай пространств всех размерностей. Суммы чисел, стоящих вдоль восходящих диагоналей, образуют хорошо известную последовательность чисел Фибоначчи (см., напр., [6, 8, 9, 25, 40, 53, 54, 89, 92, 93]). Если, спускаясь по центральному столбцу, из каждого числа вычитать соседнее справа (или слева!), то возникает последовательность чисел Каталана (см., напр., [25, 92]). Числа, стоящие по горизонтальным строкам, являются биномиальными коэффициентами. Строка с номером п состоит из коэффициентов разложения бинома + Именно это фундаментальное свойство треугольника Паскаля связывает его не только с комбинаторикой и теорией вероятностей, но и с другими областями математики и ее приложений.

Биномиальные коэффициенты можно получить путем разложения производящей функции, являющейся степенью бинома: п /я\ ьо\'с X

0.1) где п\

0.2) к\(п — к)\

Коэффициенты разложения бинома удовлетворяют рекуррентному соотношению (правилу Паскаля) Л Г и Л ЛЛ

0.3) и + Г| Г п л м к ) с начальными условиями пЛ

Vе У 0, если тт(п,к,п — к)<0 или п<£

Биномиальные коэффициенты ук; удовлетворяют граничным условиям 1 и равенству (правилу симметрии) м ( П )

Кп — ку подтверждающему наличие оси симметрии (рис. 0.1). Между биномиальными коэффициентами установлены сотни различных тождеств и соотношений. Приведем лишь широко известную формулу суммирования

II п к=о \к у 2\

Биномиальные коэффициенты строятся из натуральных чисел при помощи арифметических операций п(п — 1).(п — к + 1) 1, к) к(к-1).2-1 п> 1, 1 <к<п.

Они широко используются как в самой математике, так и в ее приложениях. Эти обстоятельства побуждают искать всевозможные обобщения биномиальных коэффициентов. Некоторые из возможных обобщений -элементы обобщенного треугольника Паскаля V (п,к) (см., напр., [7, 24, 25, 27,

60, 63, 77]), триномиальные коэффициенты г п\ к, IJ см., напр., [7, 13, 24, 25, 65,

73, 82, 86, 89, 91, 94]) и их обобщения (см., напр., [4, 7, 19, 24, 25, 27, 78, 82, 83]), каждые из которых, в свою очередь, могут служить математическими моделями разнообразных дискретных процессов (см., напр., [12, 25, 27]).

Следуя [25], обобщенным треугольником Паскаля (V -треугольником) называем треугольную таблицу, элементы которой для целых неотрицательных п, к, / удовлетворяют рекуррентным соотношениям:

V (п,к) = ап<ку (л - 1Д -1) + ДаУ (я - 1Д) (0.4) с граничными условиями

У(0,0) = У0, У(п,к) = 0, если хтп(п,к,п-к) <0 или ле? М0.

Многие известные комбинаторные числа являются частными случаями элементов обобщенного треугольника Паскаля. Так, например, если в соотношении (0.4) при У0 = 1 положить апк — /Зпк = 1, п> 1, 0<к<п, тогда

V (п,к) = т.е. имеем обычный треугольник Паскаля.

Если считать У0 = 1, то при ап к = 1, Да = ц,пх, лг > 1, 0 <к<п, имеем V (п,к) = Вк и из соотношения (0.4) следует рекуррентная формула в:=впк:[ + Мп{в:-\ (о.5) определяющая обобщенные числа Стирлинга первого рода (см., напр., [25]).

При апк = 1, /Зпк = /4, и> 1, 0<к<п, имеем V(п,к) = Ак и рекуррентную формулу

Апк=А?:1+МкА£-1, (0.6) определяющую обобщенные числа Стирлинга второго рода (см., напр., [25]).

Треугольники, составленные из чисел Вк и Ак, называются В- и А-треугольниками соответственно.

Другим известным обобщением элементов треугольника Паскаля являются пЛ триномиальные коэффициенты и их обобщения, которые также обладают к,1 у широкой приложимостью. Разнообразные семейства дискретных распределений - теоретические модели и природные популяции - способны формироваться по описываемой пирамидальной схеме (см., напр., [25]).

Как указано в (0.1), биномиальные коэффициенты

6Л получаются в результате разложения бинома (1 + *)" и выписываются в виде треугольника Паскаля в той или иной форме. Используя две переменные х0 и х{, это разложение можно записать в виде п к=о ) хкх"~к

Обозначая триномиальные коэффициенты символом целые неотрицательные числа, и полагая пЛ ук,1 где п, к, I п к,1 п\ к\1\(п-к-1)\' записываем разложение тринома (х0 + х1 + х2)" в форме п п-к х0+х1+х2)п

1 п-к ( А к=0 1=о к, IJ

0.7)

Рис. 0.2. Пирамида Паскаля. 8

Применяемое представление (0.7) упорядочивает расположение триномиальных коэффициентов в пирамиде Паскаля (см., напр., [7, 13, 24, 25,

65, 73, 82, 86, 89, 91, 94]) и ее сечениях (рис. 0.2). Заметим, что в

Г п^ ук, I у число п указывает номер горизонтального сечения пирамиды Паскаля, к - номер строки сечения (треугольника), а / — номер его столбца (диагонали).

Нетрудно убедиться, что для триномиальных коэффициентов (0.7) справедливо рекуррентное соотношение

С и \ ( п \

0.8) л + Л ( п Л Г гс > ( П 1 к,1) — 1, ^к, 1 к / 1 у

01 ( п Л

-1, к, 1 ^ с начальными условиями 0, если тт(п,к,1,п-к-1) <0 или п<£ М0.

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

Аналогично биномиальным триномиальные коэффициенты удовлетворяют условиям П 1-( ,0, о/и 0, п 1 ^к,1 ^ г пЛ ( п ^ 0, п 1 и равенствам П ^ Г П Л [ П 1 ( п л

1 ^ > к ; ^гъ к /9 /у ^/С) ух 1с /^ подтверждающим наличие трех осей симметрии в пирамиде Паскаля. Приведем формулу суммирования п п—к , П

Щк1 к=о /=0 Vе» 1 Л 3\

0.9) где, как указано выше, п \ к I у«,, I у 0, если гтп(п,к,1,п-к — 1)<0 или п<£ М0.

Пирамиду Паскаля можно строить в форме тетраэдра, а также пирамиды с различными значениями двухгранных углов, один из которых прямой. В п-м сечении (треугольнике) пирамиды (п = 0,1,2,.), параллельном основанию, располагаются коэффициенты

Г п^ подобно тому, как расположены биномиальные коэффициенты в треугольнике Паскаля. По трем внешним ребрам пирамиды Паскаля (рис.0.2) стоят единицы. Каждая из трех боковых граней представляет собой треугольник Паскаля.

Если сечение пирамиды Паскаля является правильным треугольником, то при любом допустимом значении п оно имеет три оси симметрии. На рис. 0.3, \ Л симметрии сечения при /1 = 4.

Непосредственно из формул (0.2) и (0.7) следует соотношение п взятом из [25], показано расположение элементов и указаны оси пЛ „к,1 V п п — к I наглядно иллюстрирующее наличие тесной связи между биномиальными и триномиальными коэффициентами. п-к-1 п

3 2 1 0

А ч1 2

4 4 \

VI /Л ЛГ^ 1 41/

Г 4 5 4

Рис. 0.3. Оси симметрии сечения пирамиды Паскаля.

Следуя [21], обобщенной пирамидой Паскаля (У-пирамидой) называем трехгранный пирамидальный массив, элементы которого для целых неотрицательных п, к, / удовлетворяют рекуррентным соотношениям: + + (0.10) с граничными условиями

V (ОДО) = У0, V (п,к,1) = 0, если тт (п, к, 1,п-к-1)< 0 или п<£ М0.

Некоторые известные комбинаторные числа являются частными случаями элементов обобщенной пирамиды Паскаля. Так, например, если в соотношении (0.10) при У0 = 1 положить апЫ = /Зпк1 = упЛ1 =1, п> 1, 0 <к + 1<п, тогда ч Г И

V (п,к,1) = , т.е. имеем обычную пирамиду Паскаля. ук,1 ^

Если считать У0=1, то при апХ1=ссп{, Рп,и=Рп.х, Гп,к,1=Гп-1> 0 <к + 1<п, имеем V (п,к,1) = Вк1, и из соотношения (0.10) следует рекуррентная формула впи = + рпхвпк^+, (0.11) определяющая обобщенные триномиальные коэффициенты первого рода (см., напр., [25]).

При апк1 = ак, Да,,=Д, Гп,к,1 = П> 0<к+1<п, имеем V(п,к,1) = Апи, а из соотношения (0.10) имеем рекуррентную формулу

Аи = ак-Л:1 +ЛЛ";-.+пЛ",Л (0.12) определяющую обобщенные триномиальные коэффициенты второго рода (см., напр., [25]).

Пирамиды, составленные из чисел В'и и Апк1, называются В- и Апирамидами соответственно.

При от = 1, 1 = 0 из (0.11) и (0.12) получаются рекуррентные соотношения

0.5) и (0.6) для обобщенных чисел Стирлинга первого В" и второго А" рода соответственно.

Настоящая диссертационная работа принадлежит области комбинаторного

11 анализа и посвящена развитию теории обобщенных пирамид Паскаля, позволяющей изучать свойства комбинаторных чисел при помощи выявления связей между элементами сечений обобщенной пирамиды Паскаля.

Разумеется, без геометрического представления результатов, изучаемые в диссертации объекты, которые возникали в разное время и из разных по своей природе задач, создавали впечатление разрозненности. Геометрический^ метод представления комбинаторных объектов в качестве элементов обобщенных пирамид Паскаля позволяет единым образом выявлять новые свойства и интерпретации этих объектов. Так, например, рассмотрение элементов, расположенных на плоских сечениях обычной и обобщенной пирамид Паскаля; позволяет получать новые рекуррентные соотношения и производящие функции для ряда хорошо известных комбинаторных чисел и их некоторых обобщений. Изучение сечений и частей обобщенной пирамиды Паскаля позволяет устанавливать новые соотношения между известными объектами, переносить свойства одних объектов, на- другие, а также получать новые объекты, ранее не изученные.

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

Научная*, новизна. Продолжена разработка теории обобщенных пирамид Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел. Введены и. изучены суммы элементов плоских сечений обобщенных пирамид Паскаля и суммы элементов пирамид, названных верхними отсечениями обобщенных пирамид Паскаля, являющиеся обобщениями известных комбинаторных объектов.

Основные результаты, выносимые на защиту.

2. Исследованы комбинаторные свойства плоских сечений и верхних отсечений обобщенных пирамид Паскаля.

3. Получены перечислительные интерпретации ряда известных и новых комбинаторных объектов.

Все результаты, включенные в диссертацию, получены автором лично.

Содержательная часть работы включает введение и три главы.

Первая глава диссертационной работы посвящена исследованию некоторых комбинаторных свойств-пирамиды Паскаля.

В параграфах 1.1 и 1.2 введены понятия- плоских сечений и верхних отсечений пирамиды Паскаля соответственно. Найдены* значения сумм элементов плоских сечений и верхних отсечений пирамиды Паскаля, а также рекуррентные соотношения и производящие функции этих сумм.

В параграфе 1.3 получены известные и новые соотношения и производящие функции для чисел и сумм чисел Ъы, Якобсталя, Трибоначчи, Пелля и многих других.

Во второй главе исследуются» некоторые комбинаторные свойства обобщенных пирамид Паскаля.

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

В параграфе 2.3 получены известные и новые соотношения для обобщенных чисел Трибоначчи первого и второго рода и их сумм.

В параграфе 3.1 найдены интерпретации сумм плоских сечений пирамиды Паскаля в терминах полных покрытий отрезка. В частных случаях получены новые интерпретации чисел 3м, Якобсталя, Трибоначчи, Пелля и других.

В/ параграфе' 3.2 найдены некоторые интерпретации сумм элементов верхних отсечений пирамиды Паскаля в терминах неполных покрытий отрезка. В частных случаях получены новые интерпретации сумм чисел З'у, Якобсталя, Трибоначчи, Пелля и других.

В параграфе 3.3 найдены интерпретации сумм элементов плоских сечений и верхних отсечений обобщенных пирамид Паскаля, в терминах развития популяции. В частном случае получены известная биологическая интерпретация элементов обобщенной пирамиды Паскаля; а также интерпретации сумм элементов плоских сечений* и верхних отсечений пирамиды Паскаля в терминах полных и неполных покрытий отрезка соответственно.

Апробация работы. Результаты работы, были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2008), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 2010), XI Всероссийской, конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск, 2010), XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), XXII международной научно-методической конференции «Математика в ВУЗе» (Петрозаводск, 2010), а также докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2008 - 2010), на семинарах кафедры высшей математики и прикладной информатики Забайкальского института железнодорожного транспорта (2006 - 2010).

Публикации. По теме диссертации опубликовано 10 работ. Основные результаты диссертации опубликованы в работах [28-31, 46-51]. В число указанных работ входят 3 статьи [28-30] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2010 г.)», 4 статьи [46, 47, 50, 51] в научных сборниках, 1 полный текст доклада [31] в материалах международного семинара. Работы [28-31] выполнены в нераздельном соавторстве с научным руководителем.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

ЗАКЛЮЧЕНИЕ

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

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

Результаты, полученные в диссертации, использовались при чтении специальных курсов по перечислительной комбинаторике и комбинаторным методам теории вероятностей для студентов института математики, экономики и информатики ИГУ и могут быть использованы в курсе лекций по дискретной математике в ЗабИЖТ ИрГУПС.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Серегина, Марина Валерьевна, Иркутск

1. Айгнер М. Комбинаторная теория / М. Айгнер. - М.: Мир, 1982. - 558 с.

2. Андерсон Дж. А. Дискретная математика и комбинаторика / Дж. А. Андерсон. М.: Вильяме, 2004. - 960 с.

3. Арнольд В. И. Матричная теорема Эйлера-Ферма / В. И. Арнольд // Изв. РАН. Сер. матем. 2004. - Т. 68, вып. 6. - С. 61-70.

4. Балагура А. А. Обобщенные пирамиды Паскаля и им обратные / А. А. Балагура, О. В. Кузьмин // Дискретная математика. 2007. - Т. 19, вып. 4. -С.108-116.

5. Баранов В. И. Экстремальные комбинаторные задачи и их приложения / В.И. Баранов, Б. С. Стечкин. М.: Физматлит, 2006. - 240 с.

6. Богатырев Р. Золотой треугольник / Р. Богатырев // Мир ПК. 2001. - № 6. -С. 52-59.

7. Бондаренко Б. А. Обобщенные треугольники и пирамиды Паскаля, их фрактали, графы и приложения / Б. А. Бондаренко. Ташкент: Фан, 1990. -192 с.

8. Воробьев Н. Н. Числа Фибоначчи / Н. Н. Воробьев. М.: Наука, 1992. - 190 с.

9. Гарднер М. Математические новеллы / М. Гарднер. М.: Мир, 2000. - 416 с. Ю.Грэхем Р. Конкретная математика. Математические основы информатики /

10. Р. Грэхем, Д. Кнут, О. Паташник. М.: Вильяме, 2010. - 784 с.

11. Гульден Я. Перечислительная комбинаторика / Я. Гульден, Д. Джексон. -М.: Наука, 1990. 504 с.

12. Докин В. Н. О треугольной схеме развития популяций / В. Н. Докин // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1977. -Вып. 41.-С. 104 - 161.

13. Докин В. Н. Комбинаторные числа и полиномы в моделях дискретных распределений / В. Н. Докин, В. Д. Жуков, Н. А. Колокольникова, О. В. Кузьмин, М. Л. Платонов. Иркутск: Изд-во Иркут. ун-та, 1990. - 208 с.

14. Дынкин Е. Б. Математические беседы / Е. Б. Дынкин, В. А. Успенский. М.: ФИЗМАТЛИТ, 2004. - 240 с.

15. Кнут Д. Э. Искусство программирования. Т.1. Основные алгоритмы / Д. Э. Кнут. М.: Вильяме, 2006. - 720 с.

16. Колокольникова Н. А. Соотношения между суммами некоторых специальных чисел / Н. А. Колокольникова // Асимптотические и перечислительные задачи комбинаторного анализа. Красноярск: Краснояр. ун-т, 1976.-С. 117-124.

17. Колокольникова Н. А. Обобщения триномиальных коэффициентов / Н. А. Колокольникова, О. В. Кузьмин // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1983. - Вып. 63. - С. 60 - 67.

18. Колчин В. Ф. Случайные размещения / В. Ф. Колчин, Б. А. Севастьянов, В. П. Чистяков. М.: Наука. Главная редакция физико-математической литературы, 1976. - 224 с.

19. Кофман А. Введение в прикладную комбинаторику / А. Кофман. — М.: Наука, 1975.-480 с.

20. Кручинин В. В. Число разбиений натурального числа п на части, каждая из которых не менее т / В. В. Кручинин // Матем. заметки. 2009. - Т. 86, вып. 4. - С. 538-542.

21. Кузьмин О. В. Рекуррентные соотношения и перечислительные интерпретации некоторых комбинаторных чисел и полиномов / О. В. Кузьмин // Дискретная математика. 1994. - Т. 6, вып. 3. - С. 39 - 49.

22. Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения / О.В. Кузьмин // Соросовский Образовательный Журнал. 2000. - Т. 6, № 5. -С. 101-109.

23. Кузьмин О. В. Обобщенные пирамиды Паскаля и их приложения / О. В. Кузьмин. Новосибирск: Наука. Сибирская издательская фирма РАН, 2000. - 294 с.

24. Кузьмин О. В. Перечислительная комбинаторика / О. В. Кузьмин. М.: Дрофа, 2005.-110 с.

25. Кузьмин О. В. Комбинаторные методы моделирования дискретных распределений / О. В. Кузьмин. 2-е изд., испр. и доп. - Иркутск: Иркут. унт, 2006.- 138 с.

26. Кузьмин О. В. Верхние отсечения обобщенной пирамиды Паскаля и их интерпретации / О. В. Кузьмин, М. В. Серёгина // Журнал Сибирского федерального университета. Математика и физика. 2010. - Т. 3, вып. 4. - С. 533-543.

27. Кузьмин О. В. Восходящие сечения обобщенной пирамиды Паскаля и модели развития популяций / О. В. Кузьмин, М. В. Серёгина // Обозрение прикладной и промышленной математики. 2010. - Т. 17, вып. 3. - С. 430 -432.

28. Кузьмин О. В. Плоские сечения обобщенной пирамиды Паскаля и их интерпретации / О. В. Кузьмин, М. В. Серёгина // Дискретная математика. -2010. Т.22, вып. 3. - С. 83 - 93.

29. Ландо С. К. Лекции о производящих функциях / С. К. Ландо. М.: МЦНМО.-2007.-144 с.

30. Липский В. Комбинаторика для программистов / В. Липский. М.: Мир, 1988.-213 с.

31. Малышев Ф. М. О распределении числа единиц в булевом треугольнике Паскаля / Ф. М. Малышев, Е. В. Кутырева // Дискретная математика. 2006.-Т. 18, вып. 2.-С. 123-131.

32. Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. -СПб.: Питер, 2009. 384 с.

33. Платонов М. JL Комбинаторные числа класса отображений и их приложения / М. Л. Платонов. М.: Наука, 1979. - 152 с.

34. Платонов М. Л. Комбинаторные числа: учеб. пособие / М. Л. Платонов. -Иркутск: Иркут. гос. ун-т им. A.A. Жданова, 1980. 104 с.

35. Платонов М. Л. Треугольная схема развития популяций / М. Л. Платонов, В. Н. Докин // Исследования по геомагнетизму, аэрономии и физике Солнца. — М.: Наука, 1975. Вып. 35. - С. 26 - 31.

36. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, В. Нивергельт, Н. Део. М.: Мир, 1980. - 476 с.

37. Реньи А. Вариации на тему Фибоначчи / А. Реньи // Трилогия о математике. М.: Мир, 1980.-326 с.

38. Риордан Дж. Введение в комбинаторный анализ / Дж. Риордан. М.: Иностр. лит., 1963. - 287 с.

39. Риордан Дж. Комбинаторные тождества / Дж. Риордан. М.: Наука, 1982. -254 с.

40. Рыбников К. А. Введение в комбинаторный анализ / К. А. Рыбников. М.: Изд-во Моск. ун-та, 1985. - 308 с.

41. Саркисян П. С. Задача восстановления квазиоднородной струны по ее части / П. С. Саркисян// Матем. заметки. 2007. - Т. 82, вып. 1. - С. 125-134.

42. Сачков В. Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.: МЦНМО, 2004. - 424 с.

43. Серёгина М. В. Некоторые плоские сечения пирамиды Паскаля / М. В. Серёгина // Ресурсосберегающие технологии на транспорте и в промышленности: сб. науч. тр. / под ред. Д. В. Железнова. Чита: ЗабИЖТ, 2007.-С. 188-194.

44. Серёгина М. В. Некоторые плоские сечения А- и 5-пирамид / М. В. Серёгина // Моделирование. Системный анализ. Технологии: межвуз. сб. науч. тр. /под ред. Д. В. Железнова. Чита: ЗабИЖТ, 2008 . - С. 234 - 245.

45. Серёгина М. В. Плоские сечения пирамиды Паскаля и покрытия прямоугольников / М. В. Серёгина // Материалы XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям. Иркутск: ИДСТУ СО РАН, 2010. - С. 73.

46. Серёгина М. В. Пирамида Паскаля и неполные покрытия прямоугольников / М. В. Серёгина // Математика в ВУЗе: Материалы междунар. науч.-метод. конф., Петрозаводск, июнь 2010 г. СПб., 2010. - С. 145-147.

47. Скляревский Е. Удивительный треугольник великого француза / Е. Скляревский // НакТп^ой. 2003, №10. - С. 132 - 137.

48. Стахов А. П. Обобщенные Золотые Сечения и новый подход к геометрическому определению числа / А. П. Стахов // Украинский математический журнал. Киев, 2004, Т. 56, N0 8. - С. 1143 - 1150.

49. Стахов А. П. Код да Винчи и ряды Фибоначчи / А. П. Стахов, А. А. Слученкова, И. Г. Щербаков. Санкт Петербург: Питер, 2006. - 336 с.

50. Стенли Р. Перечислительная комбинаторика / Р. Стенли. М.: Мир, 1990. -440 с.

51. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции / Р. Стенли. М.: Мир, 2009. - 767 с.

52. Успенский В. А. Треугольник Паскаля / В. А. Успенский. М.: Наука, 1979.

53. Pickover C. A. Beauty, Symmetry, and Pascal's Triangle / C. A. Pickover // Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning in Oxford, England: Oxford University Press. 2001. - Ch. 54. - P. 130 - 133.

54. Rosenthal E. R. A Pascal pyramid for trinomial coefficients / E. R. Rosenthal // Math. Teacher. 1961. - Vol. 54, № 5. - P. 336 - 338.

55. Rota G. C. Report on the present state of combinatorics / G. C. Rota // Discrete Math. 1996. - Vol. 153, № 1-3. P. 284 - 303.

56. Santana S. F. Some properties of sums involving Pell numbers / S. F. Santana, J.L. Diaz-Barrero // Missouri Journal of Mathematical Sciences. 2006. Vol. 18, № 1. -P. 33-40.

57. Sellers J. A. Domino tilings and products of Fibonacci and Pell numbers / J. A.

58. Sellers // Journal of Integer Sequences. 2002. - Vol. 5, Article 02.1.2. - 6 p. 90.Shannon A. G. Tribonacci numbers and Pascal's pyramid / A. G. Shannon //

59. Fibonacci Quart. 1977. - Vol. 15, № 3. - P. 268, 275. 91.Shorter J. Pascal's tetrahedron and the trinomial coefficients / J. Shorter, F. M.

60. Stein // Pentagon. 1982. - Vol. 42, № 1. - P. 19 - 33. 92.Sloane N. J. The On-Line Encyclopedia of Integer Sequences / N. J. Sloane.

61. Published electronically at http://www.research.att.com/~njas/sequences/ 93.Smith S. W. Row and rising diagonal sums for a type of Pascal triangle / S. W. Smith, D. B. Priest // Fibonacci Quart. 1977. - Vol. 15, № 4. - P. 359 - 361.

62. Walser H. The Pascal Pyramid / H. Walser // The College Mathematics Journal. -2000. Vol. 31, № 5. - P. 383 - 392.-48 с.

63. Яблонский С. В. Введение в дискретную математику / С. В. Яблонский. -М.: Высшая школа, 2008. 384 с.

64. Ahdout S. Streaks and Generalized Fibonacci Sequences / S. Ahdout, S. Rothman, H. Strassberg // The College Mathematics Journal, 2006. Vol. 37, № 3. - P. 221 -223.

65. Ваггу P. On Integer-sequences-based constructions of generalized Pascal triangles / P. Barry // Journal of integer sequences, 2006. Vol. 9. - Art. 06.2.4.

66. Barry P. Triangle geometry and Jacobstal numbers / P. Barry // Irish Math. Soc. -2003. Bulletin 51.- P. 45 - 51.

67. Belbachir H. Connection between ordinary multinomials, Fibonacci numbers, Bell polynomials and discrete uniform distribution / H. Belbachir, S. Bourobi, A. Khelladi // Annales Mathematicae et Informaticae, 2008. Vol. 35. - P. 21 - 30.

68. Belbachir H. Unimodal rays in the regular and generalized Pascal triangles / H. Belbachir, L. Szalay // Journal of integer sequences, 2008. Vol. 11. - Art. 08.2.4.

69. Benjamin A. T. Proofs that really count: the art of combinatorial proof / A. T. Benjamin, J. J. Quinn. M.A.A, 2003. - 208 p.

70. Bollinger R. C. A note on Pascal T-triangles, multinomial coefficients, and Pascal pyramid / R. C. Bollinger // Fibonacci Quart. 1986. - Vol. 24, № 2. P. 140 -144.

71. Borwein J. Pascal's Triangle / J. Borwein, D. Bailey // Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: А К Peters. -2003.-P. 45-48.1. V V

72. Cerin. Z. Sums of Squares and Products of Jacobsthal Numbers / Z. Cerin. // Journal of Integer Sequences. 2007. - Vol. 10, Article 07.2.5. - 15 p.

73. Comet L. Advanced Combinatorics / L. Comet. Dordrecht; Boston: Reidel, 1974. - 354 p.

74. Dence T. P. Some Half-Row Sums from Pascal's Triangle via Laplace Transforms / T. P. Dence // The College Mathematics Journal. 2007. - Vol. 38, No. 3. - P.205 209.

75. Edelman A. Pascal Matrices / A. Edelman, G. Strang // Amer. Math. Monthly. -2004. Vol. 111, No 3. - P. 189 - 197.

76. Edwards A. W. F. Pascal's Arithmetical Triangle: The Story of a Mathematical Idea / A. W. F. Edwards. Baltimore, Maryland: The Johns Hopkins University Press, 2002. - 202 p.

77. Everest G. Primes generated by recurrence sequences / G. Everest et al. // Amer. Math. Monthly 2007. - Vol. 114, №5. - P. 417 - 431.

78. Feinberg M. Fibonacci Tribonacci / M. Feinberg // Fibonacci Quart. - 1963. -Vol. 1, № 3. - P. 71 - 74.

79. Gnedin A. V. The boundary of the Eulerian number triangle / A. V. Gnedin, G. I. Olshanskii // Mosc. Math. J. 2006. - Vol. 6, № 3. - P. 461^75.

80. Green T.M. Pascal's triangle / T. M. Green, C. L. Hamberg. Palo Alto: Dale Seymour, 1986. - 280 p.

81. Hoggatt V.E., Jr. A new angle on Pascal's triangle / V. E. Hoggatt, Jr. // Fibonacci Quart. 1968. - Vol. 6, № 4. - P. 221 - 234.

82. Hoggatt V.E., Jr., Bicknell M. Diagonal sums of generalized Pascal triangle / V.E. Hoggatt, Jr., M. Bicknell // Fibonacci Quart. 1969. - Vol. 7, № 4. - P. 341 -358, 393.

83. Hoggatt V. E. Diagonal sums of the trinomial triangle / V. E. Hoggatt, Jr., M. Bicknell // Fibonacci Quart. 1974. - Vol. 12, № 1. - P. 47 -50.

84. Kallos G. A generalization of Pascal's triangle using powers of base numbers / G. Kallos // Proc. Appl. Math. Mech. 2006. - № 6. - P. 681 - 682.

85. La Haye R. Binary Relations on the Power Set of an n-Element Set / R. La Haye // Journal of Integer Sequences. 2009. - Vol. 12, Article 09.2.6. - 15 p.

86. MacMahon P. A. An Introduction to Combinatorial Analysis / P. A. MacMahon. -Cambridge: Cambridge Univ. Press, 1920.

87. Mueller S. Recursions associated with Pascal's pyramid / S. Mueller // Pi Mu Epsilon J. 1969. - № 10. - P. 417 - 422.

88. Noe T. D. On the divisibility of generalized central trinomial coefficients / T. D.