Презентация на тему элементы комбинаторики. Элементы комбинаторики. Решение комбинаторных зада

Петров Владимир,учащийся 12 группы ГБОУ СО НПО "Профессиональное училище №22" г. Саратова

В презентации рассмотрены премеры решения задач на нахождение перестановок, размещений, сочетаний.

Скачать:

Предварительный просмотр:

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Элементы комбинаторики: перестановки, сочетания и размещения Презентацию подготовил студент 12 группы ГБОУ СО НПО Петров Владимир.

Комбинаторика – раздел математики, который занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую. Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Термин "комбинаторика" был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.

Комбинаторные задачи делятся на несколько групп: Задачи на перестановки Задачи на размещение Задачи на сочетание

Задачи на перестановки Сколькими способами можно расставить 3 различные книги на книжной полке? Это задача на перестановки

Запись n ! читается так:«эн факториал» Факториал - это произведение всех натуральных чисел от 1 до n Например, 4! = 1*2*3*4 = 24 n! = 1 · 2 · 3 · ... · n.

n 1 2 3 4 5 6 7 8 9 10 n! 1 4 6 24 120 720 5040 40320 362880 3628800 Факториалы растут удивительно быстро:

Задача. Сколькими способами можно расставить 8 участниц финального забега на восьми беговых дорожках? P8 = 8!= 1 ∙2∙ 3 ∙4∙ 5 ∙6∙ 7 ∙8 = 40320

Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке. P n = 1 · 2 · 3 · ... · n. P n =n !

Задача. Квартет Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Сколькими способами можно рассадить четырех музыкантов? P = 4! = 1 * 2 * 3 * 4 = 24

Задачи на размещения

Задача: У нас имеется 5 книг, что у нас всего одна полка, и что на ней вмещается лишь 3 книги. Сколькими способами можно расставить на полке 3 книги? Выбираем одну из 5-ти книг и ставим на первое место на полке. Это мы можем сделать 5-ю способами. Теперь на полке осталось два места и у нас осталось 4 книги. Вторую книгу мы можем выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых. Таких пар может быть 5·4. Осталось 3 книги и одно место. Одну книгу из 3-ёх можно выбрать 3-мя способами и поставить рядом с одной из возможных 5·4 пар. Получится 5·4·3 разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 = 60. Это задача на размещения.

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

Задача. Учащиеся второго класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета? A 4 9 = = 6∙ 7∙ 8∙ 9 = 3024

Решите самостоятельно: В классе 27 учащихся. Нужно отправить одного учащегося за мелом, второго дежурить в столовую, а третьего вызвать к доске. Сколькими способами можно это сделать?

Задачи на сочетания: Задача. Сколькими способами можно расставить 3 тома на книжной полке, если выбирать их из имеющихся в наличии внешне неразличимых 5 книг? Книги внешне неразличимы. Но они различаются, и существенно! Эти книги разные по содержанию. Возникает ситуация, когда важен состав элементов выборки, но несущественен порядок их расположения. 123 124 125 134 135 145 234 235 245 345 ответ: 10 Это задача на сочетания

Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.

Задача. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде? C 7 2 = = 21

Решите самостоятельно: В классе 7 учащихся успешно занимаются по математике. Сколькими способами можно выбрать двоих из них, чтобы направить для участия в математической олимпиаде?

Особая примета комбинаторных задач – вопрос, который можно сформулировать так, чтобы он начинался словами «Сколькими способами…» или «Сколько вариантов…»

Перестановки Размещения Сочетания n элементов n клеток n элементов k клеток n элементов k клеток Порядок имеет значение Порядок имеет значение Порядок не имеет значения Составим таблицу:

Решите самостоятельно задачи: 1.В коробке находится 10 белых и 6 черных шаров. Сколькими способами из коробки можно вынуть один шар любого цвета? 2.Ольга помнит, что телефон подруги оканчивается тремя цифрами 5, 7, 8 но забыла, в каком порядке эти цифры расположены. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге. 3. В магазине “Филателия” продается 8 разных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?

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

Студента Группы ПР – 101(К) Савченко А.А Проверила Малыгина Г.С.

Комбинаторика! (Комбинаторный анализ) - раздел математики, изучающий дискретные объекты, множества (сочетания,перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики - алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике). Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».

Методы Комбинаторики Перестановкой из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n. Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел. Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Комбинаторные задачи Комбинаторика – от латинского слова combinare, что означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.

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

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

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

Правила суммы и произведения 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 различных двузначных чисел. 9 А D С В

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

«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения». 11 Сколькими способами могут быть расставлены 4 участниц финального забега на четырёх беговых дорожках? Рп = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов) 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 3 4 2 4 2 3 4 3 4 2 3 2 3 4 1 4 3 1 4 3 4 1 1 3 2 4 1 4 1 2 4 2 4 1 2 1 2 3 1 3 1 2 3 2 3 1 2 1 1 дорожка 2 доржка 3доржка 4 дор. Р е ш е н о п е р е б о р о м в а р и а н т о в

