{ определение – правила равенства, суммы и произведения – принцип включений – исключений – обобщение правила произведения – общее правило произведения. - презентация

1 { определение – правила равенства, суммы и произведения – принцип включений – исключений – обобщение правила произведения – общее правило произведения – выборки – перестановки и сочетания – перестановки и сочетания с повторениями – бином ньютона – примеры }

2 Комбинаторика - раздел дискретной математики, в котором изучаются объекты, составленные из элементов конечных множеств. В комбинаторной задаче решается перечислительная задача о числе выборок, получаемых из элементов заданного конечного множества по некоторым правилам, при некоторых условиях. Pascal Blaise (1623–1662) Комбинаторный смысл биномиальных коэффициентов состоит в том, что они представляют собой число различных k - членных комбинаций из n - элементного множества без повторений. Бином Ньютона Треугольник Паскаля

3 2 A – множество всех подмножеств множества A |A| – число элементов (мощность) конечного множества A A 1 x A 2 x... x A n – прямое декартово произведение множеств A 1, A 2,.., A n. Элементами декартова произведения являются последовательности ( x 1, x 2,.., x n ), где При A 1 = A 2 = …. = A n = A получается декартова степень A n множества A. Если элементы множества A считать буквами алфавита, то элементы декартовой степени можно рассматривать как слова, они в этом случае записываются в виде {x 1 x 2 …… x n }. Буквой E обозначают двухэлементное множество {0,1}.

4 Пусть A и B - конечные множества, f - функция, определенная на A со значениями в B. f называется биекцией или взаимно однозначным отображением, если выполняются условия: 1)каждому одному элементу из A соответствует один элемент множества B (функция, удовлетворяющая этому условию, называется инъекцией); 2)для любого y B существует такой x A,что f ( x) = y (такая функция называется сюръекцией). Если существует биекция из A в B, то говорят также, что между A и B имеется взаимно однозначное соответствие.

5 Правило равенства Если между конечными множествами A и B есть взаимно однозначное соответствие, то | A | = | B |. Правило суммы Если A и B конечные множества и, то. Правило произведения Для любых конечных множеств A и B имеет место равенство. Правила суммы и произведения обобщаются на случай любого числа слагаемых или сомножителей. Для правила суммы обобщение очевидно: мощность объединения любого числа попарно непересекающихся множеств равна сумме их мощностей. A B

6 Принцип включений - исключений Пусть - конечные множества, тогда Общее правило произведения Пусть упорядоченный набор ( ) формируется в результате последовательного выбора элементов x 1, x 2, …, x n, причем для любого i = 1, 2, …, n и любых x 1, x 2, …, x n-1 элемент x i можно выбрать k i способами. Тогда весь набор может быть выбран способами.

7 Для любых конечных множеств A 1, A 2, … A k имеет место равенство Теорема Д о к а з а т е л ь с т в о При k = 2 это справедливо. Для большего числа сомножителей равенство доказываем индукцией по k. Элементами множества являются наборы вида ( ), где x i A i, i = 1, …., k. Каждый такой набор можно рассматривать как состоящий из двух частей: элемента произведение множеств от A 1 до A k-1 и x k из A k. Таким образом, имеется взаимно однозначное соответствие между пересечением множеств от A 1 до A k-1 и прямым произведением двух множеств: и A k.

8 По правилу равенства:. По правилу произведения для двух сомножителей: По предположению индукции:

9 @ Есть m различных шаров и n различных урн. Найти число способов раскладки шаров по урнам. Решение Каждый шар может занимать одно из n мест, то есть n – число способов размещения одного шара по n урнам. Воспользуемся правилом произведения. Получим, что число способов раскладки шаров по урнам будет равно n m.

10 @ Сколько существует различных четырехзначных чисел, в записи которых используются только нечетные цифры ? Решение Аналогично рассматриваем ситуации с числами, которые начинаются с цифры 3 и другие случаи. Затем анализируем случаи записи, в которых учтены первые комбинации первых двух нечетных цифр в сочетании с третьей (нечетной) цифрой,.. и так доходим до четырехзначных цифр. Поскольку на каждом из четырех мест может стоять любая из пяти цифр, то всего существует 5 · 5 · 5 · 5 = 5 4 = 625 таких четырехзначных чисел. Представим, что мы начали выписывать все такие четырехзначные числа. Для начала напишем первую цифру. Поскольку нечетных цифр всего пять (1, 3, 5, 7, 9), то она может быть любой из пяти. Если мы написали первой цифрой 1, то к ней можно приписать любую из тех же пяти цифр и получить числа 11, 13, 15, 17, 19..

