Цикл уроков по теме "Введение в комбинаторику"

Урок 1. Введение в комбинаторику

Цели: дать понятие «Комбинаторика», «Комбинаторные задачи»; познакомить учащихся с историей данной науки; привести примеры нескольких комбинаторных задач с решениями для привития интереса учащихся к данной науке, ВВЕСТИ ПОНЯТИЕ ФАКТОРИАЛА, НАУЧИТЬСЯ ПРИМЕНЯТЬ .

Ход урока

Сообщение темы и целей

Работа по теме

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

С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы.

Принято считать, что комбинаторика возникла в XVI веке, когда в жизни привилегированных слоев общества большое распространение получили азартные игры и всевозможные лотереи. К азартным играм относили карты и кости (бросание шестигранных игральных кубиков).

Слово «азар» по-арабски означает «трудный». Арабы называли азартной игрой комбинацию очков, которая при бросании нескольких костей могла появиться лишь единственным образом. Например, при бросании двух костей трудным («азар») считалось появление в сумме двух или двенадцати очков. Первоначально комбинаторные задачи касались в основном азартных игр. Решались вопросы, сколькими способами можно получить некоторый набор карт в карточной игре, как часто выпадает выигрыш в той или иной лотерее. Эти и другие проблемы азартных игр и явились движущей силой в развитии комбинаторики.

Одним из первых занимался подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья (1500-1557).

В XVII веке изучением теоретических вопросов комбинаторики занимались французские ученые Б. Паскаль (1623-1662) и П. Ферма (1601-1665). Исходным пунктом их исследований тоже были проблемы азартных игр.

Дальнейшее развитие комбинаторики связано с именами Я. Бернулли (1654-705), Г. Лейбница (1646-1716) и Л. Эйлера (1707-1783). Однако и в работах этих математиков в основном рассматривались приложения к различным играм (лото, пасьянсы и т.д.). В дальнейшем комбинаторные методы играли значительную роль в развитии алгебры и геометрии.

В последние десятилетия комбинаторика активно развивается, она тесно связана с проблемами дискретной математики, линейного программирования, статистики. Ее методы широко используются при решении транспортных задач, для планирования производства и реализации продукции, для составления и декодирования шифров. Комбинаторику можно рассматривать как введение в теорию вероятностей, она помогает при решении задач этой теории осуществить подсчет числа возможных исходов и числа благоприятных исходов опыта или эксперимента в различных случаях.

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

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

При решении подобных задач мы каким-либо образом выбираем m элементов из общего числа n элементов некоторого множества E, при этом в постановке задачи четко оговариваем, каким способом составляется выборка.

• Сначала мы рассмотрим два общих правила, с помощью которых решаются задачи комбинаторики – правило суммы и правило произведения.

С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы.

Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять планы и опровергать планы противника.

Со временем появились различные игры (нарды, карты, шашки, шахматы и т.д.). В каждой из этих игр приходилось рассматривать различные сочетания фигур, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации и умел избегать проигрышных.

Не только азартные игры давали пищу для комбинаторных размышлений математиков. Еще с давних пор дипломаты, стремясь к тайне переписки, изобретали сложные шифры, а секретные службы других государств пытались эти шифры разгадать. Стали применять шифры, основанные на комбинаторных принципах, например, на различных перестановках букв, заменах букв с использованием ключевых слов и т.д.

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

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

Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма.

Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер.

Решение

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

Задача №1.

Сколько существует вариантов покупки одной розы, если продают

3 алые, 2 белые и 4 желтые розы?

Это важно

9

способов

Важно помнить, что выбирается не просто красная, белая или желтая роза, а одна конкретная роза: эта красная или эта белая, или эта желтая роза.

Правило суммы

Вернуться к решению задачи №3

Правило суммы

Если некоторый элемент А можно выбрать n способами, а элемент В – m способами, то выбор «либо А, либо В» можно сделать n + m способами.

A – n способов

В – m способов

А или В – (n + m)способов

