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

1.

2. Множества и операции над множествами

Множество –
есть многое,
мыслимое как
единое
Георг Кантор

3.

4.

5.

6.

7.

8.

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

10. Определение

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

11. Основные понятия и формулы комбинаторики

12. Основная формула комбинаторики

• Пусть имеется m групп элементов, каждая
численностью соответственно n1, n2………… nm.
Выберем по одному элементу из каждой
группы. Тогда общее число всех возможных
комбинаций вычисляется по формуле:
N= n1 ∙ n2 ∙ ….∙ nm

13. Факториал

Произведение всех натуральных чисел
от 1 до n включительно называется
n-факториалом и обозначается n!.

14. Свойства факториала

• Основное свойство:
• Для числа 0 принято:

15. Пример вычисления:

16. Перестановки

17.

Пусть имеются три буквы А, В и С.
Составим всевозможные комбинации из этих букв:
AВС, АСВ, ВСА. ВАС, CAB, СBА.
Эти комбинации отличаются друг от друга только
расположением букв.
Комбинации из n элементов, которые
отличаются друг от друга только порядком
элементов, называются перестановками.
• Перестановки обозначаются Рn,
где n — число элементов, входящих в перестановку

18. Задача

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

19. Размещения

20.

Пусть имеются три буквы А, В и С.
Составим всевозможные комбинации только из
двух букв: АВ, ВА, АС, СА, ВС, СВ.
Эти комбинации отличаются друг от друга только
расположением букв или самими буквами.
Комбинации из n элементов по m элементам,
которые отличаются или самими элементами,
или порядком их следования, называются
размещениями.
Размещения обозначаются

21.

• В факториальной форме размещения :

22. Задача

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

23. Вычислить:

24. Сочетания

Сочетания отличаются от размещений тем,
что в них не важен порядок следования
элементов, важно только их наличие.
Количество возможных сочетаний из n
предметов по k определяется формулой:
n!
C
(n k )!k !
k
n

25. Пример вычисления числа сочетаний

Задача. В колоде карт имеется 52 карты.
Сколько имеется вариантов получения при
раздаче 5 карт? Порядок получения карт не
важен.
Решение:
Воспользуемся формулой:
52!
52 51 50 49 48 47!
(52 5)!5!
47! 1 2 3 4 5
52 51 50 49 48
26 17 10 49 12 2598960
2 3 4 5
5
C52

26. задание

1) Сколькими способами могут разместиться за
круглым столом 10 человек?
2) В турнире участвуют 11 команд. Сколько
вариантов распределения призовых мест
между ними возможно?
3) Сколько можно составить всевозможных
комбинаций из букв А, В, С и Д?
Решите задачи используя формулы
комбинаторики