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

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

• Что такое комбинаторика?
Какие задачи считают комбинаторными?
• Перестановки
• Размещения
• Сочетания

Не будем спорить - будем вычислять. Г. Л е й б н и ц

• Комбинаторика – радел математики, в котором рассматриваются задачи о подсчёте числа комбинаций составленных по определённым правилам.

II. Какие задачи считают комбинаторными? Комбинаторные задачи Задачи подсчёта числа комбинаций из конечного числа элементов

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

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

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

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

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

Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.

• Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.
Этот раздел комбинаторики, называемый теорией перечислений , тесно связан с теорией вероятностей.

Правила суммы и произведения

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

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

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

Правило произведения:

• Если элемент А можно выбрать из множества элементов п способами и для каждого такого выбора элемент В можно выбрать т способами, то два элемента (пару) А и В можно выбрать п·т способами.

«Примеры решения комбинаторных задач: перебор вариантов, правило суммы, правило умножения».

• Сколькими способами могут быть расставлены 4 участниц финального забега на четырёх беговых дорожках?

Рп = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов)

2 3 4 1 3 4 1 2 4 1 2 3

1 дорожка

II. Перестановки (1) К в а р т е т Проказница Мартышка, Осёл, Козёл Да косолапый Мишка Затеяли сыграть Квартет. ……………………………………………………. Ударили в смычки, дерут, а толку нет. «Стой, братцы, стой! - кричит Мартышка. – Погодите! Как музыке идти? Ведь вы не так сидите»

4·3·2·1 = 4! способов

II. Перестановки (2)

• Перестановкой из п - элементов называется комбинации, отличающиеся друг от друга лишь порядком следования элементов
• Рп- число перестановок (Р первая буква французского слова permutation- перестановка)
Рп= n ·(n- 1)·(n- 2)·(n- 3)·(n- 4)·. . .·3 ·2 ·1= n! Рп = n!

Размещения (1)

• Четыре попутчик решили обменяться визитными карточками. Сколько всего карточек при этом было использовано?
получилось 12 карточек. Каждый из четырёх попутчиков вручил визитку каждому из трёх попутчиков 4 · 3 = 12

Комбинации, составленные из k элементов, взятых из n элементов, и отличающиеся друг от друга либо составом, либо порядком расположения элементов, называются размещениями из n элементов по k (0< k ≤n ).

Размещение из n элементов по k элементов. А первая буква

французского слова arrangement : «размещение»,

«приведение в порядок»

Размещения (2)

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

Размещения (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

Р е ш е н о п е р е б о р о м в а р и а н т о в

Размещения (4)

• Можно решить и не выписывая самих размещений:
• первый элемент можно выбрать четырьмя способами, так им может быть любой элемент из четырёх;
• для каждого первого второй можно выбрать тремя способами;
• для каждых первых двух можно двумя способами выбрать третий элемент из двух оставшихся.
Получаем

Решено с использованием п р а в и л а у м н о ж е ни я

Сочетания

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

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

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

2. На окружности отмечено п точек. Сколько существует треугольников с вершинами в этих точках?

Источники информации

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

Остальные рисунки созданы Грязновой А.К.

Он может пригласить в гости одного или несколько из них. Определите общее число возможных вариантов. №3 В 9 «а» классе учатся 25 учащихся, в 9 «б» - 20 учащихся, а в 9 «в» - 18 учащихся. Для работы на пришкольном участке надо выделить трёх учащихся из 9 «а», двух -из 9 «б» и одного – из 9 «в». Сколько существует способов выбора учащихся для работы на пришкольном участке? С №1 Пять мальчиков и четыре девочки хотят сесть на девятиместную скамейку так, чтобы каждая девочка сидела между двумя мальчиками. Сколькими способами они могут это сделать? №2 Из 12 солдат, в число которых входят Иванов и Петров, надо отправить в наряд трёх человек. Сколькими способами это можно сделать, если: а) Иванов и Петров должны пойти в наряд обязательно; б) Иванов и Петров должны остаться; в)Иванов должен пойти в наряд, а Петров –остаться? (Ответы) Устал - отдохни.

В №1 В шахматном кружке занимаются 16 человек. Сколькими способами тренер может выбрать из них для предстоящего турнира: а) команду из четырёх человек; б) команду из четырёх человек, указав при этом, кто из членов команды будет играть на первой, второй, третьей и четвёртой досках?

Перестановки элементов

Слайдов: 24 Слов: 2494 Звуков: 0 Эффектов: 0

Дискретный анализ. Комбинаторика. Перестановки. Нумерация перестановок. Отображение. Пример отображения. Нумерация множества. Теорема о лексикографическом переборе перестановок. Прямой алгоритм лексикографического перебора перестановок. Формальное описание алгоритма. Перебор перестановок. Задача о минимальном числе инверсий. Экзаменационные вопросы. Задача о минимуме скалярного произведения. Задача о наибольшей возрастающей подпоследовательности. Перебор перестановок элементарными транспозициями. - Комбинаторика.ppt

Комбинаторика 9 класс

Слайдов: 44 Слов: 2047 Звуков: 0 Эффектов: 174

Элементы комбинаторики. Не нужно нам владеть клинком, Не ищем славы громкой. Содержание курса. Тема 1. Знакомство с комбинаторикой. Основное содержание: 1. Какую задачу называют комбинаторной. Перестановка. Тематическое планирование. Обобщающий урок по теме «Элементы комбинаторики». Цель урока: I. Фронтальный опрос. Ход урока. Вопрос 1: Как обозначается произведение чисел от 1 до n? Ответ: Произведение всех натуральных чисел от 1 до n обозначается n! (n! =1 · 2 · 3…n). Вопрос 2: Что называется размещением? По какой формуле вычисляется размещение? Число размещений из n объектов по k обозначают и вычисляют по формуле: - Комбинаторика 9 класс.ppt

Понятие комбинаторики

Слайдов: 23 Слов: 922 Звуков: 0 Эффектов: 2

Комбинаторика. Тонкости. Варианты решения задачи. Область математики. Граф. Дерево возможных вариантов. Комбинаторная задача. Решение элементарных задач. Цифры. 9 правил комбинаторики. Правило произведения. Формула включений и исключений. Решение. Правило размещения. Сигналы. Размещение без повторения. Правило перестановки. Сочетание без повторения. Сочетание с повторением. Капля в море. - Понятие комбинаторики.ppt

Элементы комбинаторики

Слайдов: 15 Слов: 887 Звуков: 0 Эффектов: 20

Тема урока: «элементы комбинаторики» (практикум). Что такое комбинаторика? В чем состоит комбинаторное правило умножения? Что такое перестановки? Записать формулу для нахождения числа перестановок? Что такое факториал? Что такое размещения? Записать формулу для нахождения числа размещений? Что такое сочетания? Записать формулу для нахождения числа сочетаний? В чём различие между перестановками, размещениями и сочетаниями? Подбор комбинаторных задач. Сколько существует способов выбора учащихся для работы на пришкольном участке? Отгадай ребусы. Понятие науки « Комбинаторика». - Элементы комбинаторики.ppt

Комбинаторика и её применение

Слайдов: 28 Слов: 820 Звуков: 0 Эффектов: 1

Комбинаторика и ее применение. Проблемный вопрос. Комбинаторика. Решение комбинаторных задач. Устный счет. Двузначное число. Сколько различных трехзначных чисел можно составить из цифр. Трехзначное число. Сколько четырехзначных чисел можно составить из 4 цифр. Четырехзначное число. Обществознание и математика. Расписание на вторник. Ученик. Обед. Сколько различных комбинаций одежды имеется у Светланы. Костюм. На полке лежат 3 книги. Решение. Опыт с листом бумаги. Складывание. Самостоятельная работа. Владелец золотой медали. Области применения комбинаторики. Химия. Комбинаторика вокруг нас. - Комбинаторика и её применение.ppt

Комбинаторика и теория вероятности

Слайдов: 40 Слов: 1127 Звуков: 0 Эффектов: 187

