Презентация "Комбинаторные задачи. Комбинаторика"

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

выбор

расположение

перестановки

n!

n!

граф-это геометрическая фигура, состоящая из точек (вершины графа) и линий, их соединяющих (рёбра графа). Способы решения комбинаторных задач:

• Таблица вариантов
• Дерево вариантов
• Правило умножения

1. Дерево вариантов.

Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр.

1

159

195

5

9

519

591

915

951

2 комбинации

2 комбинации

2 комбинации

Всего 2•3=6 комбинаций.

Сколько четных двузначных чисел можно составить из цифр 0,1,2,4,5,9? Ответ:15 чисел.

1

2

4

5

9

0

2

4

10

14

12

20

22

24

40

42

44

50

52

54

90

92

94

Таблица вариантов

На завтрак можно выбрать булочку, кекс, пряники или печенье, запить можно чаем, соком или кефиром. Сколько вариантов завтрака есть?

х/б

изд.

напитки

булочка

кекс

пряники

печенье

чай

сок

кефир

чай

чай

чай

чай

кефир

сок

сок

сок

сок

кефир

кефир

кефир

булочка

булочка

булочка

кекс

кекс

кекс

пряники

пряники

пряники

печенье

печенье

печенье

Выбор напитка- испытание А

Выбор хл./бул. изделия.- испытание В

Испытание А имеет 3 варианта (исхода), а испытание В-4, всего вариантов

независимых испытаний А и В 3•4=12.

Для того, чтобы найти число

всех возможных исходов

(вариантов) независимого

проведения двух испытаний

А и В, надо перемножить число

всех исходов испытания А на

число всех исходов испытания В

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

В коридоре висят три лампочки. Сколько имеется различных способов освещения коридора?

Первый способ - перебор вариантов

Ответ: 8

Второй способ - дерево вариантов

Первая лампочка

Вторая лампочка

Вторая лампочка

Третья

лампочка

Третья

лампочка

Третья

лампочка

Третья

лампочка

+

+

+

+ + --

+

+

+

---

---

---

---

---

---

---

+

+

+

+ -- +

+ -- --

+

-- + +

-- + --

-- -- +

-- -- --

Ответ: 8

Третий способ - правило умножения

Для каждой лампочки возможны два исхода (гореть или не гореть), а лампочек три, значит

2×2×2=8

Ответ:8.

Расписание уроков.

В 9 классе в среду 6 уроков: геометрия, литература, русский язык, английский язык, биология и физкультура. Сколько вариантов расписания можно составить?

Расставляем предметы по порядку

Предмет	Число вариантов

Геометрия

6

Литература

5

Русский язык

4

Английский язык

3

Биология

2

1

Физкультура

Всего вариантов расписания

1•2•3•4•5•6=

720

Дяде Федору для приема гостей мама и папа подарили 5 разных чашек. Сколькими способами можно разделить чашки между гостями? В гости к Дяде Федору пришли папа, мама, кот Матроскин и почтальон Печкин.

У первого гостя (например, у Мамы) есть 5 вариантов выбора чашки.

У следующего (например, у папы) остается 4 варианта выбора.

Следующий (пусть это - почтальон Печкин) будет выбирать уже из 3 чашек.

Далее, (кот Матроскин) будет выбирать уже из 2 чашек.

Последний же (Дядя Федор) получает одну чашку.

Получили, что каждому выбору чашки мамой соответствует 4 возможных выбора папы, т.е. всего 5 • 4 способов. После того, как папа выбрал чашку, у Печкина есть 3 варианта выбора, у Матроскина – 2, у Дяди Федора – 1, т.е. всего

5 • 4 • 3 • 2 • 1 способов

Заметим, что 5 • 4 • 3 • 2 • 1 – это произведение всех натуральных чисел от 1 до 5. такие произведения записывают короче

5 • 4 • 3 • 2 • 1 = 5!

(читают «пять факториал»)

Семейный ужин.

Пример

В семье 6 человек, а за столом в кухне 6 стульев. Было решено каждый вечер перед ужином рассаживаться на эти 6 стульев по-новому. Сколько дней члены семьи смогут делать

это без повторений?

№1

№2

№3

№4

№5

№6

6

5

4

3

2

1

6•5•4•3•2•1=

720дн.

-почти 2 года

3. « Эн факториал»-n!.

1•2•3•4•5•6=720

Определение.

Произведение подряд идущих первых n

натуральных чисел обозначают n! и называют

«эн факториал»: n!=1•2•3•…•(n-1)•n.

2!=

1•2=

2

3!=

1•2•3=

6

4!=

1•2•3•4=

24

5!=

1•2•3•4•5=

6!=

120

1•2•3•4•5•6=

720

7!=

1•2•3•4•5•6•7=

5040

n!=(n-1)!•n

Удобная формула!!!

Закончите предложение и ответьте на вопрос

• Чему…?
• Где…?
• Зачем…?
• Как…?

• Спасибо за урок!