Файл: Комбинаторика это раздел дискретной математики, в котором изучаются вопросы о том, сколько различных комбинаций можно составить из заданных элементов (объектах) с учетом тех или иных условий..pdf


Комбинаторика – это раздел дискретной математики, в котором изучаются вопросы о том, сколько различных комбинаций можно составить из заданных элементов (объектах) с учетом тех или иных условий.

Комбинаторика возникла в XVII веке.
Первоначально комбинаторные задачи касались в основном азартных игр.


Сочетания

Перестановки

С повторением

Без повторения

Размещения

С повторением

Без повторения
Комбинаторные конфигурации

Опр. Перестановкой без повторений из n элементов называется всякий кортеж длины n из n разных заданных элементов.
Р
n
= n!
Задача №1.
Сколькими способами 4 человека могут разместиться на четырехместной скамейке?
Решение:
Р
4
= 1* 2* 3* 4=24
Ответ: 24.

Задача №2.
Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из чисел 0,2, 4.6?
Решение: из цифр 0,2.4.6 можно составить Р
4
перестановок. Из этого числа нужно исключить те перестановки, которые начинаются с 0.
Число таких перестановок Р
3
. Значит искомое число четырехзначных чисел, которые можно составить из цифр 0,2,4,6 равно:
Р
4
– Р
3
= 4!-3!= 1*2*3*4-1*2*3=24-6=18
Ответ: 18.

Задача №3.
Имеются 9 различных книг, четыре из которых учебники.
Сколькими способами можно расставить книги на полке так, чтобы все учебники стояли рядом?
Решение: сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 9, а
6 книг. Это можно сделать Р
6
способами.
И в каждой из полученных комбинаций можно выполнить Р
4
перестановок учебников. Значит, искомое число способов расположения книг равно произведению: Р
6
*Р
4
= 1*2*3*4*5*6*1*2*3*4 =17280
Ответ: 17280

Опр. Перестановкой с повторениями из n элементов называется всякая последовательность длины n, состоящей из элементов заданного множества.
????
????
????
1,
????
2,
… , ????
????
=
????!
????
1
! ????
2
! … ????
????
!
Пример: Сколько различных слов можно составить переставляя буквы слова «ротор»?
Решение:
n
1
= 2
n
2
= 2
n
3
= 1
Искомое число: ????
5 2, 2, 1 =
5!
1!2!3!
= 30
Ответ: 30

Опр. Размещение без повторений из n элементов по к элементов называется всякий кортеж длинны к из разных заданных элементов.
А или ????
????
????
=
????!
????−???? !
Задача 4.
Учащиеся второго класса изучают 8 предметов.
Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета.
Решение:????
8 4
= 8 ∗ 7 ∗ 6 ∗ 5 = 1680(способов).
Ответ: 1680

Задача 5.
Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5 и 6?
Решение: если среди семи цифр нет нуля, то число трехзначных чисел которые можно составить из этих цифр равно числу размещений из 7 элементов по 3 А .
Однако, среди данных семи чисел есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 нужно исключить те, у которых первым элементом является цифра 0.Их число равно числу размещений из 6 элементов по 2.
Значит, искомое число равно: ????
7 3
-????
6 2
=7*6*5-6*5=180
Ответ: 180

Задача 6.
Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от 0?
Решение:????
10 7
-????
9 6
=10*9*8*7*6*5*4-9*8*7*6*5*4=544320
Ответ:544320

Опр. Сочетанием из n элементов по k называется каждое k-элементное подмножество данного n элементного множества.
????
????
????
=
????!
????! ????−???? !
Задача 7.
Из 15 человек туристической группы надо выбрать трех дежурных. Сколькими способами это можно сделать?
Решение:????
15 3
=
15!
3! 15−3 !
=455
Ответ: 455

Задача 8.
Из вазы с фруктами, где лежат 9 яблок и 6 груш, нужно выбрать 3 яблока и 2 груши. Сколькими способами можно это сделать?
Решение: 3 яблока из 9-ти можно выбрать. С способами. При каждом выборе яблок груши можно выбрать С способами. Поэтому по правилу умножения выбор фруктов можно сделать С способами.
Решение:????
9 3
∗ ????
6 2
=
9!∗6!
3!∗6!∗2!∗4!
=1260
Ответ: 1260

Задача 9.
В лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить в командировку 5 человек.
Сколькими способами это можно сделать, если: а) заведующий лабораторией должен ехать в командировку;
б) заведующий должен остаться.
Решение:
а) ????
10 4
=
10!
4!∗6!
=210 б) ????
10 5
=
10!
5!∗5!
=252

