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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

 

                                         

 

 

 

                                 

 

                                            Выполнила:

                                              ст. 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 элементов можно образовать различные перестановки.

Пример

Ниже выписаны всевозможные перестановки из четырех элементов:

 

1 2 3 4	2 1 3 4	3 1 2 4	4 1 2 3
1 2 4 3	2 1 4 3	3 1 4 2	4 1 3 2
1 3 2 4	2 3 1 4	3 2 1 4	4 2 1 3
1 3 4 2	2 3 4 1	3 2 4 1	4 2 3 1
1 4 3 2	2 4 1 3	3 4 1 2	4 3 1 2
1 4 2 3	2 4 3 1	3 4 2 1	4 3 2 1

 

Теорема. Число всевозможных перестановок, которые могут быть образованы из п элементов, равно:

n! = 1

2 …. n.

Пример 

Сколько различных чисел  можно составить из цифр

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

причем:

a) каждая цифра в обозначении  числа встречается один раз 

b) цифра 0 не должна занимать первое место?

Решение. Если не принимать во внимание условие b), то из 10 цифр можно составить 10! различных чисел, в которых каждая цифра содержится один раз. Из общего количества полученных чисел 9! чисел начинаются цифрой 0. Следовательно, искомое количество чисел равно:

10!- 9! = 9 9! = 1 2 3 4 5 6 7 8 = 3 265 920.

 

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

Определение. Размещением из n элементов по k называется всякая упорядоченная часть данного множество n элементов, содержащая k элементов.

