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

1.

Теория вероятностей и
математическая статистика
Тема: Элементы
комбинаторики

2.

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

3.

Теория вероятности возникла в
17 веке, когда вероятность
различных случайных событий в
ряде азартных игр (карты,
кости…)
вычислили
французский математики Пьер
Ферма и Блез Паскаль.

4.

1
аксиома.
Вероятность
всех
возможных событий равна 1.
2 аксиома. Значение вероятности
больше либо равно нулю.
3 аксиома. Если события не могут
совпасть, их вероятности можно
складывать.

5.

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

6.

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

7.

Общие правила комбинаторики:
1.
Правило суммы.
Если элемент а может быть выбран m способами, а элемент b
другими k способами, то выбор одного из этих элементов a или
b может быть сделан m+k способами.
2. Правило произведения.
Если элемент a может быть выбран m способами, а после этого
элемент b выбирается k способами, то выбор пары элементов
(a;b) в заданном порядке может быть произведен m·k
способами.
3. Правило включения-исключения.
Если свойством S обладает m элементов, а свойством P
обладает k элементов, то свойством S или P обладает m + k − l
элементов, где l — количество элементов, обладающих
одновременно и свойством S, и свойством P.

8.

Размещение
Размещениями из m элементов по n элементов ( n ≤ m ) называются
такие соединения, каждое из которых содержит n элементов,
взятых из m данных разных элементов, и которые отличаются одно
от другого либо самими элементами, либо порядком их
расположения
Число размещений из m элементов по n обозначают
и вычисляют по формуле:

9.

Перестановки
Определение. Перестановкой из n элементов называют размещение из
n элементов по n.
Число перестановок из n элементов обозначается
и вычисляется по формуле:

10.

Сочетание
Определение.
Сочетаниями из m элементов по n элементов ( n ≤ m )
называются такие соединения, каждое из которых содержит n
элементов, взятых из m данных элементов, и которые
отличаются друг от друга по крайней мере одним элементом.
Число сочетаний из n элементов по m обозначают
и вычисляют по формуле:

11.

Примеры.
1.В вазе 7 яблок, 6 груш и 5 мандаринов.
Сколько вариантов выбора одного плода?
Решение.
7+6+5=18
Ответ: 18 вариантов.

12.

2. Из города A в город В ведут две дороги,
а из города B в город C ведут три дороги.
Сколько путей, проходящих через B,
ведут из A в C?
Решение.
2⋅3=6
Ответ: 6 путей.

13.

Сколькими способами можно составить
пару из одной гласной и одной согласной
букв слова «математика»?
Решение.
Гласные: а, е, а, и, а — 5 шт.согласные: м,
т, м, т, к — 5 шт.5⋅5=25
Ответ: 25 способами.

14.

4. Каждый ученик класса побывал в музее или на
выставке. В музей сходили 17 человек. На выставке
были 13 человек. И в музее, и на выставке были 5
человек. Сколько учеников в классе?
Решение.
Если мы найдём сумму 17+13, то окажется, что
каждого, кто побывал и в музее, и на выставке, мы
посчитали дважды. Поэтому найденная сумма на 5
больше количества учеников в классе.
Следовательно, в классе 17+13−5=25 человек.

15.

5. Пример: Пусть требуется составить набор из
ручки, карандаша и линейки.
Имеется:
5 различных ручек,
7 различных карандашей,
10 различных линеек.
Сколькими способами можно составить
требуемый набор ?
Решение:
5*7*10 = 350

16.

6. В группе 30 человек. Необходимо выбрать старосту и
профорга. Сколькими способами это можно сделать?
Решение: Старостой может быть выбран любой из 30
учащихся, т.е. существует 30 способов выбора старосты.
После того как староста уже выбран, профоргом можно
выбрать любого из оставшихся 29 учащихся. Таким
образом, одному способу выбора старосты соответствуют
29 способов выбора профорга. Следовательно, общее
число способов выбора старосты и профорга равно
30 ·29 = 870

17.

7. В техникуме работают 76
преподавателей. Из них 49 знают
английский язык, 32 - немецкий и 15
- оба языка. Сколько преподавателей
не знает ни английского, ни
немецкого языков?
Решение: Английский или немецкий
язык знают 49 + 32 – 15 = 66
преподавателей. А значит, не знают
ни одного из этих языков 77 – 66 = 10
преподавателей.

18.

8. Необходимо составить варианты контрольной работы, каждый из которых
должен содержать три задачи. Первая задача выбирается из любого
параграфа I главы сборника, вторая - из любого параграфа II главы, а третья
- из любого параграфа III главы. Сколько видов контрольной работы можно
составить, если I и III глава содержат два параграфа, а II глава - три
параграфа?
Решение: Нужно найти число способов выбора трех задач из трех
соответствующих глав.
Первую задачу можно выбрать способами, так как I глава содержит 2
параграфа. Вторую задачу можно выбрать тремя способами, так как II глава
содержит 3 параграфа. Третью задачу можно выбрать двумя способами, так
как III глава содержит 2 параграфа. Общее число способов выбора трех
задач по теореме умножения равно 2·3·2 = 12 Таким образом, можно
составить 12 различных видов контрольной работы.