Презентация к урокам по теме: Элементы комбинаторики

Элементы комбинаторики9 -11 классы, МБОУ Кочневская СОШ учитель Грязнова А.К1 Основные вопросы:2Что такое комбинаторика? Какие задачи считают комбинаторными?ПерестановкиРазмещения Сочетания


3Не будем спорить - будем вычислять. Г. Л е й б н и цКомбинаторика – радел математики, в котором рассматриваются задачи о подсчёте числа комбинаций составленных по определённым правилам. 4II. Какие задачи считают комбинаторными?Комбинаторные задачиЗадачи подсчёта числа комбинаций из конечного числа элементовКомбинаторика – от латинского слова combinare, что означает «соединять, сочетать».Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.


5I. Уровни решения комбинаторных задач1. Начальный уровень. Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами- отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки; - такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга. Иногда удаётся доказать, что данная задача не имеет решения (например, нельзя расположить 10 шаров в 9 урнах так, чтобы в каждой урне было не более одного шара – хотя бы в одной урне окажется не менее двух шаров).




62. Второй уровень. Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи.3. Третий уровень. Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи.Например: Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А.


7ПутьДлина путиПутьДлина путиABCDA1555ACDBA1300ABDCA1300ADBCA1450ACBDA1450ADCBA1550СВА300200400500400350DНа рис. изображена схема путей, связывающих эти города. Различные варианты путешествий отличаются друг от друга порядком посещения городов В, С, и .D. Существует шесть вариантов путешествия. В таблице указаны варианты и длин каждого пути:@ Gryznova A.K.

8Комбинаторные задачи на оптимизацию приходится решать мастеру, стремящемуся к быстрейшему выполнению задания, агроному, стремящемуся к наивысшей урожайности на данных полях, и т.д. 9Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи. Этот раздел комбинаторики, называемый теорией перечислений, тесно связан с теорией вероятностей. 10Правила суммы и произведения1. Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два? AB, AC, AD, BC, BD, CD – всего 6 коктейлей2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ?Первой цифрой двузначного числа может одна из цифр 1, 2, 3 (цифра 0 не может быть первой). Если первая цифра выбрана, то вторая может быть любая из цифр 0, 1, 2, 3. Т.к. каждой выбранной первой соответствует четыре способа выбора второй, то всего имеется 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел.АDСВ



112. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ? 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел.Первая цифра вторая цифра123012301230123














Правило произведения:Если элемент А можно выбрать из множества элементов п способами и для каждого такого выбора элемент В можно выбрать т способами, то два элемента (пару) А и В можно выбрать п·т способами.12@ Gryznova A.K. 13«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения».Сколькими способами могут быть расставлены 4 участниц финального забега на четырёх беговых дорожках?Рп = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов) 1 2 3 42 3 4 1 3 4 1 2 4 1 2 33 4 2 4 2 34 3 4 2 3 23 4 1 4 3 14 3 4 1 1 32 4 1 4 1 24 2 4 1 2 12 3 1 3 1 23 2 3 1 2 11 дорожка 2 доржка3доржка4 дор.Р е ш е н о п е р е б о р о м в а р и а н т о в







14II. Перестановки (1)К в а р т е т Проказница Мартышка, Осёл, Козёл Да косолапый Мишка Затеяли сыграть Квартет.……………………………………………………. Ударили в смычки, дерут, а толку нет. «Стой, братцы, стой! - кричит Мартышка. – Погодите! Как музыке идти? Ведь вы не так сидите»4·3·2·1 = 4! способов 15II. Перестановки (2)Перестановкой из п - элементов называется комбинации, отличающиеся друг от друга лишь порядком следования элементовРп- число перестановок (Р первая буква французского слова permutation- перестановка) Рп= n·(n-1)·(n-2)·(n-3)·(n-4)·. . .·3 ·2 ·1= n!Рп = n!В математике принято считать 0! =1 и 1! = 1


16Размещения (1)Четыре попутчик решили обменяться визитными карточками. Сколько всего карточек при этом было использовано? получилось 12 карточек. Каждый из четырёх попутчиков вручил визитку каждому из трёх попутчиков 4 · 3 = 121342Комбинации, составленные из k элементов, взятых из n элементов, и отличающиеся друг от друга либо составом, либо порядком расположения элементов, называются размещениями из n элементов по k (0< k ≤n ). - размещение из n элементов по k элементов. А первая буква французского слова arrangement : «размещение», «приведение в порядок»












17Размещения (2) Пуст имеется 4 шара и 3 пустых ячейки. Обозначим шары буквами a, b, c, d. В пустые ячейки можно по разному разместить три шара из этого набора.Выбирая по-разному первый, второй и третий шары, будем получать различные упорядоченные тройки шаровКаждая упорядоченная тройка, которую можно составить из четырёх элементов называется размещением из четырёх элементов по триdbcbacacbabc




18Размещения (3)Сколько же размещений можно составить из 4-х элементов (abcd) по три? abc abd acb acd adb adc bac bad bca bcd bda bdc cab cad cba cbd cda cdb dab dac dba dbc dca dcbР е ш е н о п е р е б о р о м в а р и а н т о в




19Размещения (4)Можно решить и не выписывая самих размещений:первый элемент можно выбрать четырьмя способами, так им может быть любой элемент из четырёх;для каждого первого второй можно выбрать тремя способами;для каждых первых двух можно двумя способами выбрать третий элемент из двух оставшихся.Получаем= 4·3·2 = 24Решено с использованием п р а в и л а у м н о ж е ни я




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


21Р е ш и з а д а ч и:1. На плоскости отмечено 5 точек. Сколько получится отрезков, если соединить точки попарно? 2. На окружности отмечено п точек. Сколько существует треугольников с вершинами в этих точках?


Источники информации22В.Ф.Бутузов, Ю.М.Колягин, Г.Л. Луканкин, Э.Г.Позняк и др. «Математика» учебное пособие для 11кл общеобразовательных учреждений /рекомендовано Министерством образования РФ/ М., Просвещение, 1996.Е.А. Бунимович, В.А. Булычёв: «Вероятность и статистика», пособие для общеобразовательных учебных заведений 5 – 9 классы / допущено Министерством образования Российской Федерации // Дрофа Москва 2002Ю.Н. Макарычев, Н.Г.Миндюк «Алгебра: элементы статистики и теории вероятностей 7 – 9 классы» Под редакцией С.А.Теляковского М: Просвещение , 2006 гТреугольнички http://works.doklad.ru/images/_E3ZV-_wFwU/md87b96f.gif Остальные рисунки созданы Грязновой А.К.