Введение в комбинаторику и теорию вероятностей. Комбинаторика. Дерево вариантов. Квадратные числа. Треугольные числа. Прямоугольные и непрямоугольные числа. Факториал. Перестановки. Восемь участниц финального забега. Цифры. Трёхтомник одного автора. Размещения. Из 12 учащихся нужно отобрать по одному человеку. Все цифры различны. Сколько существует трёхзначных чисел. Сочетания. Треугольник Паскаля. Сколькими способами можно выбрать трёх дежурных. Выбор букета. Три помидора. Частота и вероятность. Определение. Выбирается один шар. Два игральных кубика. Сложение вероятностей. - Комбинаторика и теория вероятности.ppt

Соединения в комбинаторике

Слайдов: 22 Слов: 1225 Звуков: 0 Эффектов: 43

Виды соединений в комбинаторике. Знакомство с теорией соединений. Раздел математики. Возникновение комбинаторики. Метод решения комбинаторных задач. Полный перебор. Встретились пятеро. Правило произведения. Обобщение правила произведения. Основные задачи комбинаторики. Виды соединений. Перестановки. Размещения. 8 участниц финального забега. Сочетания. Букет. Бином Ньютона. Разные стороны. Лишних знаний не бывает. - Соединения в комбинаторике.ppt

Комбинации

Слайдов: 7 Слов: 205 Звуков: 0 Эффектов: 22

Комбинаторные задачи. Перестановки Размещения Сочетания (выборки). Самостоятельная работа. Самостоятельная работа состояла из 2 заданий. Работу писали 27 учащихся. Задачу правильно решили 13 уч., а пример-17. не справились с работой 3 ученика. Сколько учеников успешно решили самостоятельную работу. Контрольная работа состояла из задачи и примера. Работу писали 30 уч. Первое задание правильно решили 14 уч., а второе -13. не справились с контрольной 4 ученика. Сколько учеников успешно решили контрольную работу. Задача №1. Решение: АВС, АСВ, ВАС,ВСА,САВ,СВА 6 комбинаций. Перестановки: Задача №2. - Комбинации.ppt

Размещение элементов

Слайдов: 7 Слов: 222 Звуков: 0 Эффектов: 0

Комбинаторика. Размещение и сочитание. Размещение. Сочетание. В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Формулы: Для любых натуральных чисел n и k где n>k,справедливы равенства: Для числа выборов двух элементов из n данных: - Размещение элементов.ppt

Формулы для перестановок, сочетаний, размещений

Слайдов: 11 Слов: 547 Звуков: 0 Эффектов: 0

Формулы для подсчёта количества перестановок. Подарок. Перестановки. Количество перестановок. Размещения. Количество размещений. Сочетания. Количество сочетаний. Слово «факториал». Очередь. Лесник. - Формулы для перестановок, сочетаний, размещений.ppt

Комбинаторные задачи

Слайдов: 6 Слов: 228 Звуков: 0 Эффектов: 2

Комбинаторные задачи. Из цифр 1, 5, 9 составить все трёхзначные числа без повторяющихся цифр. №2. Дерево возможных вариантов. - Комбинаторные задачи.ppt

Задачи по комбинаторике

Слайдов: 9 Слов: 213 Звуков: 0 Эффектов: 20

Комбинаторика. Правило сложения Правило умножения. Задача №1. Сколькими способами можно выбрать одну книгу. Решение: 30 + 40 = 70 (способами). Правило суммы. Задача № 2. Задача № 3. Пусть существует три кандидата на пост командира и 2 на пост инженера. Сколькими способами можно сформировать экипаж корабля, состоящий из командира и инженера? Решение: 3 * 2 = 6 (способ). Правило умножения. - Задачи по комбинаторике.ppt

«Комбинаторные задачи» 9 класс

Слайдов: 11 Слов: 1126 Звуков: 0 Эффектов: 0

