Комбинаторика

1. КОМБИНАТОРИКА

Основные понятия, определения и решение задач.
Составитель учитель математики МАОУ СОШ № 40
САЛИЙ ВАЛЕНТИНА ПАВЛОВНА

2. Что изучает комбинаторика?

• В науке и практике часто встречаются задачи, решая
которые приходится составлять различные комбинации из
конечного числа элементов и подсчитывать число
комбинаций. Такие задачи получили название
комбинаторных задач, а раздел математики, в котором
рассматриваются подобные задачи, называют
комбинаторикой. Слово «комбинаторика» происходит от
латинского слова combinare, которое означает «соединять,
сочетать».

3. Пример 1

• Из группы теннисистов, в которую входят четыре человека
– Антонов, Григорьев, Сергеев и Федоров, тренер
выделяет пару для участия в соревнованиях. Сколько
существует вариантов выбора такой пары?

4. Решение

• Составим сначала все пары, в которые входит
Антонов (для краткости будем писать первые
буквы фамилий). Получим три пары : АГ, АС, АФ.
Выпишем пары, в которые входит Григорьев, но
не входит Антонов : ГС, ГФ. Далее составим пары,
в которые входит Сергеев, но не входят Антонов и
Григорьев : СФ. Других вариантов нет. Итак,
получили шесть пар : АГ, АС, АФ,ГС,ГФ,СФ.
• Способ рассуждений, которым решена задача,
называют перебором возможных вариантов.

5. Пример 2

• Четыре ученика класса Миша, Саша,
Алёша, Таня углублённо изучают
математику. На математическую
олимпиаду требуется послать двух
учеников. Сколькими способами это можно
сделать?

6.

7. Пример 3

• В меню столовой три первых блюда А1 ,А2
А3, два вторых В1, В2 и три сока С1, С2, С3.
Сколько вариантов комплексного обеда
можно составить из этих блюд?

8. Решение

9. Решите задачи

• №1 У Ирины пять подруг: Вера, Зоя, Марина,
Полина и Светлана. Она решила двух из них
пригласить в кино. Укажите все возможные
варианты выбора подруг. Сколько таких
вариантов?
• №2 Стадион имеет четыре выхода: А, В, С,Д.
Укажите все возможные способы, какими
посетитель может войти через один выход , а
выйти через другой. Сколько таких способов?

10.

№3 Из цифр 1,2,3 составьте все возможные
двузначные числа при условии, что:
а) цифры в числе не повторяются;
б) допускается повторение цифр в числе.

11. Решение задач

• №1. ВЗ, ВМ, ВП, ВС; ЗМ,ЗП,ЗС; МП,МС; ПС.
Всего 10 вариантов.
• №2 АВ, АС, АД; ВС, ВД,СД;
ВА,СА,ДА,СВ,ДВ,ДС. Всего12 вариантов.
• №3 а)12, 13, 23,21,31,32.
• б) 11,12,13,22,21,23,31.32,33.

12. Пример 4

• В посёлке имеется 5 светофоров. Каждый
может находиться в одном из трёх
состояний (гореть красным, зелёным или
жёлтым светом). Сколькими способами
можно зажечь все светофоры?

13. Решение

• Первый светофор может быть включён тремя
разными способами. Для каждого способа
включения первого светофора можно получить 3
способа включения второго светофора, т.е. будем
иметь 3 • 3 способов включения двух светофоров.
Из всякого способа включения двух светофоров
снова можно получить три способа включения
третьего светофора, изменяя его состояние, всего
получаем 3 • 3 • 3 способов включения трёх
светофоров. При включении каждого нового
светофора число способов увеличивается в три
раза. Значит, пять светофоров могут быть включены
3 • 3 • 3 • 3 • 3 = З5 способами. Ответ: 243 способа.

14. Правила сложения и умножение

• Задачи комбинаторики решаются проще,
если использовать комбинаторные
правила сложения и умножения. Пусть
даны два непересекающихся множества
элементов: А ={a1 а2, ..,аn} и B ={Ь1, Ь2, .., Ьn }.

15. Правило сложения.

• Если элемент а(а ϵ А) может быть выбран n
способами, а элемент Ь(Ь ϵ В) может быть
выбран m способами, то число способов,
которыми можно выбрать один элемент из
множества А или множества B, равно сумме
n + m.

16. Пример 5

• В одном классе 25 учеников, в другом — 27
учеников. Сколькими способами можно
выбрать одного ученика из двух классов?

17. Решение

• Решение. 25 + 27 = 52. Ответ: 52.

18. Пример 6

• Для проезда из города М в город N можно
воспользоваться 5 автобусными
маршрутами или 3 железнодорожными.
Сколькими способами можно проехать из
города М в город N?

19. Решение

