Дискретная математика. Азарнова Т.В - 28 стр.

UptoLike

Комбинаторика
28
правилу произведения выбор гласной и согласной можно осуществить 15-ю
способами.
§2. Выборки и упорядочения
Известно, что
k
- выборка из некоторого множества представляет
собой комбинацию из
k
элементов этого множества. Выборки, в которых все
элементы различны, называются
выборками без повторения
, в отличие от
выборок с повторениями
, в которые могут входить одинаковые элементы.
Выборка называется
упорядоченной
, если существенным является не только
состав элементов в ней, но и порядок их расположения. Две упорядоченные
выборки считаются
различными
, если они отличаются либо составом
элементов, либо порядком их расположения.
1
. Размещения
.
Размещения без повторения
. Пусть имеется множество, содержащее
n
элементов. Каждое его упорядоченное подмножество, состоящее из
k
элементов, называется
размещением из n элементов по k элементов
.
Из определения вытекает, что 0
kn
и что размещения из
n
элементов по
k
элементовэто все
k
-элементные подмножества,
отличающиеся составом элементов или порядком их следования. Для
множества, состоящего из 4-х элементов
dcba
,,,, существует 24
размещения по 3 элемента:
dcbdcadbacba
dbcdacdabcab
cdbcdabdabca
cbdcadbadbac
bdcadcadbacd
bcdacdabdabc
Они отличаются друг от друга либо составом элементов, либо
порядком их расположения.
В комбинаторных задачах необходимо уметь подсчитывать число всех
размещений из
n
элементов по
k
элементов. Для обозначения этого числа
применяется специальный символ
k
n
A
число размещений из
n
по
k
»).
A
- первая буква французского слова
arrangement,
что означает
размещение, приведение в порядок. Мы уже видели, что
24
3
4
=
A
. В общем
случае на вопрос о числе размещений из
n
элементов по
k
элементов дает
ответ следующая формула: