Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 33 стр.

UptoLike

32
4
при k=4.
9. Из множества A = {a, b, c, d} составить:
а ) упорядоченные 2-выборки без повторений;
б) неупорядоченные 2-выборки без повторений.
Сколько их всего может быть?
Ответ : а ) 12; б) 6.
При решении комбинаторных задач, в которых требуется определить
количество некоторых выборок (комбинаций) из данного множества эле-
ментов, основным моментом является правильное определение типа (ха -
рактера ) выборок упорядоченные это выборки или нет , с повторениями
или без повторений.
Комбинациям , которые встречаются в этих задачах, присвоены осо-
бые названия размещения, сочетания и перестановки.
Размещения без повторений и с повторениями
Размещениями без повторений из п элементов по к называются
упорядоченные k-выборки из п элементов без повторений. Их число
обозначается
k
n
A
и вычисляется по формуле :
k
n
A
= n
×
(n-1)
×
(n-2)
×
×
(n-k + 1) =
)!(
!
kn
n
, k
n. (2)
Обычно размещения без повторений из n элементов по n называются
перестановками из n элементов. Их число обозначается P
n
и вычисляется
по формуле:
P
n
=
n
n
A
= n! (3)
Пример 7. Сколькими способами можно составить трехцветный по -
лосатый флаг, если имеется материал пяти различных цветов?
Решение. Нужно найти число 3-выборок из 5 элементов без повто-
рений (все цвета различны); порядок, в котором располагаются выбранные
цвета , существенен . Следовательно, нужно найти число упорядоченных
выборок, т .е. число размещений из 5 по 3 без повторений. По формуле (2)
имеем
3
5
A
=
)!35(
!5
=5
×
4
×
3 = 60 (способов).
Заметим, что эту задачу можно решить иначе. Для выбора цвета пер-