Задача №2.

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

2

Первое блюдо:

3

Второе блюдо:

3 + 3 =

2 ∙ 3 = 6 способов

Правило произведения

Вернуться к решению задачи №3

Правило произведения

Если некоторый элемент А можно выбрать n способами, а элемент В – m способами, то пару А и В можно выбрать n ∙ m способами.

A – n способов

В – m способов

А и В – (n ∙ m)способов

Задача №3.

На блюде лежат 8 яблок, 3 груши и 4 апельсина.

а) Сколькими способами можно взять один плод?

Правило суммы

8 + 3 + 4 = 15 способов

Выбирается 1 плод.

б) Сколькими способами можно взять:

• яблоко с грушей

• яблоко с апельсином

• грушу с апельсином

• яблоко, грушу и апельсин

8 · 3 = 24 способа

Выбирается 2 или 3 плода.

8 · 4 = 32 способа

Правило произведения

3 · 4 = 12 способов

8 · 3 · 4 = 96 способов

Задача №3.

На блюде лежат 8 яблок, 3 груши и 4 апельсина.

в) Сколькими способами можно взять два фрукта

с разными названиями?

Применяются оба правила.

Правило суммы

Правило произведения

Пара рассматривается

как единое целое.

Выбирается пара.

8 · 3 + 8 · 4 + 3 · 4 = 24 + 32 +12 = 68 способов

Задача №4.

Проверка(5)

Самостоятельная работа.

В пакетике драже лежат 9 красных, 10 синих

и 12 зеленых конфет.

а) Сколькими способами можно взять 1 конфету?

а) 9 + 10+ 12 = 31способ

б) Сколькими способами можно взять:

• красную и синюю конфеты

• красную и зеленую конфеты

б) 9 · 10 = 90 способов

• синюю и зеленую конфеты

9 · 12 = 108 способов

10· 12 = 120 способов

в) 9 · 10 + 9 · 12 + 10 · 12 = 318 способов

в) Сколькими способами можно взять две конфеты разного цвета?

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

1 способ (перебор)

4

1

7

11

71

41

74

44

14

77

17

47

Ответ: 9 чисел

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

2 способ (построение дерева различных вариантов)

4

1

7

1 цифра

7

1

4

7

1

1

4

7

4

2 цифра

74

11

14

47

71

77

17

41

44

Ответ: 9 чисел

Задача №5.

Сколько различных двузначных чисел можно составить, используя цифры 1,4, и 7, если цифры могут повторяться.

3 способ (использование формулы)

двузначное число

2цифра числа

(три выбора)

1 цифра числа

(три выбора)

3 · 3 = 9 чисел

Ответ: 9 чисел

Задача №6.

Проверка (3)

Самостоятельная работа.

Сколько различных трехзначных чисел можно составить используя цифры

3 и 5, если цифры могут повторяться? (задачу решить 3 способами)

3 способ

(формула)

1 способ

(перебор)

2 способ

(дерево различных вариантов)

3

333

5

555

2 · 2 · 2 = 8 чисел

553

335

5

3

3

5

355

533

353

535

3

5

3

5

5

3

5

3

Ответ: 8 чисел

Задача №7.

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

0, 1, 2, 3, если цифры могут повторяться .

двузначное число

2 цифра числа (четыре выбора : 0,1,2,3)

1 цифра числа

(три выбора: 1,2,3)

3 · 4 = 12 чисел

Ответ: 12 чисел

Задача №8.

Сколько различных трехзначных чисел можно составить, используя цифры

4, 5, 6?

трехзначное число

2 цифра числа

(два выбора)

3 цифра числа

(один выбор)

1 цифра числа

(три выбора: 4,5,6)

Определение

3 · 2 · 1= 6 чисел

3 · 2 · 1= 3! = 6 чисел

Произведение всех натуральных чисел от 1 до n включительно называется n – факториал и обозначается символом n!

n! = 1 · 2 · 3 · … · n = n!

0! = 1

Ответ: 6 чисел