• Решение. По формуле сложения количество
способов равно сумме 5 + 3 = 8. Ответ: 8.

20. Правило умножения (основное правило комбинаторики).

• Если элемент а(а ϵ А) может быть выбран n
способами, а элемент b (b ϵ В) после
каждого выбора элемента а может быть
выбран m способами, то число способов,
которыми можно выбрать пару элементов а
и b в указанном порядке по одному из
каждого множества, равно произведению
n •m.

21. Пример 7

• В одном классе 25 учеников, в другом — 27
учеников. Сколькими способами можно
выбрать двух учеников по одному из
каждого класса?

22. Решение

• Одного ученика первого класса можно
выбрать 25 способами, а второго класса —
27 способами. Двух учеников по одному из
каждого класса (по правилу умножения)
можно выбрать 25 • 27 способами; 25 • 27
= 675. Ответ: 675.

23. Пример 8

• На книжной полке стоит 6 исторических
романов и 4 приключенческих. Сколькими
способами можно взять с полки 2 книги
разных жанров?

24. Решение

• По правилу умножения существует 6 • 4
способов взять с полки 2 книги разных
жанров. Ответ: 24.

25. Правило умножения в общем виде.

• Пусть имеем n элементов, из которых
требуется выбрать один за другим некоторые
k элементов. Если первый элемент можно
выбрать n1 способами, после чего второй
элемент можно выбрать n2 способами, затем
третий элемент — n3 способами и т.д., то число
способов, которыми могут быть выбраны все k
элементов, равно произведению
n1 • n2 • n3 • ... • nk.

26. Пример 9

• Собрание из 30 человек должно выбрать
председателя и секретаря. Сколькими
способами это можно сделать?

27. Решение

• Председателем собрания можно выбрать
30 способами, после чего секретаря — 29
способами (из 29 оставшихся членов
собрания). По правилу умножения
существует 30 • 29 способов выбора
председателя и секретаря. 30•29 = 870.
Ответ: 870.

28. Пример 10

• Сколькими способами можно рассадить 5
гостей за праздничным столом, если
приготовлено 8 мест?

29. Решение

• Для первого гостя имеется 8 возможностей
выбрать место. После выбора места
первым, для второго гостя остаётся 7
возможностей, аналогично для третьего
гостя — 6 возможностей (из 6 свободных
мест), для четвёртого — 5 вариантов, для
пятого — 4. По правилу умножения
получаем 8 • 7 • 6 • 5 • 4 = 6720 способов
рассадить гостей. Ответ: 6720.

30. Пример 11

• Из 10 членов шахматного кружка требуется
составить команду из 3 человек для участия
в соревнованиях. Сколькими способами
это можно сделать?

31. Решение

• Первого члена команды (на первую доску)
можно выбрать 10 способами, после чего
второго (на вторую доску) — 9 способами,
а третьего (на третью доску) — 8
способами. Всего получаем 10 • 9 • 8= 720
вариантов выбора трёх шахматистов из
десяти. Ответ: 720.

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

• Перестановкой называется конечное
множество, в котором установлен порядок
его элементов. Число перестановок из n
элементов обозначают символом Рn (от
французского слова permutation —
«перестановка»).

33. Формула для вычисления перестановок

• Число перестановок из n элементов равно
произведению всех натуральных чисел от
1 до n;
• Рn = n!.

34. Пример 12

• Сколькими способами семья из 5 человек
может занять пять спальных мест в
пятиместном гостиничном номере?

35. Решение

• Р5=1 • 2 • 3 • 4 • 5 = 120.
• Ответ: 120.

36. Пример 13

• Каким числом способов 8 человек могут
находиться в очереди?

37. Решение

• Р8=1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 = 40 320.
Ответ: 40 320.

38. Пример 14

• Сколько различных четырёхзначных чисел
можно составить из цифр 9, 7, 5, 0, если в
каждом числе все цифры должны быть
разными?

39. Решение

• Если бы среди данных цифр не было нуля, то
количество составленных из них четырёхзначных
чисел (без повтора цифр в каждом числе) было бы
равно количеству перестановок из 4 элементов:
• Р4 = 1 • 2 • 3 • 4 = 24.
• Целое число не может начинаться цифрой 0. Среди
найденных 24 чисел с цифры 0 будет начинаться
столько чисел, сколько существует перестановок из
3 элементов (цифр 9, 7, 5): Р3 = 1 • 2 • 3 = 6.
• Значит, четырёхзначных чисел, составленных из
данных цифр, будет Р4 - Р3 = 24 - 6 = 18. Ответ: 18.

40. Пример 15

• 9 мальчиков купили 9 билетов в театр.
Сколькими способами они могут занять 9
кресел в театральном ряду, если Миша,
Петя и Ваня обязательно хотят сидеть
рядом (в любом порядке).