Обратимся теперь к истории появления графов.
Впервые в рассмотрение их ввел великий математик
Леонард Эйлер. Это был один из крупнейших математиков XVIII . Он родился в швейцарском городе
Базеле, где в 15 лет закончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли.
Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения.

Графом называется конечное множество точек, некоторые из которых соединены линиями.
Точки называются вершинами графа, а соединяющие линии – рёбрами.
Количество рёбер, выходящих из вершины графа, называется степенью вершины.
Предложение 1.
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Предложение 2.
Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.
Эта закономерность справедлива не только для полного, но и для любого графа.

Теорема.
Число нечетных вершин любого графа четно.
Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым (уникурсальным).
Предложение 3.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф.
Движение можно начать с любой вершины и закончить его в той же вершине.

Предложение 4.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Предложение 5.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».

Задача 1. Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба 10 см?
Решение. Куб имеет 12 ребер, сумма длин которых равна 120 см. Если бы была возможность из проволоки длиной 120 см, не ломая ее изготовить каркас этого куба, то это означало бы, что граф состоящий из вершин и ребер куба, является уникурсальным. Но так как этот граф имеет 8 вершин третьей степени, то по теореме, приведенной выше, для его изображения необходимо 4 росчерка. Итак, ответ к задаче –
отрицательный. Заметим, что для изготовления куба с ребром
10 см необходимо либо проволоку 120 см разрезать 3 раза, либо использовать кусок проволоки длиной 150 см и по каким-то трем ребрам проложить ее дважды.
(Исп. предложение 6)

Задача 2.
Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это? Нарисуйте если да.
Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Задача 3
В первенстве класса по настольному теннису 6 участников: Андрей, Борис
Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с
Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с
Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом.
Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение:
Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8.
Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Задача 4. «Сколько можно составить различных трехзначных чисел, удовлетворяющих условию:
а) первая цифра 7;
б) вторая цифра делится на 3;
в) число кратно 2».
Решение.
Ответ: 15

Задача 5.
В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9.
Путешественник обнаружил, что два города соединены авиалинией тогда и только тогда, когда двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли из города 1 добраться в город 9?
Решение. Покажем возможные маршруты, нарисовав граф. И в этой задаче 1 и 9 попали в две разных части графа. Ясно, что в правой части графа сгруппировались города-цифры нацело делящиеся на 3, а в левой части графа ребра соединяют две цифры: одну — делящуюся на 3 с остатком 1, а другую — делящуюся на 3 с остатком 2.
Примечание. Отметим, что один и тот же граф можно нарисовать по- разному. Если учащиеся одного класса нарисуют графы к одной задаче, то мы можем получить столько графов, сколько учащихся их рисовали.
Нарисованные по-разному графы (если они нарисованы без ошибок) принято называть изоморфными. Любой читатель может нарисовать бесконечное множество изоморфных графов.

Правило. Для подсчета числа ребер графа необходимо просуммировать степени вершин и полученный результат разделить на два.
Следствие. Сумма степеней всех вершин графа должна быть четной (иначе ее нельзя было бы разделить на 2 нацело).
Теорема. Число нечетных вершин любого графа —
четно.

Задача 6.
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей.
Примечание. Если Петя друг Васи, то Вася - друг
Пети.
Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3; 11 — степень 4; 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

Задача 7.
В деревне есть 15 телефонов, а АТС отсутствует. Можно ли телефоны соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Решение. Предположим, что это возможно. Рассмотрим граф,
вершины которого соответствуют телефонам, а ребра —
соединяющим их проводам. В этом графе
(15 *5) /2 вершин, степень каждой из которой равна пяти.
Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

Ориентированный граф или орграф называется граф, у которого множество ребер является множеством упорядоченных пар.
Началом ребра называется вершина, указанная в паре первой, концом – вторая этой пары (графически она указана стрелкой).
Орграф часто будем обозначать парой (V,E), где V –
множество вершин, Е – множество дуг графа. Если дуга е,
соединяющая вершины x и y, ориентирована от х и y, то будем говорить, что х – начало дуги и х – конец дуги е, или что дуга е выходит из х и заходит в y. Такую дугу е будем иногда называть (x,y)–дугой.
Вершины x и y будем называть смежными, если существует
(x,y)–дуга или (y,x)–дуга. Если дуга е соединяет вершины x и y, то будем говорить, что инцидентна вершинам x и y.
Дугу, выходящую из некоторой вершины и заходящую в ту же вершину, будем называть петлей, а дуги, выходящие из одной и той же вершины и заходящие в одну и ту же вершину, будем называть кратными.