Комбинаторные задачи и начальные сведения из теории вероятностей. Примерное планирование. Комбинаторные задачи. Способы решения комбинаторных задач. У Ирины пять подруг: Вера, Зоя, Марина, Полина и Светлана. Составьте все возможные трёхзначные числа. Определение. Множество, состоящее из любых К элементов. В каком порядке указаны элементы. Начальные сведения из теории вероятности. На полке стоят 12 книг, из которых 4 – это учебники. - «Комбинаторные задачи» 9 класс.ppt

Примеры комбинаторных задач

Слайдов: 17 Слов: 536 Звуков: 0 Эффектов: 31

Перестановки. Комбинации. Перестановки. Формула перестановки. Количество перестановок. В турнире участвуют семь команд. Сколько вариантов расписания можно составить. Размещения. Состав выбранных объектов. Выбор и перестановка объектов. Сколькими способами можно расставить 5 томов на книжной полке. Количество трехзначных чисел. Сочетания. Имеется n различных объектов. Варианты распределения. Количество возможных вариантов сочетаний. Сколькими способами можно сформировать бригаду. - Примеры комбинаторных задач.ppt

Решение комбинаторных зада

Слайдов: 39 Слов: 2705 Звуков: 0 Эффектов: 45

Решение комбинаторных задач. Что такое комбинаторика. Из истории комбинаторики. Число различных комбинаций. Лейбниц. Простые и наглядные методы. Методы решения комбинаторных задач. Правило суммы. Правило произведения. Сколько среди них чисел, кратных 11. Сколько существует способов. Сколько различных трехзначных чисел. Флаг в виде четырех горизонтальных полос. Общее количество вариантов. Сколько всего стран. Крестики и нолики. Разные значки. Сколькими способами можно посадить шестерых школьников. Коля сидит на краю. Четырехзначные числа. На входной двери дома установлен домофон. - Решение комбинаторных зада.ppt

Комбинаторные задачи и их решения

Слайдов: 11 Слов: 1585 Звуков: 0 Эффектов: 5

Комбинаторные задачи и их решения. Пояснительная записка. Углубление знаний учащихся. Появление стохастической линии. Требования к уровню подготовки. Учебно-тематический план. Содержание программы. Поурочное планирование. Презентации. Школьнику о теории вероятностей. - Комбинаторные задачи и их решения.ppt

Методы решения комбинаторных задач

Слайдов: 21 Слов: 587 Звуков: 0 Эффектов: 0

Решение комбинаторных задач с помощью графов. Вопросы к уроку. Чем занимается комбинаторика. Что такое граф. Примеры графов. Задача. Пример полного графа. Конверт. Ужасные грабители. Число. Сколько трёхзначных чисел можно составить. Цифры в записи числа. Сколькими способами вы можете рассадить 3-х гостей на 3-х разноцветных табуретках. Правило произведения. Имеющиеся места. Способы. Расписание на пятницу. - Методы решения комбинаторных задач.ppt

Число вариантов

Слайдов: 24 Слов: 797 Звуков: 0 Эффектов: 386

Комбинаторные задачи. Комбинаторика. Выбор. Расположение. Перестановки. Способы решения комбинаторных задач: Таблица вариантов Дерево вариантов Правило умножения. 1. Дерево вариантов. Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр. 2 комбинации. Всего 2 3=6 комбинаций. Сколько четных двузначных чисел можно составить из цифр 0,1,2,4,5,9? Ответ:15 чисел. Таблица вариантов. Сколько вариантов завтрака есть? Х/б изд. Напитки. Булочка. Кекс. Пряники. Печенье. Чай. Сок. Кефир. Выбор напитка- испытание А. Выбор хл./бул. изделия.- испытание В. Правило умножения. В коридоре висят три лампочки. - Число вариантов.pptx

Принцип Дирихле

Слайдов: 20 Слов: 1358 Звуков: 0 Эффектов: 50

Принцип Дирихле. Биография. Формулировка. Область применения. Задачи. Доказательство. Средние линии треугольника. 11 различных целых чисел. Принцип Дирихле для длин и площадей. Попарно не пересекающиеся отрезки. - Принцип Дирихле.ppt

Граф

Слайдов: 40 Слов: 1071 Звуков: 0 Эффектов: 155

