Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 8. Тема: Сочетания. Цель: Разобрать формулы.

Презентация:



Advertisements
Похожие презентации
Сочетания Сочетания Определение 1 Сочетанием из n элементов по k называется всякая совокупность попарно различных k элементов, выбранных каким-либо способом.
Advertisements

Комбинаторика. Сочетания Определение 1 k-сочетанием множества А называется неупорядоченный набор попарноразличных элементов множества А длины k. Другими.
Комбинаторика 1. Комбинаторика Комбинаторика – раздел математики, посвященный подсчету количеств разных комбинаций элементов некоторого, обычно конечного,
ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ (КОМБИНАТОРИКА) §1. Принципы сложения и умножения Комбинаторика занимается подсчетом количеств разных комбинаций, которые можно.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 7. Тема: Размещения. Цель: Рассмотреть.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 4. Тема: Множество. Операции над множествами.
{ определение – правила равенства, суммы и произведения – принцип включений – исключений – обобщение правила произведения – общее правило произведения.
Вероятности случайных событий. Теория вероятностей математическая наука, изучающая закономерности случайных явлений.
Перестановки. Перестановки Определение 1 Перестановкой из n элементов называется всякий способ нумерации этих элементов Пример 1 Дано множество. Составить.
Правило умножения Если элемент А можно выбрать m способами, а элемент В можно выбрать n способами, то пару А и В можно выбрать m*n способами.
§ 4. Формула включений-исключений. Беспорядки. Теорема 1 (формула включений- исключений). Пусть А = А 1 А 2 … А m – конечное множество. Тогда.
УРОК 4. Элементы комбинаторики.. Задачи на непосредственный подсчет вероятностей Комбинаторика изучает количество комбинаций (подчиненное определенным.
Основы математической обработки информации Элементы комбинаторики.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 10. Тема: Основные принципы комбинаторики. Цель: Ознакомиться.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 5. Тема: Вычисление множеств. Выражение.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 2. Тема: Таблица истинности. Основные.
Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 16 Тема: Метод математической индукции.
«Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр.
Комбинаторика. Комбинаторика Комбинаторика – раздел математики, посвященный подсчету количеств разных комбинаций элементов некоторого, обычно конечного,
Элементы комбинаторики Лекция 4. Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.
Транксрипт:

Кафедра математики и моделирования Старшие преподаватели Е.Д. Емцева и Е.Г. Гусев Курс «Высшая математика» Лекция 8. Тема: Сочетания. Цель: Разобрать формулы для числа сочетаний с повтором и без повтора. Освоить их применение при решении задач.

Сочетания Определение 1 Сочетанием из n элементов по k называется всякая совокупность попарно различных k элементов, выбранных каким-либо способом из данных n элементов. Другими словами k-сочетание – это k- элементное подмножество n элементного множества. Пример. Дано множество. Составим 2- сочетания:

Сочетания Теорема 1 Число k- сочетаний n-элементного множества вычисляется по формуле Доказательство. Из каждого k-сочетания, переставляя его элементы всевозможными способами, получим k! размещений. Значит, Отсюда

Пример Сколькими способами можно выбрать 3 плитки шоколада из имеющихся 5 плиток? Решение. Задача сводится к вычислению числа сочетаний из 5 по 3

Свойства сочетаний 1) Доказательство: 2) Доказательство:

Свойства сочетаний 3) Доказательство: 4) Доказательство:

Бином Ньютона Доказательство. Доказательство поведем индукцией по n. 1)Базис индукции. При n=1 бином Ньютона имеет вид Упростив выражение, получим верное равенство 2) Индуктивное предположение. Допустим при n=t выполняется равенство

Бином Ньютона 3)Индуктивный переход. Докажем, что при n=t+1 выполняется равенство Для этого домножим в равенстве индуктивного предположения левую и правую части на. Получим

Бином Ньютона Раскроем скобки в правой части равенства Приведем подобные Используем свойства числа сочетаний

Следствия из бинома Ньютона получается из бинома Ньютона при 1)Равенство 2) Равенство

Сочетания с повторениями

Сочетание с повторениями Определение 1 Сочетанием из n элементов по k называется всякая совокупность k элементов, выбранных каким-либо способом из данных n элементов. Пример: Дано множество А=. Составим 2- сочетания с повторениями:

Число сочетаний с повторениями Теорема 1. Число k-сочетание с повторениями n – элементного множества вычисляется по формуле Доказательство. Лемма. Количество упорядоченных наборов из 0 и 1 длины n, состоящих из k единиц равно. Доказательство Леммы. Упорядоченный набор из 0 и 1 однозначно определяется выбором мест для единиц. Число различных вариантов выбора k мест для единиц вычисляется по формуле Лемма доказана.

Число сочетаний с повторениями Строим k-сочетания с повторениями из элементов множества В каждом таком наборе сначала расположим элементы типа, затем типа,и так далее. Каждому k- сочетанию с повторениями поставим в соответствие последовательность из 0 и 1 длины n+k-1, число единиц в этой последовательности равно k, число нулей n-1. Каждый 0 отделяет наборы различных типов. Каждое k-сочетание с повторениями однозначно определяет указанную последовательность и наоборот. По лемме таких последовательностей существует. Значит,

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

Порядок важен Порядок не важен С повторениями Без повторений Сводная таблица

Решение задач

Задачи 1) В почтовом отделении продают 5 видов интернет-карт. Сколькими способами можно купить в нем 3 различные карты? Сколькими способами можно купить 3 карты? Решение. Ответ на первый вопрос получим с помощью формулы числа сочетаний без повторений, так как карты различные На второй вопрос ответим, используя формулу числа сочетаний с повторениями, так как не сказано, что карты различных видов, значит виды карт могут повторяться

Задачи 2)В классе 8 мальчиков и 9 девочек. Сколькими способами можно выбрать группу детей, состоящей из 4 мальчиков и 3 девочек? Решение. Четырех мальчиков выберем из 8, троих девочек – из 9. По правилу умножения получим

Задачи 3)Используя бином Ньютона, раскрыть скобки. Решение.

Задачи 4)Сколькими способами можно раздать 6 одинаковых апельсинов между тремя детьми? Решение. Так как апельсины одинаковые, их вообще нельзя использовать в качестве 6 различных элементов множества. Рассмотрим множество, состоящее из троих детей. Будем выбирать детей для апельсинов. Используем формулу числа сочетаний с повторениями, так как одному ребенку может достаться несколько апельсинов, а может не достаться ни одного.

Задачи 5) Сколькими способами можно распределить 5 одинаковых принтеров, 3 телефонных аппарата, 7 мониторов между 4 фирмами? Решение. Распределим сначала принтеры, затем телефонные аппараты, и, наконец, мониторы. Используя правило умножения, получим

Задачи 6) Сколькими способами можно закодировать дверь, если она открывается при одновременном нажатии определенного количества различных цифр? Код может состоять из 1, или 2, или …,или 10 цифр. Для однозначного кода различных вариантов существует, для двузначного, …, для десятизначного. По правилу сложения получим Использовали следствие из бинома Ньютона.

Вопросы: Сравнить выражения С и А Вычислить С k n n k 8 2