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

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

Расчет количества вариантов: формулы перемножения и сложения количества вариантов. Количество текстов данной длины в данном алфавите.

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

Историческая справка С комбинаторными задачами люди столкнулись в глубокой древности. В Древнем Китае увлекались составлением магических квадратов. В Древней Греции изучали фигуры, которые можно составить из частей квадрата. Комбинаторика становится наукой в семнадцатом веке. Изучением комбинаторных задач занимались французские математики Б. Паскаль и П.Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц. Замечательные достижения в области комбинаторики принадлежат Л.Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей.

Правило суммы Если пересечение конечных множеств А и В пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В :

Задача №1. На одной полке книжного шкафа стоит 30 различных книг, а на другой – 40 различных книг (не такие как на первой). Сколькими способами можно выбрать одну книгу.

Правило умножения. Если множества А и В конечны, то число N возможных пар (а; в), где а из А, в из В равно произведению чисел элементов этих множеств: N = n (A) *n (B)

Задача № 2 Пусть существует 3 кандидата на пост командира и 2 на пост инженера. Сколькими способами можно сформировать экипаж корабля, состоящий из командира и инженера?

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

Такую схему называют деревом возможных вариантов.

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

Следовательно, общее число искомых трехзначных чисел равно произведению 4·3·2, т.е. 24. Следовательно, общее число искомых трехзначных чисел равно произведению 4·3·2, т.е. 24. Отвечая на поставленный вопрос в задаче , мы использовали, так называемое комбинаторное правило умножения.

Комбинаторное правило умножения Если первый элемент можно выбрать n1 способами, после чего второй элемент можно выбрать из оставшихся элементов n2 способами, затем третий элемент – n3 способами и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению n1· n2· n3· …nk.

Домашнее задание 1 вариант. 1. Сколько можно составить четырехзначных чисел из цифр 1, 5, 8, 3, если: а) цифры в числе не повторяются; б) цифры могут повторяться. 2. В среду в 5 «Б» классе 5 уроков: русский, информатика, естествознание, ИЗО, иностранный. Сколько можно составить вариантов расписания на день? Сколько можно составить вариантов расписания на день, зная, что информатика –первый урок?

Задача 1. Сколькими способами могут быть расставлены 8 участниц финального забега на 8 беговых дорожках?

Решение. Существует Р8 всевозможных перестановок из 8 элементов, т.е. Р8 = 8! = 8·7·6·5·4·3·2·1= 40 320 (способов) Ответ: 40 320 способов.

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

Решение: Составим сначала все пары, которые входит Антонов. Получим 3 пары: АГ,АС,АФ. Выпишем пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС,ГФ. Составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев. Такая пара только одна: СФ. Других вариантов составления пар нет, так как все пары, в которые входит Федоров уже составлены. Итак, мы получили 6 пар: АГ,АС,АФ, ГС,ГФ, СФ.

Итак, мы получили 6 пар: АГ,АС,АФ, ГС,ГФ, СФ. Значит, всего существует 6 вариантов выбора тренером пары теннисистов из данной группы. Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов.

Пример 3. Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги.

Решение. Путь из А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеются 2· 3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2· 3· 2, т.е. 12, способов выбора туристами маршрута из города А к пристани.