Я решил разобраться какую роль в обычной жизни играют графы. Исследовать роль графов в нашей жизни. Научиться работать с программой подготовки презентаций Microsoft PowerPoint. Что такое граф. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа. Вершина графа. Количество рёбер, выходящих из вершины графа, называется степенью вершины. Нечётная степень. Чётная степень. История возникновения графов. Задача о Кенигсбергских мостах. Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. - Граф.ppt

Виды графов

Слайдов: 15 Слов: 429 Звуков: 0 Эффектов: 11

Графы. Состав графа. Изображение вершин. Неориентированный граф. Граф отношения «переписываются». Ориентированный граф. Взвешенный граф. Семантическая сеть. Иерархия. Дерево – граф иерархической структуры. Корень – главная вершина дерева. Файловая структура. Самое главное. Какая связь между графом и таблицей. Как называется взвешенный граф иерархической структуры. - Виды графов.ppt

Теория графов

Слайдов: 14 Слов: 1029 Звуков: 0 Эффектов: 0

V-множество вершин, E- множество ребер Граф - G(V, Е). G(V, Е, f) V,E – множества, отображение инциденции f: Е? V&V множества Е в V&V. Основы теории графов. Определение инцидентности. Пусть задан абстрактный граф G(V, Е, f). Если f(е) = (x&x), то ребро называется петлей в вершине х. Определение смежности. Теорема 1. В любом конечном графе G(V, Е) количество нечетных вершин - четно. Пример операций разборки. В противном случае маршрут незамкнутый. Цепь - незамкнутый маршрут, состоящий из последовательности различных ребер. Цикл - замкнутый маршрут, состоящий из последовательности различных ребер. - Теория графов.ppt

Применение теории графов

Слайдов: 15 Слов: 895 Звуков: 0 Эффектов: 0

Теория «графов». Несколько слов о памяти. Психический процесс. Человеческая память. Приём развития картографической памяти. Математическая модель. Страны. Столицы. Выполнение заданий. Задания к «графам». Проверочный практикум. Политическая карта. Панама. Возможность. - Применение теории графов.ppt

Кратчайший путь

Слайдов: 36 Слов: 1830 Звуков: 0 Эффектов: 0

Нахождение кратчайшего пути. Содержание. Графы: определения и примеры. Три способа изображения одного графа. Пример двух разных графов. Степень вершины. Смежные вершины и рёбра. Путь в графе. Достижимость. Длина пути. Примеры неориентированных графов. Ориентированные графы. Смешанный граф. Путь в орграфе. Примеры ориентированных графов. Взвешенные графы. Длина пути во взвешенном графе. Примеры взвешенных графов. Способы представления графов. Матрица смежности. Пример матрицы смежности. Преимущества матрицы смежности. Иерархический список. Пример иерархического списка. Преимущества иерархического списка. - Кратчайший путь.ppt

Остовное дерево

Слайдов: 39 Слов: 2332 Звуков: 0 Эффектов: 18

Остовные деревья. Минимальное остовное дерево. Максимальный взвешенный лес. Эквивалентные задачи. Эквивалентность. Доказательство. Условия оптимальности. Оптимальное решение. Алгоритм Краскала. Алгоритм Краскала находит оптимальное решение. Алгоритм Краскала можно реализовать. Связный граф. Как улучшить шаг. Время работы шага. Алгоритм Прима. Алгоритм Прима находит решение. Как реализовать шаг. Максимальный взвешенный ориентированный лес. Минимальное остовное ориентированное дерево. Корневое ориентированное дерево. Эквивалентность трех задач. Ориентированный лес. Ориентированный лес и циклы. -

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

