Дискретная математика. Комбинаторика. Соколова С.В. - 10 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

10
Пример
.
Пару
лыж
можно
выбрать
шестью
способами
,
пару
ботинок
–
тремя
.
Сколькими
способами
можно
выбрать
лыжи
с
ботинками
?
Здесь
выбираем
пару
элементов
(
лыжи
,
ботинки
) –
всего
6 3 18
⋅ =
способов.
Правило
включения
-
исключения. Если свойством
S
обладает
m
элементов, а свойством
P
обладает
k
элементов, то свойством
S
и
P
обладает
m k l
+ −
элементов, где
−
количество элементов,
обладающих одновременно и свойством
S
, и свойством
P
.
Пример. На полке стоят банки с компотом из яблок и груш. В
десяти банках есть яблоки, в шести – груши, в трех – и яблоки, и груши.
Сколько всего банок на полке? Здесь
10
m
=
,
6
k
=
,
3
l
=
, т.е. всего на
полке
10 6 3 13
m k l
+ − = + − =
банок.
4. РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ
Задача. Определить количество всех упорядоченных наборов
(
)
1 2
, ,...,
m
x x
х
длины
m
, которые можно составить из элементов
множества
(
)
X X n
=
, если выбор каждого элемента
i
x
,
1,2,...,
i m
=
,
производится из всего множества
X
.
Упорядоченный набор
(
)
1 2
, ,...,
m
x x х
-
это элемент декартова
произведения
...
m
X X X X
× × × =
, состоящего из m одинаковых
множителей
X
. По правилу произведения количество элементов
множества
m
X
равно
m
m m
X X n
= =
. Мы вывели формулу
m
m
n
A n
=
.
Пример. Сколько четырехзначных телефонных номеров можно
составить, если использовать все десять цифр?
Здесь
10, 4
n m
= =
,
и количество телефонных номеров равно
4
4
10
10 10000
A
= = .
5.
РАЗМЕЩЕНИЯ
БЕЗ
ПОВТОРЕНИЙ
Задача
.
Сколько
упорядоченных
наборов
(
)
1 2
, ,...,
m
x x
х
можно
составить из
n
элементов
множества
X
,
если
все
элементы
набора
различны
?
Первый
элемент
1
x
можно
выбрать
n
способами
.
Если
первый
элемент
уже
выбран
,
то
второй
элемент
2
x
можно
выбрать
лишь
1
n
−
способами
,
а
если
уже
выбран
1
m
−
элемент
1 2 1
, ,...,
m
x x
х
−
,
то
элемент
m
x
можно
выбрать
(
)
1 1
n m n m
− − = − +
способами
(
повторение
уже

Страницы