Избранные комбинаторные задачи

Федеральное агентство по образованию

 Государственное образовательное учреждение

 Воронежский Государственный Педагогический Университет

 Кафедра высшей математики 
 
 
 
 
 
 
 
 
 
 
 
 

 Курсовая  работа 

   Избранные комбинаторные  задачи  
 

                                            
 
 

                                    

                                             Выполнила:

                                               ст. 4к. отд. МИ                                                                     

                                                        физ.-мат. факультета

                                                                       Бакаева Ольга Викторовна   

                                                Руководитель:

                                                         доктор физ.-мат. наук

                                                                     профессор В.В.Обуховский  
 
 
 
 
 
 

Воронеж 2011

Введение 

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

     Задачи  работы обусловлены ее целью:

     Во-первых, раскрыть теоретическое содержание данной темы.

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

     Задачи  данной работы:

     •  Изучить комбинаторные характеристики натурального ряда;

     • Ознакомиться с комбинаторными тождествами и методами их доказательства;

     •  Рассмотреть примеры решения комбинаторных задач. 
 
 
 
 
 
 
 
 
 
 

Содержание 

1. Введение……………………………………………………………….2

2. Избранные комбинаторные задачи…………………………………..4

 2.1. Теория………………………………………………………………..4

  2.1.1. Разбиения…………………………………………………………..4

  2.1.2. Перестановки……………………………………………………...1

  2.1.3. Размещения………………………………………………………..1

  2.1.4. Сочетания………………………………………………………….1

  2.1.5. Перестановки с повторениями……………………………………1

  2.1.6. Размещения с повторениями……………………………………...1

  2.1.7. Сочетания с повторениями……………………………………….1 

  2.1.8. Комбинаторные тождества и методы их доказательства………1

 2.2. Примеры решения комбинаторных задач…………………………1

Заключение……………………………………………………………….16

Литература………………………………………………………………..1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 2. Избранные комбинаторные  задачи

 2.1. Теория

 2.1.1. Разбиения

     Разбиением  множества U называется подразделение этого множества на непересекающиеся и исчерпывающие его подмножества, так что каждый элемент и принадлежит одному и только одному из подмножеств. Подмножества   в таком разбиении называются ячейками. Итак [, , …, ] будет разбиением множества U, если выполнены два условия:

