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

На правах рукописи

Баранчук Антон ЛеонЦцович

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

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

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

Иркутск - 2005

Работа выполнена в Иркутском государственном университете. Научный руководитель:

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

доктор физико-математических наук Зуев Юрий Анатольевич,

кандидат физико-математических наук, доцент Забудский Геннадий Григорьевич

Ведущая организация:

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

Защита состоится 16 декабря 2005 года в 13 часов на заседании диссертационного совета Д 212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, ул. К.Маркса, 1, Институт математики, экономики и информатики ИГУ.

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

Автореферат разослан 15 ноября 2005 г.

Ученый секретарь диссертационного совета,

канд. физ.-мат. наук — Аргучинцева М.А.

¿006 - У

ггт

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Частными случаями обобщенной пирамиды Паскаля являются многие комбинаторные объекты: обобщенные числа Стерлинга В"к и А"к, обобщенные триномиальные коэффициенты В"и и А"и первого и второго рода, соответственно, обобщенные числа Фибоначчи и Трибо-наччи, числа Эйлера, присоединенные числа Лаха и многие другие, в том числе комбинаторные полиномы. Изучение сечений и частей обобщенной пирамиды Паскаля позволяет устанавливать новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также строить конструктивные алгоритмы взаимных преобразований.

Понятие «полином разбиения» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса - введено Беллом. Один из таких полиномов, связанный с производными от композиции функций, Риордан назвал полиномом Белла.

М.Л. Платонов для получения явной формы обращения формулы Бруно ввел 5-полиномы, являющиеся, в алгебраическом и аналитиче-

ском смысле, обратными однородным ^-полиномам Белла. Эти объекты О.В. Кузьмин назвал полиномами Платонова.

Свойства однородных А-полиномов Белла А(п,к;%) и сопряженных им В-полиномов Платонова В(п,к;$ изучали Дж. Риордан, К.А. Рыбников, М.Л. Платонов, Б.И. Селиванов, X. Хараламбидес, О. Хри-зафиноу, В.Д. Жуков, О.В. Кузьмин, О.В. Леонова и др. Комбинаторные А- и В- полиномы успешно применяются при решении целого ряда перечислительных задач.

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

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

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

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

практических приложений изучаемых комбинаторных объектов достаточно разнообразен.

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

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

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

Основные результаты, выносимые на защиту: 1. Выведены новые свойства А- и В- пирамид и их сечений. Построена производящая функция сумм элементов различных сечений под фиксированными углами треугольников типа Паскаля, в том числе треугольников обобщенных и обычных чисел Стир-линга второго рода. Установлена новая связь обобщенных чисел Стирлинга с обобщенными триномиальными коэффициентами.

2. Исследованы расщепленные полиномы Белла, являющиеся обобщением однородных полиномов Белла. Введены и изучены новые объекты - расщепленные полиномы Платонова, являющиеся обобщением полиномов Платонова. Показано, что расщепленные полиномы Белла и Платонова образуют в совокупности квазиортогональную пару.

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

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

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

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

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

линомов. Исследования, проводимые по теме диссертации, были поддержаны:

грантом для поддержки научно-исследовательской работы аспирантов государственных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию (2004 г.);

- грантом Рособразования "Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов" (2005 г.);

- грантом поддержки научно-исследовательской работы аспирантов и молодых сотрудников ИГУ (2005 г.).

Апробация работы. Результаты работы были представлены на научно-теоретической конференции "Молодые ученые к 80-летию ИГУ" (Иркутск, 1998); всероссийском научно-практическом молодежном симпозиуме "Экология Байкала и Прибайкалья" (Иркутск, 2001); второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003); научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, 2003); всероссийской конференции "Информационные и вычислительные технологии и системы" (Улан-Удэ, 2003); III международной научно-практической конференции "Математическое моделирование в образовании, науке и производстве" (Тирасполь, 2003); VIII международном семинаре "Дискретная математика и ее приложения" (Москва, 2004); конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2004); конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" (Москва, 2004); ме-

