Введение в комбинаторику. Определение

1.

Введение в
комбинаторику

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

Область математики,
в которой изучают
комбинаторные задачи,
называется
комбинаторикой

3.

Слово "комбинаторика" происходит от латинского
"combinare", которое означает "соединять, сочетать".
Комбинаторика - раздел математики, в котором
изучаются вопросы о том, сколько различных
комбинаций, подчиненных тем или иным условиям,
можно составить из заданных объектов.
Комбинаторными задачами интересовались и
математики, занимавшиеся составлением и
разгадыванием шифров, изучением древних
рукописей.
Сейчас комбинаторика находит приложения во многих
областях науки: в биологии, в химии, механике и т.д.

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

Раздел комбинаторики,
в котором при решении задач
подсчитывается число
решений, называется
теорией перечислений

5. Факториал

Факториа́л числа n (обозначается n!,
произносится эн факториа́л) — это
произведение всех натуральных чисел
до n включительно:
1 • 2 • 3 • … • n = n!

6. Факториал

4! = 1•2•3•4 = 24
3! = 1•2•3 = 6
6! = 1•2•3•4•5•6 = 720

7. Главное свойство факториала

(n+1)! = (n+1) • n!
Следствие
1! = 1
0! = 1

8.

Несколько первых значений для n!:
1! = 1
2! = 1 ∙ 2 = 2
3! = 1 ∙ 2 ∙ 3 = 6
4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24
5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120
6! = 5! ∙ 6 = 720 и т. д.
Принято считать,
что 0 ! = 1

9. Перестановки, размещения, сочетания

10.

Перестановки
Перестановкой из n элементов
называется каждое расположение этих
элементов в определенном порядке.
Pn = n!
Pn = 1·2·3·…·(n − 2)(n − 1)n

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

Размещением из n элементов по два
называют любую упорядоченную пару,
составленную из данных n элементов.
Количество размещений из n элементов
по два обозначают через An2
(по первой букве французского слова
arrangement – размещение)

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

Запишем все размещения из 3 элементов
a, b, с по 2:
ab ac
A 3 2 6
2
3
A n (n 1)
2
n
ba
bc
ca
cb

13.

Сколькими
способами
можно
распределить
два билета на
разные
кинофильмы
между семью
друзьями?
Размещением из n элементов
по k называют любой
упорядоченный набор из k
элементов, составленный из
данных n элементов.
A n (n 1)
2
n
A 7 (7 1) 7 6 42
2
7
Аналогично можно получить: А3n, А4n, Аkn.

14.

A n (n 1) (n 2)
3
n
A n (n 1) (n 2) (n 3)
4
n
A n (n 1) (n 2) ... (n (k 1))
k
n
A n (n 1) (n 2) ... (n k 1)
k
n
A n(n 1)( n 2) ... 3 2 1 n !
n
n

15.

Размещения
Размещением из n элементов по k ( k ≤ n )
называется любое множество, состоящее из любых
k элементов, взятых в определенном порядке из
n элементов.
Формула числа
размещений
n!
А
(n k )!
k
n
Два размещения из n элементов
считаются различными, если они
отличаются самими элементами или
порядком из расположения.

16.

n!
А
(n k )!
k
n
4!
1 2 3 4 24
A
24
4 3 !
1!
1
3
4
6!
3 ! 4 5 6
A
120
6 3 !
3!
3
6

17. Сочетания

Сочетанием из n элементов по k (k ≤ n) называют
любую группу из k элементов, составленную
из данных n элементов.
Число сочетаний из n элементов по k обозначают
k
через C n
(по первой букве французского слова combination –
сочетание).
Разница заключается в том, что если в размещении
переставить местами элементы, то получится
другое размещение, а сочетание не зависит от
порядка входящих в него элементов.

18.

Сочетания
Сочетанием из n элементов по k называется любое
множество, составленное из k элементов,
выбранных из данных n элементов.
Формула числа
сочетаний
А
С
Рn
k
n
k
n
n!
C
k!(n k )!
k
n
В сочетаниях не имеет значения, в каком
порядке указаны элементы. Два сочетания
из n элементов по k отличаются друг от
друга хотя бы одним элементом.

19.

Задача. «Проказница Мартышка, Осёл, Козёл и косолапый
Мишка затеяли сыграть квартет» и для начала стали
выбирать 4 инструмента из 11, имеющихся на складе.
Найти число возможных выборок.
Решение. Воспользуемся тем, что число всех сочетаний из
n элементов по k элементов вычисляется по формуле
n!
C
k! n k !
k
n
11!
7! 8 9 10 11
C
330
4! 11 4 ! 1 2 3 4 7!
4
11

20. Сколькими различными способами из семи участников математического кружка можно составить команду из двух человек для участия в

олимпиаде?
5! 6 7 6 7
7!
7!
C
21
2!(7 2)! 2! 5! 1 2 5!
2
2
7

21.

Сколькими различными способами можно
распределить между шестью лицами две
разные путевки в санатории?
2
6
A
6!
С
P2 6 2 ! 2!
2
6
Сколькими способами можно присудить шести
лицам три одинаковые премии?
3
6
A
С
P2
3
6