1. = 0 при i j (ячейки не пересекаются)
2. … = U (эти ячейки исчерпывают все множество U).

     Пример 1. Если U = {а, b, с, d, е}, то [{а, b}, {с, d, e}], [{b, с, е}, {a}, {d}] и [{а}, {b}, {с}, {d}, {e}] представляют собой три различных разбиения множества U. Последнее из них является разбиением на единичные подмножества.

     Переход от детального анализа множества  логических  возможностей к менее  детальному осуществляется фактически посредством некоторого разбиения. Например, рассмотрим логические возможности для исходов первых трех встреч команд Янки и Доджерс в первенстве США по бейсболу. Перечислим все возможности, указывая победителя каждой игры:

     {ЯЯЯ,  ЯЯД, ЯДЯ, ДЯЯ, ЯДД, ДЯД, ДДЯ,  ДДД}.

     Отнеся  к одной ячейке все исходы с  одинаковым числом побед, одержанных Янки, мы получим разбиение

     [{ЯЯЯ}, {ЯЯД, ЯДЯ, ДЯЯ}, {ЯДД, ДЯД, ДДЯ}, {ДДД}].

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

     Если [, , ..., ] и [, , …, ] — два разбиения одного и того же множества U, то мы получаем новое разбиение, рассматривая систему всех подмножеств U вида В. Это новое разбиение называется измельчением двух первоначальных разбиений.

     Пример 2. Обычно измельчениями разбиений пользуются в проблеме классификации. Например, множество V всех живых форм можно подвергнуть разбиению [Ж, Р], где Ж означает множество всех животных, а Р — множество всех растений. Можно также образовать разбиение [В, С], где В — множество всех вымерших живых форм, а С — множество всех ныне существующих живых форм. Измельчение [Ж В, Ж С, Р В, Р С] дает полную классификацию, соответствующую этим двум разным принципам классификации.

     Многие  из примеров, которые нам встретятся в дальнейшем, связаны с рассмотрением процессов, осуществляемых в несколько этапов. Разбиения и измельчения разбиений служат удобным средством для представления отдельных этапов процесса. Графическим представлением такого процесса служит, естественно, дерево. Например, предположим, что этот процесс состоит в последовательном узнавании значений истинности некоторого ряда высказываний, имеющих отношение к заданной ситуации. Если U—множество логических возможностей для этой ситуации и р — высказывание, относящееся к U, то знание значения истинности ш равносильно знанию того, какая из ячеек разбиения [Р, ] содержит реализующуюся возможность. Напоминаем, что Р — это множество истинности высказывания р, а — множество истинности ~р. Допустим теперь, что мы выяснили значение истинности некоторого второго высказывания q. Эта информация опять-таки может быть описана посредством разбиения, именно [Q, ]. Вместе эти два высказывания дают нам информацию, которая может быть представлена посредством измельчения этих двух разбиений:

     [P Q, P , Q, ].

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

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

     Этим  измельчением будет

     [P Q R, P Q , P R, R, P , Q , R, ,].

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

     Если бы множество U содержало (приблизительно один миллион) логических возможностей и если бы мы могли задавать вопросы, требующие ответа «да» или «нет», таким образом, чтобы знание значения истинности для каждого вопроса сокращало бы каждый раз число возможностей вдвое, то посредством двадцати вопросов мы смогли бы определить любую заданную возможность из множества U. Мы можем осуществить такой опрос, например, в случае, когда у нас имеется перечень всех возможностей и нам разрешается спрашивать «Лежит ли реализующаяся возможность в первой половине списка возможностей?», и если ответ утвердительный, то «Лежит ли она в первой четверти?» и т. д. На практике, как правило, у нас не имеется такого перечня, и мы можем осуществить указанную процедуру лишь приближенно.

     Пример 3. В известной игре «двадцать вопросов» (эта игра требует от «водящего» определения заданного объекта с помощью 20 вопросов, на которые ему отвечают лишь «да» или «нет») является весьма обычной ситуация, когда отгадывающий стремится произвести разбиение описанного выше типа. Например, предположим, что задан какой-либо город. Отгадывающий может спросить: «Этот город в Северной Америке?», и если ответ утвердительный, то: «Он в Соединенных Штатах?», и если последует ответ «да», то: «Он лежит к западу от Миссисипи?», и если последует ответ «нет», то: «Он относится к Новой Англии?» (Так называют густонаселенный район на северо-востоке Соединенных Штатов, включающий в себя 6 штатов; этот район явился первым объектом европейской колонизации на территории США), и т. д. Конечно, на самом деле при такой процедуре не происходит разделения возможностей в точности пополам. Если число всех возможностей не превышает миллиона, то с тем большей уверенностью можно ожидать получения ответа после двадцати вопросов, чем точнее разделение возможностей на две равные части в результате каждого из них.

      

     2.1.2.Перестановки

     В математике и в ее приложениях  нередко рассматриваются  множества (мы ограничиваемся лишь конечными  множествами) упорядоченные, элементы которых задаются «в определенном порядке». Так, например, алфавит есть упорядоченное множество букв: в алфавите буквы выписываются в определенном порядке. Так, в русском алфавите буква б следует за а, в следует за б и т. д., буква а (первая) не следует ни за какой буквой, а за буквой я (последняя) не следует ни одной буквы. Понятие упорядоченного конечного множества изучается в арифметике, поэтому мы ограничимся лишь указанием ряда необходимых для дальнейших положений.

     Для упорядоченного конечного множества установлено понятие непосредственного следования элементов, при этом:

     1°.  Существует единственный первый элемент, не следующий ни за одним элементом множества.

     2°.  Существует единственный последний  элемент, за которым не следует ни один элемент множества.

     3°.  За всяким элементом, отличным  от последнего, непосредственно  следует единственный элемент упорядоченного множества.

     4°.  Конечное упорядоченное множество, содержащее n элементов, может быть приведено во взаимно однозначное соответствие с n первыми числами натурального ряда

     1, 2, ..., n,

причем  первому элементу ставится в соответствие число 1, последнему число n; если некоторому элементу поставлено в соответствие число k, то непосредственно следующему за ним поставлено в соответствие число k + 1. Это соответствие называется нумерацией элементов данного множества.

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

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

     Всякое  данное множество, содержащее более  одного элемента, может быть упорядочено  несколькими способами. Иными словами, из данных n>1 элементов можно образовать различные перестановки.