🗊Презентация Комбинаторика. Общие правила комбинаторики

Комбинаторика Захарова В.Ф. Zakharova.vf@gmail.com

Комбинаторика Общие правила комбинаторики Перестановки Размещения Сочетания. Свойства сочетаний

Комбинаторика Combinare (лат.) – сочетать, соединять

Основные правила комбинаторики Перебор возможных вариантов Пример: Из группы теннисистов, в которую входят пять человек - Антон, Борис, Виктор, Глеб и Дмитрий, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? Дерево (граф) возможных вариантов Пример: Сколько трехзначных чисел можно составить из цифр 1, 3, 5 и 7, используя в записи числа каждую из них не более одного раза?

Основные правила комбинаторики Комбинаторное правило умножения Пример: В меню столовой возможные первые блюда: борщ, щи, рассольник. На второе: гуляш, жаркое, голубцы, плов. Из напитков: чай, кофе, компот. Сколько различных обедов может заказать посетитель? В общем виде Пусть имеется n элементов (n1 возможных первых, n2 возможных вторых и т. д.) и требуется выбрать из них один за другим k элементов. Число способов , которыми могут быть выбраны все k элементов, равно произведению  n1 ∙ n2 ∙ n3 ∙ … ∙ nк.

Примеры Из города А в город В ведут 5 дорог, а из города В в город С — 3 дороги. Сколько путей, проходящих через В, ведут из А в С? Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма? Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»? А из слова «здание»? Бросают игральную кость с 6 гранями и запускают волчок, имеющий 8 граней. Сколькими различными способами могут они упасть? На вершину горы ведут 5 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз? Сколькими способами можно указать на шахматной доске два квадрата — белый и черный? А если нет ограничений на цвет выбранных квадратов? Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?

Факториал Произведение первых подряд идущих n натуральных чисел обозначают n! n! = 1 ∙2 ∙3 ∙… ∙ (n -2)∙ (n – 1)∙ n 1! = 1 2! = 1∙2 = 2 3! = 1∙2∙3 = 6 4! = 1∙2∙3∙4 = 24 5! = 1∙2∙3∙4∙5 = 120 6! = 5! ∙ 6 = 120 ∙ 6 = 720 7! = 6! ∙ 7 = 720 ∙7 = 5040

Факториал Полезные упражнения:

Перестановки  Опр. Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке  Рn = n∙(n -1)∙(n – 2 )∙ …∙3∙2∙1=n! Рn = n! – формула количества всевозможных перестановок из n элементов

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

Размещения Опр. Размещением из n элементов по k (k ≤n) называется любое множество, состоящее из k элементов, взятых в определенном порядке из данных  n элементов. Аnk = 

Размещения Пример 1. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета Решение: А84 = 5 ∙ 6 ∙ 7 ∙ 8 = 1680 Пример 2. Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5? Решение: А63 - А52 =  4 ∙ 5 ∙ 6 - 4 ∙ 5 = 120-20=100. Пример 3. Сколько существует трехзначных чисел (без повторения цифр в записи числа)? Решение: А103 - А92 =  8 ∙9 ∙10 - 8 ∙9 = 720-72=648.

Размещения В организацию избрано 9 человек. Из них надо избрать председателя, его заместителя и секретаря. Сколькими способами это можно сделать? Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского, на любой  другой из этих пяти языков? Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? Та же задача, если одна из полос должна быть красной? Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1,3,5,7,9? б) 0,2,4,6,8? Какова сумма всех таких пятизначных чисел в каждом из пунктов?

Сочетания Задача: Сколькими способами можно выбрать из 5 человек 3 дежурных?

Сочетания

Сочетания Встретились 6 друзей и каждый пожал руку каждому своему другу. Сколько было рукопожатий? В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно? Сколько диагоналей можно провести в выпуклом 7-угольнике? n-ке? В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала? Из вазы с фруктами, где лежат 9 яблок и 6 груш, нужно выбрать 3 яблока и 2 груши. Сколькими способами можно это сделать? Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если: а)заведующий лабораторией должен ехать в командировку; б)заведующий лабораторией должен остаться? На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений. Сколькими способами читатель может выбрать 3 книги, если: а) словарь нужен ему обязательно; б) словарь ему не нужен? 

Сочетания У мамы 2 яблока и 3 груши. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано? У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано? Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз? Во скольких случаях ровно один туз? Во скольких случаях не менее двух тузов? Ровно два туза?

Свойства сочетаний

Треугольник паскаля. Бином Ньютона

Свойства сочетаний

Использованная литература Макарычев Ю. Н. Алгебра : элементы статистики и теории вероятностей : учеб. пособие для учащихся 7—9 кл. общеобразоват. учреждений / Ю. Н. Макарычев, Н. Г. Миндюк; под ред. С. А. Теляковского. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. - М.: ФИМА, МЦНМО, 2006. - 400 с.