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

1.

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

2.

Комбинаторика
– это раздел математики, в котором
изучаются вопросы о том, сколько
различных комбинаций, подчиненных тем
или иным условиям, можно составить из
заданных объектов.
Правило произведения
Если существует n вариантов выбора
первого элемента и для каждого из них
имеется m вариантов выбора второго
элемента, то всего существует n•m
различных пар с выбранными таким
образом первым и вторым элементами.

3.

Перестановками из n элементов
называются соединения (комбинации),
которые состоят из одних и тех же n
элементов и отличаются одно от
другого только порядком их
расположения.

4.

Число перестановок:
Pn = n(n –1)(n – 2) 3 2 1
Произведение первых
n!
n
(1)
натуральных чисел обозначают
(читается «эн факториал»)
n! = 1 2 3 (n –2)(n–1)n
(2)
Pn = n!
(3)

5.

Размещениями из m элементов по n
элементов (n ≤ m) называются такие
соединения, каждое из которых содержит
n элементов, взятых из данных m разных
элементов, и которые отличаются одно от
другого либо самими элементами, либо
порядком их расположения.
Обозначение:
читают «А из эм по эн»:
= 12.

6.

Α
n
m=
m(m – 1)(m – 2) • … • (m – (n – 1)) (1)
= 4 • 3 • 2 = 24;
= 4 • 3 = 12;
= 5 • 4 • 3 = 60
=
(2)

7.

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

8.

Образуем все соединения,
содержащие n элементов,
выбранных из данных m
разных элементов, без
учета порядка их
расположения. Число таких
соединений
Из каждого полученного
соединения перестановками
его элементов можно
образовать Рn=n! соединений,
отличающихся одно от другого
только порядком
расположения его элементов.
Получим все размещения из
mэлементов по n, число
которых равно
По правилу произведения число таких соединений равно
С Pn A
n
m
n
m

9.

С Pn A
n
m
n
m
m!
А
при m n и Pn n!
( m n)!
n
m
m!
С
где m n
( m n)! n!
n
m

10.

Свойства:
1)С C
n
m
m n
m
2 )С C
n
m
n 1
m
C
n 1
m 1