§ 3. Размещения. Сочетания

Рассмотрим конечное множество с числом элементов и образуем следующее теоретико-множественное произведение:

Исходя из введем два понятия

Упорядоченные r-выборки. r-выборку, которая определена в § 2 формулой (2 2) и в которой порядок компонент фиксирован по определению, будем называть упорядоченной -выборкой.

Говорят, что две упорядоченные -выборки

равны, или эквивалентны, тогда и только тогда, когда

Упорядоченная 2-выборка называется также двойкой, упорядоченная 3-выборка — тройкой

Упорядоченная -выборка называется также размещением из элементов по Когда это размещение называется перестановкой элементов.

Неупорядоченные r-выборки. Неупорядоченная -выборка не есть -выборка в смысле данного выше определения Если в определении упорядоченной -выборки не учитывать порядок компонент, то мы приходим к неупорядоченной -выборке, которую будем обозначать

Говорят, что две неупорядоченные -выборки равны, или эквивалентны, если каждая из них состоит из одних и тех же элементов взятых одно и то же число раз.

Неупорядоченная -выборка называется также парой, неупорядоченная -выборка — триадой.

Неупорядоченная -выборка называется также сочетанием из элементов по

Пример. Пусть Тогда

Метод последовательного пересчета упорядоченных r-выборок, обладающих заданным свойством. Прежде чем описать общие алгебраические методы перечисления и пересчета упорядоченных или неупорядоченных -выборок, напомним некоторые классические приемы и результаты.

Пусть где множество -выборок обладающих заданным свойством. Подсчитаем их число, обозначая его через

Обозначим через

r-выборку, принадлежащую

Чтобы определить подсчитаем число элементов которые могут быть взяты для образования первой компоненты -выборки (если такая существует), затем число элементов которые могут быть взяты для образования

второй компоненты -выборки когда первые компоненты уже известны; действуя дальше аналогично, доходим до

Получаем

Число упорядоченных r-выборок с повторением (размещения с повторением). Определим число упорядоченных -выборок. Каждую из компонент выбираем различными способами Имеем

Из (3.7) получаем

Следовательно, существует упорядоченных -выборок с повторением.

Например, если то можно образовать упорядоченных -выборок:

Число упорядоченных r-выборок без повторения (размещения без повторения). Определим число упорядоченных -выборок, которые можно образовать, выбирая первую компоненту различными способами вторую компоненту различными способами из оставшихся элементов, компоненту различными способами из оставшихся элементов.

Имеем

В силу (3.7)

В частности, при

Число называют числом перестановок из элементов и обозначают

Например, если , то можно образовать следующих упорядоченных -выборок без повторения:

Число неупорядоченных r-выборок с повторением (сочетания с повторением). Поскольку формула (3.7) не может быть использована, так как рассматриваются неупорядоченные -выборки, мы применим другой метод.

Пусть - число неупорядоченных -выборок с повторением из где

Мы покажем, что

где

При формула (3.15) справедлива, так как и существует в точности неупорядоченных -выборок. Покажем теперь, что

Для доказательства (3.17) предварительно представим каждую выборку таким образом, чтобы индексы а ее компонент шли в неубывающем порядке слева направо. Тогда число -выборок, начинающихся единицей, равно число -выборок, начинающихся двойкой, равно число -выборок, начинающихся равно

Действуем по индукции. Пусть означает, что соотношение

выполняется. Покажем, что

Для имеем

Учитывая хорошо известное соотношение (треугольник Паскаля)

получаем

Подставим (3.22) в (3.17):

Итак,

выполняется и (3.15) доказано.

Например, если то можно образовать следующих неупорядоченных -выборок с повторением: .

Число неупорядоченных r-выборок без повторения (сочетания без повторения). Число упорядоченных -выборок без повторения в силу (3.11) (с учетом равно

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

Например, если , то можно образовать следующих неупорядоченных -выборок без повторения:

Число разбиений множества на неупорядоченных r-выборок без повторения. Отметим, что неупорядоченную -выборку без повторения можно рассматривать как множество. Заметив это, разобьем конечное множество из элементов на подмножеств таких, что

Ел

Каждое из подмножеств можно рассматривать как неупорядоченную выборку без повторения. Чему равно количество таких разбиений множества Обозначим это число через и докажем, что

Для образования неупорядоченной Ярвыборки элементы берутся из всего множества следовательно, число таких выборок равно С. Для образования неупорядоченной -выборки

в нашем распоряжении остается элементов поэтому число таких выборок равно и т. д. Перемножая эти выражения, получаем число различных разбиений.

Выражение (3.32) можно упростить. В самом деле,

Подставляя (3.33) в (3.32), имеем

Часто это выражение обозначают символически

Пример. Пусть . Найдем число разбиений Имеем

Приведем их:

УПРАЖНЕНИЯ

(см. скан)