§ 1. Основные определения

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

С операцией отбора подмножеств связано понятие выборки, с которым можно связать как осуществление операции отбора, так и ее результат – само выбранное подмножество.

Подмножество из r элементов, выбранных из множества М, состоящего из п элементов называется выборкой объема r из п элементов или (п, r)-выборкой.

Если порядок следования элементов в выборке задан, то выборка называется упорядоченной; в противном случае – неупорядоченной.

Упорядоченная (п, r)-выборка называется (п, r)-перестановкой.

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

В выборках элементы могут повторяться или не повторяться.

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

Число (п, r)-перестановок будем обозначать символом Р(п, r), а число перестановок с повторениями − . На практике сами (п, r)-перестановки часто называются размещениями и обозначаются символом , а перестановками называются упорядоченные (п, п)-выборки.

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

Число сочетаний без повторений будем обозначать символом , с повторениями − .

Пример. Пусть М = {a, b, c}, r = 2. Указать все упорядоченные и неупорядоченные выборки с повторениями и без повторений из трех элементов по два.

□ Имеем

1. aa, ab, ac, ba, bb, bc, ca, cb, cc – девять перестановок с повторениями, = 9.

2. ab, ac, ba, bc, ca, cb – шесть перестановок без повторений, Р(3, 2) = 6.

3. ab, ac, bc – три сочетания без повторений, = 3.

4. aa, ab, ac, bb, bc, cc – шесть сочетаний с повторениями, = 6. ■