41. Решение

• Будем считать трёх неразлучных друзей (Мишу, Петю и Ваню)
как один элемент общей компании, а три занятых ими кресла —
как одно место. Тогда можем считать, что размещаем 7 человек
в 7 креслах. Это можно сделать столькими способами, каково
число перестановок из 7 элементов: Р7 =1 • 2 • 3 • 4 • 5 • 6 • 7 =
5040.
• В то же время трое друзей (Миша, Петя и Ваня) в своих трёх
креслах могут распределиться Р3 способами
• Р3 = 1 • 2 • 3 = 6.
• Таким образом, каждой перестановке из 7 элементов
соответствует любая перестановка из трёх элементов. Всего
перестановок по правилу умножения будет
• Р7 • Р3 = 5040 • 6 = 30 240.
• Ответ: 30 240.

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

43. Обозначение

44. Формула для вычисления размещений

45. Пример 16

• Учащиеся класса изучают 11 различных
предметов. Сколькими способами можно
составить расписание на один день, чтобы
в нём было 5 различных предметов?

46.

47. Пример 17

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

48.

49. Пример 18

• Сколькими способами 10 человек могут
занять четыре кресла, имеющиеся в
комнате?

50.

51. Пример 19

• В одиннадцатом классе 25 учащихся. На
выпускном вечере ребята обменялись друг
с другом фотокарточками. Сколько всего
было роздано фотокарточек?

52.

53. Сочетания

• Сочетанием из n элементов по k называется
любое множество, составленное из k
элементов, выбранных из данных п
элементов. В отличие от размещений,
сочетания различаются только элементами,
и не имеет значения, в каком порядке
заданы элементы.
• Например, {а, Ь, с} и {Ь, с, а} — одно и то же
сочетание.

54. Формула для вычисления сочетаний

55. Пример 20

• В вазе стоят 10 красных и 5 белых роз.
• а) Сколькими способами можно составить
букет из 3 роз?
• б) Сколькими способами можно составить
букет из 1 красной и 2 белых роз?

56.

57. Пример 21

• Из 9 мальчиков и 11 девочек спортивного
класса для участия в соревнованиях надо
составить команду, в которую должны
входить 3 мальчика и 3 девочки.
Сколькими способами это можно сделать?

58. Решение

59. Пример 22

На витрине магазина выставлено 6 сортов
сыра и 5 видов йогурта. Покупателю
требуется 2 куска сыра разных сортов и 3
йогурта разного вида. Сколькими
способами покупатель может составить
свою покупку?

60. Решение

61. Решите задачи

• 1. Для проезда из города М в город N можно
воспользоваться 5 автобусными маршрутами или 3
железнодорожными. Сколькими способами можно
проехать из города М в город N?
• 2. Из города А в город С можно проехать лишь с
пересадкой в городе Б. Из А в Б существуют 3
автобусных маршрута и 2 железнодорожных. Из Б в С
можно проехать 4 поездами или 2 автобусами. Сколько
существует вариантов проезда из города А в город С?
• 3. Из 5 первокурсников, 7 второкурсников и 10
третьекурсников надо выбрать трёх студентов на
конференцию. Сколькими способами это можно
сделать, если студенты должны быть разных курсов?

62. Решение задач

• 1. По формуле сложения количество
способов равно сумме 5 + 3 = 8. Ответ: 8.
• 2. Из А в Б можно проехать 3 + 2 = 5
способами, а из Б в С — 6 способами
(4 + 2 = 6). По формуле умножения из А в С
можно проехать 5 • 6 = 30 способами.
Ответ: 30.
• 3.По теореме умножения получаем 5•7•10
= 350 способов. Ответ: 350.

63. Решите задачи

• 4. Сколькими способами можно расставить на
полке 10 различных книг?
• 5. На полке стоит 8 разных книг по математике и 2
разные книги по физике. Сколькими способами
можно расставить эти книги, если книги по физике
должны стоять рядом?
• 6. Сколькими способами можно расставить на
полке 7 различных книг так, чтобы определённые
три книги стояли рядом?
• 7. Сколькими способами можно расставить на
полке 7 различных книг, чтобы определённые 3
книги не стояли рядом?

64. Решение задач 4,5

• 4. Количество способов равно числу перестановок
из 10 элементов. Р10 = 10! = 1 • 2 • 3 • 4 • 5 • 6 • 7
8 • 9 • 10 = 3 628 800. Ответ: 3 628 800.
• 5. Будем рассматривать 2 книги по физике как одну
книгу. Тогда 9 книг можно расставить Р9 способами.
Далее 2 книги по физике можно в каждом случае
поставить двумя разными способами. По правилу
умножения общее количество вариантов равно 2
Р9 = 2 • 9! = 2 • 1 • 2 3 • 4 • 5 • 6 • 7 • 8 9 = 725 760.
Ответ: 725 760.

