Решение комбинаторных задач

Решение комбинаторных задач

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

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

Методы решения комбинаторных задач

1. Метод перебора вариантов

2. Дерево возможных вариантов

3. Табличный метод

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

Метод перебора вариантов

Полный перебор вариантов без составления таблиц и схем

Пример:

Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?

Решение:

Перебираем всевозможные варианты: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

Задача 1.

В финальном забеге на 100 м участвуют Смирнов, Петров и Орлов. Назовите возможные варианты распределения призовых мест.

Ответ:

Задача 1: Вариант1: 1) Смирнов, 2) Петров, 3) Орлов. Вариант2: 1) Смирнов, 2) Орлов, 3) Петров. Вариант3: 1) Орлов, 2) Смирнов, 3) Петров. Вариант4: 1) Орлов, 2) Петров, 3) Смирнов. Вариант5: 1) Петров, 2) Орлов, 3) Смирнов. Вариант6: 1) Петров, 2) Смирнов, 3) Орлов .

Дерево возможных вариантов

способ решения разнообразных задач, касающихся перебора вариантов происходящих событий.

Пример:

Какие трехзначные числа можно составить из цифр 0, 3, 8?

Решение:

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

???

3

8

8

3

0

3

8

0

8

0

3

3

3

0

8

3

0

8

0

8

3

0

8

3

0

8

Задача 2.

Сколько существует флагов составленных из трех горизонтальных полос одинаковой ширины и различных цветов: белого, синего, красного и зеленого? Есть ли среди них Государственный флаг Российской Федерации?

Ответ:

Задача 2: всего существует 24 флага, среди них есть Государственный флаг Российской Федерации.

Задача 3.

Запишите все возможные варианты расписания пяти уроков на день из предметов: математика, русский язык, история, английский язык, физкультура, причем математика должна быть вторым уроком.

Ответ:

Задача 3: обозначив М - математика, Р - русский язык, И - история, А - английский язык, Ф - физкультура и построив дерево возможных вариантов, получим всего 24 варианта .

Табличный метод

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

Задача 1. Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец - первые цифры искомых чисел, вверху первая строка - вторые цифры.

Первая цифра может быть любая, а вторая только нечетная (1, 3, 7, 9)

1

1

3

3

11

7

31

13

4

17

41

33

6

9

61

37

43

19

7

47

39

8

63

71

67

81

9

49

73

77

83

69

91

87

79

93

89

97

99

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

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

Пример:

Сколько трехзначных чисел можно составить из цифр: 1, 2, 5, 8 используя в записи числа каждую из них не более одного раза?

Решение:

Первую цифру выбираем четырьмя способами (1, 2, 5, 8), вторую цифру можно выбрать тремя способами, и на выбор третьей цифры остается два способа. Количество искомых трехзначных чисел равно произведению 4 · 3 · 2 = 24.

Задача 4.

Сколькими способами можно составить список из шести учеников 10 класса сдающих зачет по математике?

Решение: первого в списке ученика можно выбрать 6 способами,

второго – 5 способами,

третьего – 4 способами,

четвертого – 3 способами,

пятого – 2 способами,

шестого – 1 способом (оставшийся ученик).

Перемножив полученные результаты получим 6 · 5 · 4 · 3 · 2 · 1 = 720

Ответ: 720 способов.