Комбинаторика

Слайд 1

Слайд 2

Оглавление Комбинаторика Методы Комбинаторики Комбинаторные задачи Уровни решения комбинаторных задач Правила суммы и произведения Примеры решения комбинаторных Задачи Комбинаторики Перечислительная комбинаторика Краткая историческая справка

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 8

Правила суммы и произведения 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 С В в оглавление

Слайд 9

Первая цифра вторая цифра 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 в оглавление

Слайд 10

«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения». Сколькими способами могут быть расставлены 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 дор . Р е ш е н о п е р е б о р о м в а р и а н т о в в оглавление

Слайд 11

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

Слайд 12

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

Слайд 13

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