Элементы комбинаторики

1.

Элементы
комбинаторики

2.

Что такое «комбинаторика»?
• Комбинаторика – это раздел математики,
посвященный задачам выбора и
расположения элементов некоторого (обычно
конечного) множества в соответствии с
заданными правилами.
• Комбинаторные задачи – это задачи на
перебор всех возможных вариантов.

3.

Примеры комбинаторных
задач
ПРИМЕР 1. В кафе предлагают два первых блюда: борщ, рассольник
– и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени.
Укажите все обеды, которые может заказать посетитель.
Решение.
Введем обозначения: Б – борщ, Р – рассольник;
Г – гуляш, К – котлеты, С – сосиски, П – пельмени.
Составим все возможные пары из первого и второго блюд:
БГ
РГ
1-ый способ –
БК
РК
БС
РС
перебор всех
БП
РП
вариантов.
ИТОГО: 8 обедов.

4.

Примеры комбинаторных
задач
ПРИМЕР 1. В кафе предлагают два первых блюда: борщ, рассольник
– и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени.
Постройте дерево возможных вариантов обеда.
Обед
Первое блюдо
Б
Р
Второе блюдо
Г К С П
Г К С П
2-ой способ –
графическийпостроение
дерева
вариантов .

5.

Комбинаторные правила
Вернемся к примеру 1.
ПРИМЕР 1. В кафе предлагают два первых блюда: борщ, рассольник
– и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени.
Сколько различных обедов может заказать посетитель?
Решение.
С каждым первым блюдом может сочетаться
4 вторых блюда. Так как первых блюд 2, то
чтобы посчитать число всех возможных
комбинаций, надо 2 умножить на 4 :
2 · 4 = 8 (обедов)
3-ий способ –
использование
правил
и формул.
Правило умножения. Если имеется m способов выбрать элемент a
и n способов выбрать элемент b , то пару (a,b) можно выбрать
m · n способами.

6.

Примеры комбинаторных
задач
ПРИМЕР 2. Запишите все трехзначные числа, в записи которых
используются цифры 1, 2 и 3 без повторения.
Решение.
123
132
213
231
312
321
1
Цифры:
2-я
2
3
3-я
3
2
2
1
3
3
1
3
1
2
2
1
1-я
1-ый способ.
ВСЕГО: 6 чисел
Дерево возможных
вариантов
2-ой способ.

7.

Комбинаторные правила
С помощью правила умножения решим
ПРИМЕР 2. Сколько существует трехзначных чисел, в записи которых
используются цифры 1, 2 и 3 без повторения?
Решение.
Первой цифрой может быть любая из 3-х цифр, второй
цифрой – любая из 2-х оставшихся цифр, третьей цифрой –
одна цифра.
По правилу умножения количество чисел, в записи которых
используются цифры 1, 2 и 3 без повторения, равно:
3·2·1=6
3-ий способ.

8.

Примеры комбинаторных
задач
ПРИМЕР 3. Какие двузначные числа можно записать, используя
цифры 1, 2 и 3 ?
Решение.
11
12
13
21
22
23
ВСЕГО: 9 чисел
31
32
33
1-ый способ.

9.

Комбинаторные правила
С помощью правила умножения решим
ПРИМЕР 3. Сколько двузначных чисел можно записать, используя
цифры 1, 2 и 3 ?
3-ий способ.
Решение.
Имеем 3 способа выбрать 1-ую цифру числа и 3 способа
выбрать 2-ую цифру числа. По правилу умножения всего
можно записать:
3 · 3 = 9 (чисел)

10.

Комбинаторные правила
Правило умножения можно обобщить для большего числа
элементов.
Правило умножения (в общем виде). Если имеется m способов
выбрать элемент a , n способов выбрать элемент b , … , k способов
выбрать элемент t , то набор (a, b, …, t) можно выбрать
m · n · … · k способами.

11.

Комбинаторные правила
ПРИМЕР 4. В классе 12 мальчиков и 15 девочек. Сколькими
способами можно выбрать одного человека из класса на
общешкольную конференцию?
Решение.
12 + 15 = 27 (способов)
Правило сложения. Если имеется m способов выбрать элемент a
и (независимо от них) n способов выбрать элемент b , то выбрать
один элемент – или a, или b - можно m + n способами.
Аналогичное правило применяется и для большего числа
элементов.

12.

Комбинаторные правила
(обобщение)
И a, и в
Или a, или в
Правило
умножения
Правило
сложения
Если имеется m способов
выбрать элемент a и n
способов выбрать элемент b ,
то выбор a и b можно сделать
m · n способами.
Если имеется m способов
выбрать элемент a и n способов
выбрать элемент b , то выбор
a или b можно сделать
m + n способами.

13.

Решаем на уроке
№ 715 с. 185
№ 716
Домашняя работа:№ 717