Два различные размещения из данных n элементов, взятых по k, различаются либо составом входящих в них элементов, либо при одном (и том же составе элементов порядком их расположения.

Число различных размещений, взятых из n элементов по k обозначается символом .

Пример 

Ниже выписаны всевозможные размещения, составленные из четырех элементов по 3

1 2 3	1 2 4	1 3 4	2 3 4
1 3 2	1 4 2	1 4 3	2 4 3
2 1 3	2 1 4	3 1 4	3 2 4
2 3 1	2 4 1	3 4 1	3 4 2
3 1 2	4 1 2	4 1 3	4 1 3
3 2 1	4 2 1	4 3 1	4 3 1

Теорема. Число различных размещений, взятых из n элементов по k, выражается формулой:

= n(n — 1)(n — 2) … (n — k + l) = .

Пример 

Сколько различных натуральных  чисел можно составить из цифр 0, 1, 2, 3, 4, если в обозначении каждого числа каждая из данных цифр входит не более одного раза?

Решение. Из пяти данных цифр можно составить = 5! различных размещений; эти размещения дадут всевозможные пятизначные числа за исключением тех размещений, которые начинаются нулем. Количество этих последних размещений равно . Таким образом, из данных цифр можно составить:

 —  = 5

4 3 2 1 — 4 3 2 1 = 96

различных пятизначных чисел. Количество различных четырехзначных чисел, которые можно составить из цифр 0, 1,  2, 3, 4, равно за вычетом количества тех размещений, которые начинаются нулем, т. е.

 —  = 5 4

3 2 — 4 3 2 = 96.

Аналогично количество различных  трехзначных, двузначных и однозначных  чисел будет равно соответственно

 —  = 48      — = 16   и   4

Всего получится 260 натуральных  чисел.

 

2.1.4. Сочетания

Пусть µ  некоторое конечное множество, состоящее из n элементов:

{a, b, …, c}.

Определение. Сочетанием из n элементов, взятых по k, называется всякая часть, содержащая k элементов данного множества µ, состоящего из n элементов.

Два различные сочетания из данных n элементов, взятых по k, отличаются составом входящих в них элементов: именно, если два сочетания различны, то в одном из них содержится хотя бы один элемент, не содержащийся в другом.

Пример 

Ниже выписаны всевозможные сочетания, составленные из 5 элементов 1, 2, 3, 4, по 3:

123, 124, 125, 134,135, 145

234, 235, 245

345

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

1, 2, 3, ..., n.

Это множество натуральных  чисел будет служить представителем класса конечных множеств, содержащих n элементов.

Символом  обозначается число различных сочетаний из n элементов, взятых по k.

Так, например,   есть число частей множества n элементов 1, 2, ..., n, взятых по одному, эти части по сути сами элементы 1, 2, 3, ..., , количество таких частей равно n:

 =n.

Далее, есть число частeй рассматриваемого множества, содержащих по 2 элемента, все такие части можно вписать в следующую таблицу:

 

{1, 2},	{1, 3},	{1, 4},	…,	{1, n},
	{2, 3},	{2, 4},	…,	{2, n},
		{3, 4},	…,	{3, n},
		……………
				{n-1, n}.

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

 

{1, 2},	{1, 3},	…,	{1, n},
{2, 1},	{2, 3},	…,	{2, n},
…………………….
{n-1, 1},	{n-1, 2},	…,	{n-1, n},
{n, 1},	{n, 2},	…,	{n, n-1}.

 

В этой таблице каждая пара выписана 2 раза, так, например, взяв элемент 1, присоединив к нему элемент 2, получим {1, 2} ту же пару {2, 1} получим, взяв элемент 2 и присоединив к нему 1. Число всех строк таблицы равно n, число столбцов n-1, общее число всех пар n(n-1), из которых различными являются пар, следовательно:

= .

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

= 1.

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

=1.

В дальнейшем мы будем пользоваться следующим общепринятым обозначением.

Если m — натуральное число, отличное от 1, то символом m! обозначается произведение всех натуральных чисел, не больших m;

m! = 1

2 ... m.

Если m = 1, то считаем 1! = 1.

Если m = 0, то считается 0! = 1.

Для отрицательных и для дробных значений m символу m! (в элементарной алгебре) не приписывается никакого смысла.

Теорема. Число сочетаний из n элементов по k, где 0 k n равно:

 =   или при k

0 = .

Пример 

Найти число диагоналей n-угольника.

Решение. Вершины многоугольника образуют множество n точек плоскости, из которых никакие три не лежат на одной прямой. Соединив всевозможными способами попарно эти точки, получим:

=

отрезков, из которых n отрезков являются сторонами многоугольника, а прочие

   — n =

его диагоналями.

 

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

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

Пусть {a, b, …, c} — некоторое данное множество (конечное) элементов.

Определение. Перестановкой с повторениями, в которой элемент а повторяется α раз, элемент b повторяется β раз и т. д., элемент с повторяется γ раз, где α, β, …, γ — данные числа, называется всякое размещение с повторениями, составленное из данных элементов, в котором каждый из элементов повторяется указанное число раз. Число m = α + β + ... + γ называется порядком перестановки.

Пример

Ниже выписаны все перестановки, в которых элементы a, b и с повторяются 2, 2 и 1 раз (соответственно)

aabbc	aabcb	aacbb	ababc	abacb
abbac	abbca	abcab	abcba	acabb
acbab	acbba	baabc	baacb	babac
babca	bacab	bacba	bbaac	bbaca
bbcaa	bcaba	bcaba	bcbaa	caabb
cabab	cabba	cbaab	cbaba	cbbaa

 

Теорема. Число различных перестановок с повторениями из элементов {a, b, …, c}, в которых элементы a, b, …, c повторяются соответственно α, β, …, γ раз, равно:

 

Пример 

Дано p + q + r различных предметов; сколькими способами можно разбить эти предметы на 3 группы так, чтобы первая группа содержала р предметов, вторая q предметов, а третья r предметов?

Решение. Расположим все данные предметы в каком-нибудь определенном порядке:

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

2  1  2  3 ... 1

означает, что первый предмет  попал во вторую группу, второй в  первую, третий во вторую и т. д., последний  в первую. Всякому распределению  предметов по группам взаимно  однозначно соответствует перестановка из чисел 1, 2, 3, в которой 1 встречается p раз, 2 встречается q раз и 3 встречается r раз. Число возможных способов распределения предметов равно:

 

 

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

Термином «размещение  с повторениями», составленным из данных элементов:

, , … ,

по k в комбинаторике называется всякая конечная k-членная последовательность, членами которой являются данные элементы (а).

Два размещения с повторениями:

, , … ,   и , , … ,

одинаковы б том и только в том случае, когда на одинаковых местах находятся одни и те же элементы:

= ,  = , … , =.

В размещении с повторениями (как и во всякой последовательности) один и тот же элемент может находиться на нескольких различных местах. Если в размещении с повторениями , , … ,   некоторый элемент занимает р различных мест, то говорят, что этот элемент повторяется в размещении р раз.

Пример 

Ниже выписаны всевозможные размещения с повторениями из 4 элементов 1, 2, 3, 4 по 3:

111 112 121 211 113 131 311 114 141 411 222 221 212 223 232

322 224 242 422 333 331 313 133 332 323 134 343 433 444 441

414 144 442 424 244 123 124 213 214 132 334 443 434 344 312

314 142 143 412 413 241 243 421 423 431 432 342 341 321 324

231 234 122  233

 

Теорема. Число всевозможных размещений с повторениями из n элементов по k равно:

.

Пример 

Имеется n различных книг, каждая в р экземплярах; сколькими способами можно сделать выбор книг из числа данных?

Решение. Перенумеруем в каком-либо порядке n данных книг. Если первая книга берется в экземплярах, вторая в экземплярах и т. д. n-я в экземплярах, то указанному выбору соответствует размещение с повторениями:

, , … ,

из р+1 чисел 0, 1, 2, ..., р, взятых по n (если = 0, то i-я книга не берется вовсе). Таким образом получается различных комбинаций, по числу размещений с повторениями из р+1 элементов по n. Исключив из рассмотрения комбинацию 0, 0, ..., 0, означающую, что не берется ни одна книга, мы получим — 1 различных способов выбора книг.

 

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

Пусть а, b, с,..., d — данное конечное множество, содержащее n элементов. Поставим в соответствие каждому элементу этого множества некоторое целое неотрицательное число, называемое кратностью данного элемента. Это соответствие определяет функцию, для которой значениями аргумента являются данные элементы, а значениями функции — целые неотрицательные числа — кратности элементов. Пусть α — кратность элемента а, β — кратность элемента b, γ — кратность элемента с и т. д. Для обозначения рассматриваемого соответствия выписывают символ, обозначающий данный элемент столько раз, какова его кратность, если эта кратность положительна, если же кратность данного элемента равна нулю, то соответствующий символ не выписывается. Символы, обозначающие элементы, можно писать в каком угодно порядке, лишь бы каждый из них был написан столько раз, какова кратность соответствующего элемента. Так, например, записи