ждународной конференции 18ВЕР-2004 (Москва, 2004); XVII международной научно-методической конференции "Математика в вузе" (Великий Новгород, 2005); VI всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2005); IV всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005); семинарах кафедры дискретной математики и теории вероятностей ИМЭИ ИГУ (2002-2005).

Публикации. Основные результаты диссертации опубликованы в работах [1]-[15].

Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 97 наименований. Общий объем диссертации - 92 страниц, включая 29 рисунков и 7 таблиц.

Содержание работы

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

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

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

к-ого столбца (к^О). Найдены соответствующие соотношения для треугольников обобщенных и обычных чисел Стирлинга второго рода. Рассмотрим матрицу вида:

"оо °01 а02 °03 Я04

«ю аи а,г а,3 а,„

«20 °2| «22 аи

а)0 Й31 аП «33 °34

«40 Л41 «42 «43 «44

О)

обладающую свойством Паскаля:

0,0 < г < 0.

Пусть /(*) - производящая функция последовательности которая составляет первый столбец матрицы (1). Хоггат показал, что производящая функция элементов к-ого столбца матрицы (1) задается соотношением

и получил формулу производящей функции чисел типа Фибоначчи (сумм элементов восходящих диагоналей):

Будем строить (р,я)-сечение по двум фиксированным элементам А и В матрицы (1). При этом А выбираем в первом столбце матрицы, а элемент В зададим следующим: пусть р - параметр, который определяет, на сколько элементов выше сечения, перпендикулярного главной диагонали и проходящего через А, лежит элемент В; д - параметр, за-

(2)

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

Смит и Прист в 1977 получили формулу вычисления сумм элементов различных (р,я)-сечений треугольников типа Паскаля. Результаты работ Хоггата, Смита и Приста обобщены автором данной диссертации для произвольного треугольника типа Паскаля, заданного производящей функцией первого столбца /(*).

э-Треугольником будем называть треугольник, образованный числами Стирлинга второго рода . Производящая функция элементов этого треугольника имеет вид:

пшт /»1

А-треугольником называется треугольник, образованный обобщенными числами Стерлинга второго рода А"к. Б-Треугольник является частным случаем А-треугольника.