Пример Задачи Комбинаторики При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати? Решение: Каждый возможный исход соответствует функции (аргумент функции - это номер кости, значение - очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.

Разделы Комбинаторики!

Перечислительная комбинаторика Перечислительная комбинаторика (или исчисляющая комбинаторика) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например, перестановок) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п. Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правиламсложения и умножения. Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример - известная Задача о письмах.

Вероятностная комбинаторика! Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

Краткая историческая справка Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр (Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI-XVII вв.). Следующий этап развития теории вероятностей связан с именем Якоба Бернулли (1654-1705). Доказанная им теорема, получившая впоследствии название «Закона больших чисел», была первым теоретическим обоснованием накопленных ранее фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др. Новый, наиболее плодотворный период связан с именами П. Л. Чебышева (1821-1894) и его учеников А.А.Маркова(1856-1922) и А. М.Ляпунова (1857-1918). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математика м (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским

Описание презентации по отдельным слайдам:

1 слайд

Описание слайда:

Комбинаторика Подготовили учащиеся МБОУ СОШ № 7 г. Мичуринска Большакова Д. , Щербинина М. Учитель Духанина О.С.

2 слайд

Описание слайда:

Ход исследования: Что такое комбинаторика Что же послужило толчком для возникновения и развития комбинаторики Где в практической деятельности человека встречается комбинаторика Задачи Социологический опрос Вывод

3 слайд

Описание слайда:

4 слайд

Описание слайда:

Что такое Комбинаторика? Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Комбинаторика (от латинского combinare) означает “соединять, сочетать”.

5 слайд

Описание слайда:

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

6 слайд

Описание слайда:

Возникновение Комбинаторики С давних пор дипломаты, стремясь к тайне переписки, изобретали сложные шифры, а секретные службы других государств пытались эти шифры разгадать. Стали применять шифры, основанные на комбинаторных принципах. В 1970 – 1980 гг. комбинаторика добилась новых успехов. В частности, с помощью ЭВМ решена проблема четырёх красок: доказано, что любую карту можно раскрасить в четыре цвета так, что никакие две страны, имеющие общую границу, не будут окрашены в один и тот же цвет.

7 слайд

Описание слайда:

Сферы применения Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например: химику, изучающему строение органических молекул, имеющих данный атомный состав. ученому-агроному, планирующему распределение сельскохозяйственных культур на нескольких полях конструктору, разрабатывающему новую модель механизма

8 слайд

Описание слайда:

Задача №1 Государственные флаги многих стран состоят из горизонтальных или вертикальных полос разных цветов. Сколько существует различных флагов, состоящих из двух горизонтальных полос одинаковой ширины и разного цвета – белого, красного и синего? Решение: Пусть верхняя полоса флага – белая (Б). Тогда нижняя полоса может быть красной (К) или синей (С). Получили две комбинации – два варианта флага. Если верхняя полоса флага – красная, то нижняя может быть белой или синей. Получим ещё два варианта флага. Пусть, наконец, верхняя полоса – синяя, тогда нижняя может быть белой или красной. Это ещё два варианта флага. Всего получили 3 2 = 6 комбинаций – шесть вариантов флагов.

9 слайд

Описание слайда:

Задача №2 Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7? Используя в записи числа каждую из них не более одного раза. Решение: Чтобы ответить на этот вопрос, выпишем все такие числа. Пусть на первом месте стоит цифра 1. На втором месте может быть записана любая из цифр 3, 5, 7. Запишем, например, на втором месте цифру 3. Тогда в качестве третьей цифры можно взять 5 или 7. Получим два числа 135 и 137. Если на втором месте записать цифру 5, то в качестве третьей цифры можно взять цифру 3или 7. В этом случае получим числа 153 и 157. Если же, наконец, на втором месте записать цифру 7, то получим числа 173 и 175. Итак, мы составили все числа, которые начинаются с цифры 1. Таких чисел шесть: 135, 137, 153, 157, 173, 175. Аналогичным способом можно составить числа, которые начинаются с цифры 2,с цифры 5, с цифры 7. Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел: 135, 137, 153, 157, 173, 175, 315, 317, 351, 357, 371, 375, 513, 517, 531, 537, 571, 573, 713, 715, 731, 735, 751, 753, Таким образом, из цифр 1, 3, 5, 7 (без повторения цифр) можно составить 24 трехзначных числа.

10 слайд

Описание слайда:

Дерево возможных вариантов 1 5 7 3 1 3 3 7 5 7 1 5 7 1 3 7 1 3 5 7 5 3 5 7 1 7 1 5 3 7 1 7 1 3 3 1 5 1 5 3 Всего 24 варианта Всего 24 варианта

11 слайд

Описание слайда:

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

Слайд 2

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

Слайд 3

Вспомним несколько примеров таких задач

1.Несколько стран в качестве символа своего государства решили использовать флаг в виде 3-х горизонтальных полос одинаковых по ширине и цвету: синий, красный и белый. Сколько стран могут испытать такую символику при условии, что у каждой страны свой отличный от других флаг? Будем искать решение с помощью дерева возможных вариантов.

Слайд 4

Ответ: 6 комбинаций

Слайд 5

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

Составим таблицу: слева от 1 – го столбца поместим первые цифры искомых чисел, сверху – вторые цифры этих чисел (чётные цифры, тогда столбцов будет три).

Слайд 6

Так в столбце перечислены все возможные варианты, следовательно, их столько же, сколько клеток в столбце, т.е. 15.

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

Слайд 7

3.На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их может кофеем, соком или кефиром. Из скольких вариантов завтрака Вова может выбирать?

Решим задачу, перебирая всевозможные варианты, путем кодирования вариантов завтрака Решение: КП КБ КПр КК СП СБ СПр СК К-рП К-рБ К-рПр К-рК Ответ: 12 вариантов.

Слайд 8

Во всех задачах был осуществлён перебор всех возможных вариантов или комбинаций. Поэтому эти задачи называют комбинаторными. Слово комбинация происходит от латинского combino– соединяю. Действительно при получении любой комбинации мы составляем её из отдельных элементов последовательно соединяя их друг с другом. С этой точки зрения: число – это комбинация цифр, слово – это комбинация букв, меню – это комбинация блюд. Во всех предложенных задачах для подсчёта числа комбинаций мы использовали простой способ подсчёта – прямое перечисление (опираясь на «дерево возможных вариантов», таблицу, кодирование). Но способ перебора возможных вариантов далеко не всегда применим, ведь количество комбинаций может исчисляться миллионами. Здесь на помощь приходят несколько замечательных комбинаторных правил, которые позволяют подсчитать количество комбинаций без их прямого перечисления.

Слайд 9

Мы рассмотрели примеры 3-х разных задач, но получили совершенно одинаковые решения, которые основаны на общем правиле умножения: Пусть имеется n элементов и требуется выбрать из них один за другим к элементов. Если первый элемент m1выбрать n1 способами, после чего второй элемент m2выбрать n2 способами из оставшихся, затем третий элемент m3 выбрать n3 способами из оставшихся и т.д., то число способов могут быть выбраны все к элементов, равно произведению Примени это правило к каждой из решённых задач. 1-я задача: выбор верхней полосы - из 3-х цветов, т.е. n1=3; средняя полоса – из 2-х цветов, т.е.n2=2; нижняя полоса – из 1-го цвета, т.е. n3=1. n1 n2 n3 = 3 * 2 * 1 = 6 2-я задача: заметим, что в этой задаче задействованы два независимых исхода, поэтому mn = 5 *3 = 15

Слайд 10

Решение задач в классе: № 714, 716,718(а),721

№714. В кафе предлагают два первых блюда: борщ, рассольник - и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из первого и второго блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дере­во возможных вариантов.

Слайд 11

Решение. Что бы указать все обеды из двух блюд, будем рассуждать так. Выберем одно блюдо (борщ) и будем добавлять к нему поочерёдно разные вторые блюда, получая пары: Б г; б к; б с; б п (4 пары). Теперь в качестве первого блюда выберем рассольник и будем добавлять к нему поочерёдно разные вторые блюда: Рг; р к; р с; рп (4 пары). Согласно правилу комбинаторного умножения всего обедов: 2*4=8. Построив дерево возможностей, получим 8 вариантов. Ответ: б г; б к; б с; б п; р г; р к; р с; р п.; получим восемь разных обедов из двух блюд.

Слайд 12

№ 716 Стадион имеет четыре входа: А, В, С и D. Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов?

Слайд 13

Решение. Из условия ясно, что порядок выбора имеет значение: АВ означает, что посетитель вошёл через А и вышел через В, а ВА означает, что вошёл через В, а вышел через А. Чтобы перечислить все варианты выбора двух входов, будем придерживаться следующего правила. Выпишем обозначения всех входов в ряд: А, В, С, Д. Берём первый вход и дописываем к нему поочерёдно каждый из остальных входов, получаем 3 пары: А В, А С, А Д. Берём второй вход и дописываем к нему поочерёдно каждый из остальных входов, кроме него самого начиная с начала ряда, т. е. с первого входа: ВА, ВС, ВД. Выбирая третий, а затем четвёртый вход, получаем СА, СВ, СД; ДА, ДВ, ДС. Общее количество способов выбора: 4*3=12 (к каждому из 4 входов мы дописывали 3 других). Замечание. Подсчитать количество способов выбора, не составляя пары, можно по правилу произведения: первый выбор (через какой вход войти) можно сделать 4 способами (А, или В, или С, или Д); после этого второй выбор (через какой вход войти) можно сделать 3 способами (любой вход, кроме того, через который вошли). Общее количество выбора равно 4*3=12. Ответ: 12 способов.