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

1.

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

2.

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

3.

3

4.

Комбинаторика
Перестановки без повторений
Перестановками без повторений называют комбинации,
состоящие из одних и тех же n различных элементов и
отличающиеся только порядком их расположения.
Пусть имеется n различных объектов, например, a, b, c, d.
Будем переставлять их всеми возможными способами (число
объектов остается неизменными, меняется только их
порядок). Получившиеся комбинации
называются перестановками , без повторений, а их число
равно:
Pn=n!=1⋅2⋅3⋅...⋅(n−1)⋅n
Символ n! называется факториалом и обозначает
произведение всех целых чисел от 1 до n. По определению,
считают, что 0!=1,1!=1.
4

5.

Смысловая нагрузка: «Сколькими способами
можно переставить n объектов?»
Сколькими способами можно переставить 3
объекта по трем местам? {1,2,3}
123
321
132
231
213
312
P3=3!=6
В каких случаях ее надо применять?
1) Число предметов должно быть равно
количеству мест.
2) Важен порядок элементов.
5

6.

Комбинаторика
Перестановки без повторений
Задача. Найти число перестановок элементов a, b, c, d, e ?
Сколько существует различных вариантов установки их в
последовательность друг за другом?
Решение.
n = 5 различных элементов, порядок важен
(последовательность друг за другом), нужно выбрать все
объекты, повторений нет.
Нужна формула: Перестановки без повторений Pn=n!
Значит, число различных расположений 5-ти
элементов : Pn=5!=1×2×3×4 ×5= 120 способов.
6

7.

Комбинаторика
Перестановки с повторениями
Пусть имеется n1 предметов 1-го типа, n2
предмета 2-го, nk предметов k-го типа и при
этом n1+n2+...+nk = n
(k ≤ n)
Количество перестановок с повторениями
из n элементов k типов (k≤n)