Студента Группы ПР – 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). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математика м (С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским

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

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

• В Древней Греции

• подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей и т.д.

• Со временем появились различные игры
• (нарды, карты, шашки, шахматы и т. д.)

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

• Готфрид Вильгельм Лейбниц (1.07.1646 - 14.11.1716)

• Комбинаторику, как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика».

• Леонард Эйлер(1707-1783)

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

Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами.

• Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами.
• При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В.
• Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k-число совпадений.

В коробке находится 10 шаров: 3 белых, 2 черных, 1 синий и 4 красных. Сколькими способами можно взять из ящика цветной шар?

• В коробке находится 10 шаров: 3 белых, 2 черных, 1 синий и 4 красных. Сколькими способами можно взять из ящика цветной шар?
• Решение:
• Цветной шар – это синий или красный, поэтому применим правило суммы:

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.

• Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.
• При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Сколько может быть различных комбинаций выпавших

• Сколько может быть различных комбинаций выпавших
• граней при бросании двух игральных костей?
• Решение:
• На первой кости может быть: 1,2,3,4,5 и 6 очков, т.е. 6 вариантов.
• На второй – 6 вариантов.
• Всего: 6*6=36 вариантов.

• Правила суммы и произведения верны для любого количества объектов.

№1. Из города А а город В ведут 6 дорог, а из города В в город С – 3 дороги. Сколькими способами можно проехать из города А в город С?

• №1. Из города А а город В ведут 6 дорог, а из города В в город С – 3 дороги. Сколькими способами можно проехать из города А в город С?
• №2. На книжной полке стоят 3 книги по алгебре, 7 по геометрии и 2 по литературе. Сколькими способами можно взять с полки одну книгу по математике?
• №3. В меню имеется 4 первых блюда, 3 – вторых, 2 – десерта. Сколько различных обедов можно из них составить?

• « Эн факториал»-n!.

• Определение.
• Произведение подряд идущих первых n
• натуральных чисел обозначают n! и называют
• «эн факториал»: n!=1 2 3 … (n-1) n.

• 1 2 3=

• 1 2 3 4=

• 1 2 3 4 5=

• 1 2 3 4 5 6=

• 1 2 3 4 5 6 7=

• n!=(n-1)! n

• Удобная формула!!!

Комбинации из n-элементов, отличающиеся друг от друга только порядком следования элементов, называются перестановками.

• Комбинации из n-элементов, отличающиеся друг от друга только порядком следования элементов, называются перестановками.
• Обозначаются Рn

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

• Из чисел 1, 5, 9 составить трёхзначное
• число без повторяющихся цифр.

• 2 комбинации

• 2 комбинации

• 2 комбинации

• Всего 2 3=6 комбинаций.

Комбинации из n-элементов по k, отличающиеся друг от друга составом и порядком, называются размещениями.

• Комбинации из n-элементов по k, отличающиеся друг от друга составом и порядком, называются размещениями.

• Размещения

Комбинации из n-элементов по к к .

• Комбинации из n-элементов по к , отличающиеся только составом элементов, называются сочетаниями из n -элементов по к .

• Сочетания

Из 20 учащихся надо выбрать двух дежурных.

• Из 20 учащихся надо выбрать двух дежурных.
• Сколькими способами это можно сделать?

• Решение:

• Надо выбрать двух человек из 20.
• Ясно, что от порядка выбора ничего не зависит, то есть
• Иванов - Петров или Петров - Иванов - это одна
• и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

1. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять: из 8 букв; из 7 букв; из 3 букв?

• 1. Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять: из 8 букв; из 7 букв; из 3 букв?
• 2. Студенту необходимо сдать 4 экзамена в течение десяти дней. Сколькими способами можно составить ему расписание экзаменов?
• 3. Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?
• 4. Сколько существует различных автомобильных номеров, которые состоят из 5 цифр, если первая из них не равна нулю? Если номер состоит из одной буквы, за которой следуют четыре цифры, отличные от нуля?
• 5. Подрядчику нужны 4 плотника, а к нему с предложением своих услуг обратились 10. Сколькими способами он может выбрать среди них четверых?
• 6. Сколькими способами можно расставить на полке семь книг
• 7. Сколько 5-буквенных слов можно образовать, используя для этого 10 различных букв.
• 8. Сколькими способами можно отобрать несколько фруктов из семи яблок, четырех лимонов и девяти апельсинов? (Фрукты одного вида считаем неразличимыми.)