Теорема 1.1. Производящая функция сумм элементов (р,ф-сечения А-треугольника имеет вид:

14 О Л!*0

Если в последнем соотношении положить <7=0, то получим широко известную формулу производящей функции чисел Фиббоначи.

Формулу Хоггата (2) обобщает следующая теорема для треугольников типа Паскаля, для которых известна производящая функция кого столбца.

Теорема 1.2. Производящая функция сумм (р,ц)—элементов сечения треугольника типа Паскаля имеет вид:

(=0 II-*.

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

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

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

Основные результаты главы опубликованы в работах [5, 6,11, 14,

15].

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

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

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

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

В параграфе 2.1 рассматриваются однородные полиномы Белла, их свойства и доказывается новое рекуррентное соотношение для этих комбинаторных объектов.

Рассмотрим следующие разложения:

ее п ¡1*

ехр[*£(0] = 1 + -г •

л-1 М

Величины есть однородные полиномы Белла.

Для краткости будем обозначать их следующим образом А{п,к\г), где g = (g¡,g2,.■■)■ Однородные полиномы Белла имеют многочисленные интерпретации, для них известен ряд рекуррентных соотношений. Сформулировано и доказано следующее утверждение:

Теорема 2.1. Для и>0,имеет место рекуррентное соотношение:

А(п + и; я) = X -'.*-!;*).

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

Расщепленные полиномы Белла имеют вид

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

Ж л, А; являются полиномами относительно совокупности переменных '¡щ,1 = ],к,п1=],п-к+\, однородными степени к по нижним индексам и симметрическими по верхним индексам.

Доказаны следующие соотношения для расщепленных полиномов Белла.

Теорема 2.2. Для п>\,\<к<п имеет место рекуррентное соотношение:

Теорема 2.3. Для п>\,\£к<,п имеет место рекуррентное соотношение:

На основе идеи, высказанной в 1990 году М.Л. Платоновым, построен алгоритм "расщепления" однородных полиномов Белла.

В параграфе 2.3 рассмотрены, тесно связанные с однородными полиномами Белла, В-полиномы Платонова, которые имеют вид

Л

п_ п-к* I а ^

м о я.

где суммирование ведется по всем к, г 0, таким что

п-к+1

п-к+1

'¿Гк, = п- к, £ Iк, = 2и - 2к.

А- и В-полиномы могут рассматриваться как элементы взаимно-обратных матриц.

В параграфе 2.4 по аналогии с расщепленными А-полиномами введены новые объекты - расщепленные В-полиномы, называемые расщепленными полиномами Платонова. Для этих полиномов построена таблица, найден явный вид и доказан ряд соотношений.

Показано, что расщепленные однородные полиномы Белла связаны с расщепленными полиномами Платонова соотношениями квазиортогональности:

где ё„ к - символ Кронекера.

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

'е)Ви,к, 'г) =4,*, 'в)2ил 'я) = 6,

н

А(к+\к- А(к+\,к+1-, '«) о

А(к+2,к, А(к+2,к+1;'Я) А(к+2,к+Ъ'

А(к+Ъ,к\ й 3(£+ЗД+1; А(к+2,к+2,

А(п,к-, А(п,к+и... Л(п,и-1;

Теорема 2.4. Для п > 1,1 < Л < п имеет место рекуррентное соотношение:

А(п,1%

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

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

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

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

В параграфе 3.1 рассматривается конструктивное построение индекса релевантности на основе принципа п-мерных обобщенных пи-

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

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

В параграфе 3.3 приводится описание программного комплекса ррк"УЪиа1 для изучения свойств комбинаторных полиномов и обобщенной пирамиды Паскаля. В систему входят: система визуального создания пирамиды и ее сечений, операции с полиномами (от вычисления коэффициентов до построения рекуррентных соотношений), а также все алгоритмы и классы, созданные для представления и обработки исследуемых комбинаторных объектов.

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

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

Список публикаций автора

1. Баранчук А.Л., Кузьмин О.В. О некоторых комбинаторных полиномах. // Обозрение прикладной и промышленной математики. -2005. - Т. 12, вып. 3. -С. 651-653.

2. Баранчук А.Л., Кузьмин О.В. Расщепленные однородные полиномы Белла и квазиортогональные им // Материалы VIII межд. семинара "Дискретная математика и ее приложения". - М.: Изд-во мех.-мат. фак-та МГУ, 2004. - С.170-172.

3. Баранчук А.Л., Логинов Т.А. Механизм защиты авторских прав на основе механизма активации // Технологии Microsoft в информатике и программировании: Конф.-конкурс работ студ., асп. и молод, ученых-Новосибирск: НГУ, 2004. - С.72-74.

4. Баранчук А.Л, Гранин М.Н., Логинов Т.А. Современные проблемы распространения программного обеспечения и пути их решения: .» система активации ПО // Проблемы Земной цивилизации. Поиск

решения проблем выживания и безопасности Земной цивилизации: Сб. статей. -Иркутск, 2002. -Вып. 6, ч. 1. -С.185-193.

5. Кузьмин О.В., Баранчук А.Л. О конструктивном подходе к перечислению элементов треугольников типа Паскаля. // Труды второй Восточно-Сибирской зональной межвуз. конф. по математике и про-

блемам ее преподавания в ВУЗе. - Иркутск: Изд-во Иркут. пед. унта, 2003.-С. 141-144.

6. Кузьмин О.В., Баранчук A.JI. Конструктивное перечисление элементов треугольника типа Паскаля // Математическое моделирование, численные методы и комплексы программ: Межвуз. темат. сб. тр. -СПб.: СПбГАСУ, 2003. - Вып. 9. - С.179-183.

7. Кузьмин О.В., Баранчук A.JL, Логинов Т.А. Конструктивные комбинаторные алгоритмы в системе защиты и лицензирования программного обеспечения // Инфокоммуникационные и вычислительные технологии и системы: Материалы всерос. конф. - Улан-Удэ: Изд-во Бурят, ун-та, 2003. - Ч. 2. - С.15-17.

8. Баранчук А.Л. Конструктивное построение индекса релевантности на основе принципа N-мерных пирамид Паскаля // Математика в вузе: Материалы межд. науч.-метод. конф. - СПб, 2005. - С.162-163.

9. Логинов Т.А., Баранчук А.Л. Защита авторских прав в сети Интернет // Вестн. Иркут. ун-та: Спец. выпуск. - Иркутск: Иркут. ун-т, 2003.-С.85-86.

10. Baranchuk A.L., Kuzmin O.V., Loginov Т.А. Constructive combinatorial algorithms in the software protection system based on an activation mechanism // Математическое моделирование в образовании, науке и производстве: Материалы III межд. науч.-практ. конф,-Тирасполь: РИО ПриднГУ, 2003. - С.8-10.

11. Kuzmin О.V., Baranchuk A.L. Constructive method of counting elements in Pascal type triangles // Математическое моделирование в образовании, науке и производстве: Материалы III межд. науч.-практ. конф. - Тирасполь: РИО ПриднГУ, 2003. - С.198-199.

12. Баранчук A.JI., Логинов Т.А. Программный комплекс PPKVisual для изучения свойств комбинаторных полиномов и обобщенной пирамиды Паскаля. // Обозрение прикладной и промышленной математики. - 2005. - Т. 12, вып. 3. - С.699.

13. Баранчук А.Л., Логинов Т.А. Система лицензирования программного обеспечения на основе механизма активации // Технологии Microsoft в теории и практике программирования. - М.: Изд-во факта выч. мат. и кибернетики МГУ, 2004. - С. 5.

14. Баранчук А.Л. Перколяция конечных мозаичных структур // Студент и научно-технический прогресс. - Иркутск: Иркут. ун-т, 1998-С. 37-38.

15. Баранчук А.Л. Перколяционная модель эпидемии // Студент и научно-технический прогресс. - Иркутск: Иркут. ун-т, 1998. - С. 39.

с

г

Подписано в печать 14.11.05. Формат 60x84 1/16. Бумага офсетная. Печать трафаретная. Уч.-изд. л. 1,0. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 120.

Отпечатано с готового оригинал-макета

РЕДАКЦИОННО-ИЗДАТЕЛЬСКИЙ ОТДЕЛ Иркутского государственного университета 664003, Иркутск, бульвар Гагарина, 36; тел. (3952) 24-14-36

m 35 0

РНБ Русский фонд

2006-4 22633 У

Введение

Глава 1. Треугольники и пирамиды типа Паскаля

1.1. Сечения в треугольниках типа Паскаля

1.2.Многомерные пирамиды Паскаля 24 1.3.Обобщенный треугольник и обобщенная пирамида Паскаля 35 1.4. Алгоритмы взаимных преобразований

Глава 2. Комбинаторные полиномы

2.1. Однородные полиномы Белла '

2.2. Расщепленные полиномы Белла

2.3. Полиномы Платонова

2.4. Расщепленные полиномы Платонова

2.5. Полиномы Каталана

2.6. Алгоритмы взаимных преобразований

Глава 3. Практические приложения

3.1. Конструктивное построение индекса релевантности на основе принципа n-мерных пирамид Паскаля

3.2. Модуль защиты от мошенничества в системе лицензирования программного обеспечения на основе механизма активации

В настоящее время в связи с развитием современных компьютерных и информационных технологий и близких к ним разделов науки существенно повысилась значимость дискретной математики в целом и комбинаторного анализа в частности [28, 55, 64]. Развитие комбинаторных методов обусловлено появлением разнообразных задач дискретной математики, связанных с существованием, алгоритмами построения и подсчетом числа некоторых конфигураций из элементов данного множества [1, 2, 3, 6, 12, 16, 58]. Конфигурации, построенные в соответствии с определенными правилами, называются обычно комбинаторными [51].

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

Комбинаторные задачи алгоритмического характера на дискретных конечных математических структурах встречаются постоянно. Можно выделить два класса прикладных задач: создание алгоритмов и программ с преобладанием вычислений комбинаторного характера и алгоритмов, осуществляющих конструктивное перечисление комбинаторных объектов заданного класса [2, 4, 5, 11, 13, 15, 21-23, 25-28, 41, 47, 52, 54, 55, 57].

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

14]. Значительная часть соответствующих работ (при этом обнаружился достаточно широкий спектр толкования различными исследователями терминов «конструктивный», «эффективный» и т. д.) опиралась на успехи, достигнутые в изучении математического понятия алгоритма. Один из наиболее последовательных и законченных подходов к построению конструктивной математики на этой основе доставляется основанной А.А.Марковым советской школой конструктивной математики, формирование основных понятий которой относится к 50-м г.г. XX в. [63].

Конечный объект - это "объект, о котором можно мыслить не привлекая абстракции актуальной бесконечности" [60]. Некоторые из конечных объектов являются конструктивными объектами. Каждый конструктивный объект состоит из конечного числа множества элементов, принадлежащих каждый к одному из конечного числа типов и связанных некоторыми отношениями также из конечного числа типов. Таким образом, конструктивный объект имеет расчлененное строение и состоит из отдельных самостоятельных элементов. Большинство комбинаторных объектов являются конструктивными.

Среди множества чисел комбинаторного происхождения самыми работоспособными в теоретических исследованиях и различного рода приложениях, вне всякого сомнения, являются биномиальные коэффициенты, которые, при каждом фиксированном п, образуют (п+1)-ю строку таблицы, называемой треугольником Паскаля. В последние десятилетия расширился круг исследователей, как самого треугольника Паскаля, так и его плоских и пространственных аналогов и обобщений. Имеется ряд научных и методических публикаций, большей частью зарубежных математиков, но среди них только четыре книги. Это две монографии [7, 32] и два популярных издания [59, 73].

Идеи построения арифметических треугольников комбинаторного происхождения, родственных треугольнику Паскаля, и их приложений высказывались многими авторами (см., например, [18, 42, 72, 77, 82], а также обширную библиографию в [7, 32]), причем в некоторых работах, естественно, полученные результаты повторяются. Пирамиды и гиперпирамиды Паскаля открываются и переоткрываются, строятся и используются в ряде работ, в частности при построении различных семейств комбинаторных чисел [7]. Однако достаточно общий подход к изучению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был предложен О.В. Кузьминым сравнительно недавно [32].

Частными случаями обобщенной пирамиды Паскаля являются многие комбинаторные объекты, в частности это: обобщенные числа Стирлинга В"к и В"к и обобщенные триномиальные коэффициенты В"/ и

A'h первого и второго рода, соответственно, обобщенные числа Фибоначчи и Трибоначчи, числа Эйлера, присоединенные числа JIaxa, и многие другие [48, 50, 79], в том числе комбинаторные полиномы. Изучение определенным образом заданных сечений и частей обобщенной пирамиды Паскаля позволяет строить новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также строить конструктивные алгоритмы взаимных преобразований.

Различные, чаще всего ортогональные, полиномы комбинаторного характера широко применяются в ряде разделов математики и ее приложений (см., например, [8, 49, 56, 65, 66, 70, 74, 75, 76, 78, 81]). Понятие «полином разбиения» - полином от нескольких переменных, определяемый с помощью суммы по различным разбиениям его индекса -введено Беллом [67, 68]. Один из таких полиномов, связанный с производными от композиции функций, Риордан [48, 49] назвал полиномом Белла.

МЛ. Платонов [44] для получения явной формы обращения формулы Бруно ввел 5-полиномы, являющиеся, в алгебраическом и аналитическом смысле, обратными однородным ^-полиномам Белла. Эти объекты О.В. Кузьмин [30] назвал полиномами Платонова.

Свойства однородных ^-полиномов Ъешт A(n,k,g) и сопряженных им 5-полиномов Платонова B(n,k,g) изучались в работах В.Д. Жукова, О.В. Кузьмина, О.В. Леоновой, M.JI. Платонова, Б.И. Селиванова [19, 20, 31, 32, 37, 44, 45, 53] и др. В ряде работ [19, 26, 30, 33-37, 39, 40, 69, 71] изучались некоторые обобщения этих комбинаторных объектов. Комбинаторные А- и В-пошшомы успешно применяются при решении целого ряда перечислительных задач [17, 32, 44,45, 46].

В указанной монографии [17] при моделировании дискретных распределений с помощью комбинаторных полиномов показано, что структура матрицы, составленной из однородных полиномов Белла, такова, что ее столбцы содержат полную информацию о свертках любых натуральных порядков дискретного вероятностного распределения.

Однородные полиномы Белла и полиномы Платонова применяются в задачах, связанных с дискретными процессами восстановления, однородными ветвящимися процессами и другими разделами теории вероятностей и ее приложений [17, 32, 44].

При рассмотрении суммы независимых случайных величин, в которой каждое слагаемое имеет отличное от других распределение, возникают так называемые расщепленные полиномы Белла [17]. Эти полиномы являются в некотором смысле обобщением однородных полиномов Белла.

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

Построены алгоритмы взаимных преобразований исследуемых объектов. Спектр практических приложений изучаемых комбинаторных объектов достаточно разнообразен.

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

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

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

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

1. Выведены новые свойства А- и В-пирамид и их сечений. Построена производящая функция сумм элементов различных сечений под фиксированными углами треугольников типа Паскаля, в том числе треугольников обобщенных и обычных чисел Стерлинга второго рода. Установлена новая связь обобщенных чисел Стерлинга с обобщенными триномиальными коэффициентами.

2. Исследованы расщепленные полиномы Белла, являющиеся обобщением однородных полиномов Белла. Введены и изучены новые объекты - расщепленные полиномы Платонова, являющиеся обобщением полиномов Платонова. Показано, что расщепленные полиномы Белла и Платонова образуют в совокупности квазиортогональную пару.

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

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

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

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

- грантом для поддержки научно-исследовательской работы аспирантов государственных образовательных учреждений высшего профессионального образования, находящихся в ведении Федерального агентства по образованию (2004 г.);

- грантом Рособразования "Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов" (2005 г.);

- грантом поддержки научно-исследовательской работы аспирантов и молодых сотрудников ИГУ (2005 г.).

Апробация работы. Результаты работы были представлены на научно-теоретической конференции "Молодые ученые к 80-летию ИГУ" ф

Иркутск, 1998); всероссийском научно-практическом молодежном симпозиуме "Экология Байкала и Прибайкалья" (Иркутск, 2001); второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, 2003); научно-теоретической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, 2003); всероссийской конференции "Информационные и вычислительные технологии и системы" (Улан-Удэ, 2003); III международной научно-практической конференции "Математическое ф моделирование в образовании, науке и производстве" (Тирасполь, 2003);

VIII международном семинаре "Дискретная математика и ее приложения" (Москва, 2004); конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2004); конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и практике программирования" (Москва, 2004); международной конференции ISDEF-2004 (Москва, 2004); XVII международной научно-методической конференции "Математика в вузе"(Великий Новгород, 2005); VI всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2005); IV всероссийской конференции «Математика, информатика, управление» (Иркутск, 2005); семинарах кафедры дискретной математики и теории вероятностей ИМЭИ ИГУ (2002-2005). ф Публикации. Основные результаты диссертации опубликованы в работах [83]-[97].

Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 97 наименований. Общий объем диссертации - 92 страницы, включая 29 рисунков и 7 таблиц.

Основные результаты главы опубликованы в работах [85, 86, 89-91, 94-96].

Заключение

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

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

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

2. Алгоритмические исследования в комбинаторике. М.: Наука, 1978.

3. Андерсон, Джеймс А. Дискретная математика и комбинаторика. М: Вильяме, 2003.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — СПб.: Вилиямс, 2000.

6. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: ФИЗМАТЛИТ, 2004.

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

8. Бондаренко JI.H. Многочлены композиций и обобщенные многочлены Эйлера // Труды V Международной конференции «Дискретные модели в теории управляющих систем» (Ратмино, 2629 мая 2003г.). М.: Изд. отдел факультета ВМиК МГУ, 2003. -С.13-15.

9. Браславский П.И., Вовк Е.А., Маслов М.Ю. Фасетная организация интернет-каталога и автоматическая жанровая классификация документов // http://company.Yandex.ru/articles/article8.html

10. Ю.Венбо Мао. Современная криптография: теория и практика. СПб.: Вилиямс, 2005.

11. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989

12. Гасфилд Дэн. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский диалект; БХВ - Петербург, 2003.

13. Генри С. Уоррен, мл. Алгоритмические трюки для программистов. СПб.: Вилиямс, 2000.

14. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. -М.: Мир, 1998.

15. Гудман С., Хидетниеми С. Ввведение в разработку и анализ алгоритмов. М.: Мир, 1981.

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

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

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

19. Жуков В.Д. Рекуррентные формулы для обобщенных А- и В-полиномов // Исследования по геомагнетизму, аэрономии и физике Солнца. -М.: Наука, 1983. Вып. 66. - С. 192-197.

20. Жуков В.Д. Производящий определитель // Асимптотические и перечислительные задачи комбинаторного анализа. Красноярск: Изд-во Краснояр. ун-та. 1976. - С. 47-58.

21. Кнут Д., Искусство программирования, т. 1. Основные алгоритмы. -СПб.: Вильяме, 2000.

22. Кнут Д. Искусство программирования для ЭВМ, т. 2. Получисленные алгоритмы. — СПб.: Вильяме, 2000.

23. Кнут Д. Искусство программирования для ЭВМ, т. 3. Сортировка и поиск. — СПб.: Вильяме, 2000.

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

25. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.:МЦНМО, 1999.

26. Коробов Н.М. Специальные полиномы и их приложения. Диофантовы приближения. // Математические записки, 1996. Т.2 -С. 77-79.

27. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

28. Кувырков П.П., Темников Ф.Е. Комбинаторные системы. М.: Энергия, 1975.

29. Кузьмин О.В. Взаимные преобразования некоторых полиномов разбиений // Алгоритмические и комбинаторные вопросы дискретных систем и ЭВМ. Иркутск: Иркут. ун-т, 1990. - С.71-79.

30. Кузьмин О.В. Построение обобщенных А- и В-полиномов в пространстве отображений // Методы дискретного анализа в теории графов и сложности. Новосибирск: ИМ СО РАН, 1992. - Вып.52. -С. 66-76.

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

32. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. -Новосибирск: Наука, 2000.

33. Кузьмин О.В., Леонова О.В. О полиномах Тушара // Асимптотические и перечислительные задачи комбинаторного анализа. Иркутск: Иркут. ун-т, 1997. - С.101-109.

34. Кузьмин О.В., Леонова О.В. Полиномы Тушара и им квазиортогональные // Оптимизация, управление, интеллект. -1999. -Вып. 3.-С. 218-227.

35. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения // Дискретная математика. 2000. - Том 12, вып. 3. - С.60-71.

36. Кузьмин О.В., Леонова О.В. Некоторые свойства полиномов Тушара // Мат. VII межд. семинара «Дискретная математика и ее