11 @ Сколько существует четырехзначных чисел, все цифры которых нечетные, причем хотя бы одна из них равна 5 ? Решение Найдем теперь количество четырехзначных чисел, в которых все цифры нечетны, но нет ни одной цифры 5. Это четырехзначные числа, в записи которых встречаются только четыре цифры: 1, 3, 7, 9. Начнем проводить рассуждения как в первой задаче. На первом, втором, третьем и четвертом месте может находиться любая из четырех цифр. Значит всего таких чисел может быть 4 · 4 · 4 · 4 = 256. Количество четырехзначных чисел, все цифры которых нечетны, равно 625; количество четырехзначных чисел, которые состоят из цифр 1, 3, 7, 9 равно 256; тогда количество четырехзначных чисел, все цифры которых нечетны, причем хотя бы одна из них 5, равно = 369. Основная сложность задачи состоит в том, что не ясно, какая из цифр по счету является 5, условию задачи удовлетворяют и те числа, в которых цифр 5 несколько. Выяснено, что число четырехзначных чисел, все цифры которых нечетны, равно 625.

12 @ Сколько может быть четырехзначных чисел, делящихся на 5, если у них все цифры различные ? Решение Пусть А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – множество цифр, a = α 1 α 2 α 3 α 4 четырехзначное число, где,,,. Если α 4 = 0 тогда цифра α 1 может быть выбрана 9 способами, цифра α 2 может быть выбрана 8 способами, а α 3 – 7 способами. По правилу произведения получаем, что число α может быть получено = 504 способами. Если α 4 = 5 тогда т.е. цифра α 1 может быть выбрана 8 способами, цифра α 2 может быть выбрана также 8 способами, а α 3 – 7 способами. По правилу произведения получаем, что число α может быть получено = 448 способами. Таким образом, используя правило суммы, получаем, что существует = 952 четырехзначных числа, делящихся на 5, у которых все цифры различные.

13 В простейших комбинаторных задачах требуется подсчитать число способов выбрать k элементов из n – элементного множества. То, что получается в результате выбора, называется выборкой из n по k или (n,k) – выборкой. Понятие выборки отличается от понятия подмножества. Отличие состоит в том, что в выборках может допускаться повторение элементов. Это означает, что в выборку может входить несколько экземпляров одного и того же элемента. Говорят, что рассматриваются выборки с повторениями. Выборки могут быть упорядоченными или неупорядоченными. Упорядоченность означает, что выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, считаются различными. Если же такие выборки считаются одинаковыми, то говорят, что рассматриваются неупорядоченные выборки. Упорядоченные выборки называют перестановками (или размещениями), неупорядоченные – сочетаниями.

14 Таким образом, имеется четыре основных типа выборок: сочетания с повторениями. перестановки (без повторений), перестановки с повторениями, сочетания (без повторений) Подсчитаем число выборок каждого типа. Множеством, из которого делается выбор, будем считать множество чисел I n = { 1, 2, …., n }. Перестановки с повторениями из n по k – это последовательности длины k, состоящие из элементов множества I n, то есть элементы множества I n k. По правилу произведения следует: Перестановки с повторениями. Число (n,k) – перестановок с повторениями равно n k

15 Перестановки из n по k обозначим Доказательство В качестве первого элемента перестановки может быть выбран любой из n элементов множества I n. Поскольку повторения недопустимы, второй элемент можно выбрать n 1 способами, третий n 2 способами и т.д. Применяя обобщенное правило произведения, получаем При k = n получим формулу для числа перестановок всех n элементов Размещения

16 @ Сколько может 2 -перестановок из четырех объектов, пронумерованных как 1, 2, 3, 4 ? Решение

17 Сочетания (без повторений) из n по k Число (n,k) – сочетаний обозначим как Доказательство Сочетания из n по k, то есть неупорядоченные выборки без повторений, это просто k – элементные подмножества n – элементного множества. Выписывая элементы (n,k) – сочетания в некотором порядке, получаем (n,k) – перестановку. Поскольку k элементов можно упорядочить k ! способами, то из каждого сочетания можно образовать k ! различных перестановок. Из всех сочетаний таким образом получится перестановок. Ясно, что каждая перестановка будет при этом получена точно один раз.

18 Число перестановок с повторениями, которые получаются из n элементов находится по формуле Число ( nk ) - сочетаний с повторениями находится по формуле

19 @ Каким числом способов можно застроить улицу из 10 домов, если 3 дома пятиэтажные, 5 – двухэтажные и 2 - четырехэтажные ? Решение 524

20 @ Найти число сочетаний с повторениями по 2 из четырех элементов, пронумерованных как 1, 2, 3, 4 ? Решение

21 Бином Ньютона

22

23

24 @ Из колоды (52 карты) вынули 10 карт. Найти вероятность того, что выбран ровно один туз. Решение 10 карт можно выбрать числом способов. 1 туз можно выбрать 4 способами (число мастей 4) Оставшиеся карты можно выбрать числом способов.

25 @ Из колоды (52 карты) вынули 10 карт. Найти вероятность того, что выбрано не менее двух тузов. Решение 10 карт можно выбрать числом способов. Для выборки не менее двух тузов отнимем от общего числа способов число способов выборки без тузов и с одним тузом