65. Решение задачи 6

• Если 3 указанные книги рассматривать как
одну книгу, то 5 книг (7-3 + 1 = 5) можно
расставить Р5 способами. Затем для
каждого полученного способа имеем Р3
способов расстановки 3 книг. По правилу
умножения всего будет Р5 • Р3 вариантов
расстановки книг согласно условию задачи.
Р5 • Р3 = 5! • 3! = 1 • 2 • 3 • 4 • 5 • 1 • 2 • 3 =
720. Ответ: 720.

66. Решение задачи 7

• 7 книг можно расставить на полке Р7
способами; Р7 = 1 • 2 • 3 • 4 • 5 • 6 • 7 =
5040. В 720 случаях указанные книги будут
стоять рядом (см. задачу 6). Значит, в
остальных случаях будут выполняться
условия данной задачи. 5040 - 720 = 4320.
Ответ: 4320.

67. Решите задачи

• 8. Сколькими способами можно рассадить 4 учащихся на 20
местах?
• 9. Требуется распределить 4 путевки на 4 различные турбазы
среди 9 работников. Каким количеством способов можно это
сделать?
• 10. Сколько трёхзначных чисел можно составить из цифр 9, 8, 7,
6, 2, если цифры в числе не повторяются?
• 11. Ученики 6 класса изучают 11 различных учебных предметов.
Сколькими способами можно составить расписание из 5
различных предметов на понедельник, если математика
должна быть вторым уроком?
• 12. Сколькими способами можно рассадить 6 пассажиров в
разные вагоны (по одному в вагон), если в составе поезда 11
вагонов?

68. Задача 8

Задача 9
Задача 10

69. Задача 11

3адача 12

70. Задача 13

• Сколько существует пятизначных чисел с
неповторяющимися цифрами, которые
делятся на 10?

71. Способы решения задачи 13

72. Задача 14

• Сколько существует двузначных чисел с
неповторяющимися цифрами, у которых
обе цифры чётные?

73. Задача 15

• Из 16 рабочих надо выделить 5 для
выполнения некоторой работы. Сколькими
способами это можно сделать?

74. Задача 16

• На плоскости даны 9 точек, никакие 3 из
них не лежат на одной прямой. Сколько
прямых можно провести, соединяя точки
попарно?

75. Задача 17

• Сколькими способами можно составить
букет из 5 цветков, если имеем 8 ромашек
и 7 васильков?

76. Задача 18

• Сколькими способами можно разделить
группу из 15 человек на 2 группы так, чтобы
в одной было 10 человек, а в другой — 5?

77. Задача 19

• Сколькими способами читатель библиотеки
может выбрать 3 книги из 5 предложенных
библиотекарем?

78. Задача 20

• В турнире принимали участие 15
шахматистов, и каждые 2 шахматиста
встретились один раз. Сколько партий было
сыграно в турнире?

79. Задача 21

• Сколько можно составить из простых
делителей числа 2730 составных чисел,
которые содержат только три простых
делителя?

80. Задача 22

• В коробке лежит 12 синих и 8 красных
карандашей. Сколькими способами можно
выбрать 3 синих и 2 красных карандаша?

81. Задача 23

• Сколькими способами можно отправить 15
школьников в 3 спортивных лагеря, если в
один из них могут принять 8 школьников,
во второй — 3, а в третий — 4 школьника?

82. Решение задачи 23

83. Задача 24

• Сколькими способами можно разделить 10
билетов в кино, 4 билета в театр и 3 билета
в цирк среди 17 человек?

84. Решите задачи

• 25. Сколько четырехзначных чисел, кратных
10, можно составить из цифр 0,5,7,8, и 9?
• 26. Сколькими различными способами
можно назначить двух ребят на дежурство
в столовой, если в классе 24 учащихся?
• 27. Сколькими различными способами
могут распределиться призовые места
( первое, второе, третье ) между пятью
велогонщиками?

85. Решите задачи

• 28. Сколько различных четырехзначных
чисел можно составить с использованием
нечетных цифр, если цифры в числе не
повторяются?
• 29. Сколько различных трехзначных чисел,
кратных пяти, можно составить из нечетных
цифр, если цифры в числе не могут
повторятся?

86. Решите задачи

• 30. Секретный замок состоит из трех
барабанов, на каждом из которых
набирается одна из цифр от 0 до 9. Сколько
существует способов выбрать код этого
замка, если владелец использует только
нечетные цифры, которые могут
повторятся?
• 31. Сколько существует трехзначных чисел,
в записи которых нет цифры 3?

87. Ответы

• 25. 100
• 26. 276
• 27. 60
• 28. 120
• 29. 12
• 30. 125
• 31. 648