- •Глава I. Азы комбинаторики
- •§ 1. Основные принципы комбинаторики
- •§ 2. Размещения и перестановки без повторений
- •§ 3. Размещения и перестановки с повторениями
- •§ 4. Подмножества конечных множеств и сочетания
- •§ 5. Сочетания с повторениями
- •§ 6. Принцип включения-исключения
- •§ 7. Примеры решения простейших комбинаторных задач
- •§ 8. Примеры других комбинаторных объектов и сводка некоторых результатов
- •Биномиальные коэффициенты
- •Числа Стирлинга
- •Глава II. Рекуррентные соотношения
- •§ 1. Определение и примеры рекуррентных соотношений
- •Основы метода конечных разностей
- •§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка
- •Алгоритм нахождения общего решения
- •§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 4. Метод производящих функций для решения общего линейного однородного рекуррентного соотношения с постоянными коэффициентами
- •Алгоритм нахождения общего решения
- •§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 6. Некоторые примеры применения производящих функций
§ 2. Размещения и перестановки без повторений
Рассмотрим следующую задачу: сколькими способами можно расставить на книжной полке семь книг из имеющихся пятидесяти ?
Для решения применяется принцип умножения: можно рассматривать процесс расстановки как последовательность семи экспериментов. В первом возможно 50 исходов (первую книгу можно выбрать 50-ю способами), во втором – 49 исходов (первую книгу уже брать нельзя), и т.д., в седьмом – 44 исхода. Таким образом, по принципу умножения получаем 50494847464544 возможных расстановок.
Ещё одна задача: сколькими способами можно выбрать из 20 студентов старосту, его заместителя, редактора стенгазеты и физорга ?
Здесь тоже осуществляется последовательный выбор из группы объектов нескольких. Выбрать председателя можно 20-ю способами, его зама – 19-ю, редактора – 18-ю и физорга – 17-ю. Общее количество способов получаем по принципу умножения 20191817.
Что объединяет эти задачи ? Из некоторого множества A = {a1 , … , an } делается последовательный упорядоченный выбор нескольких k объектов: вначале произвольным образом – первый, потом второй из оставшихся кроме первого, и.т.д. Другими словами, формируется упорядоченный набор попарно различных элементов (b1 ; … ; bk), где b1 , … , bk A. Любой такой набор попарно различных элементов (b1 ; … ; bk) множества A длины k называется размещением без повторений n элементов по k местам.
Поэтому имеет смысл решить более общую задачу: каково количество размещений без повторений n элементов по k местам ?
Если (читается “А из n по k”) – количество таких размещений, то легко понять, что после выбора первого элемента, осуществимого n способами в размещении (b1 ; b2 ; … ; bk) остаётся незаполненным “хвост” (b2 ; … ; bk), представляющий собой размещение без повторений из элементов множества A \ {b1} по k–1 местам. Количество способов заполнить этот “хвост” равно . Таким образом, получается рекуррентная формула , причём, очевидно, что . Поэтому
Примеры: 1. Если A = {1, 2, 3}, то все размещения трёх элементов по двум местам таковы: (1; 2), (1; 3), (2; 1), (2; 3), (3; 1), (3; 2) – всего 6 штук, т.е. = 6.
2. Если A = {1, 2, 3, 4}, то все размещения четырёх элементов по трём местам таковы:
(1; 2; 3), (1; 2; 4), (1; 3; 2), (1; 3; 4), (1; 4; 2), (1; 4; 3),
(2; 1; 3), (2; 1; 4), (2; 3; 1), (2; 3; 4), (2; 4; 1), (2; 4; 3),
(3; 1; 2), (3; 1; 4), (3; 2; 1), (3; 2; 4), (3; 4; 1), (3; 4; 2),
(4; 1; 2), (4; 1; 3), (4; 2; 1), (4; 2; 3), (4; 3; 1), (4; 3; 2).
Значит, = 24.
Следует помнить, что значение определено только при k n. Для k > n размещений без повторений n объектов по k местам не существует.
Если A = {a1 , … , an } – конечное множество из n элементов, то перестановкой объектов a1 , … , an называется произвольное их размещение на n местах, т.е. любой упорядоченный набор с попарно различными элементами. Количество всех размещений n объектов по k местам обозначается через Pn .
Поскольку перестановки являются частными случаями размещений, то формула для подсчёта общего количества верна и в этом случае. Поэтому .
Примеры: 1. Сколькими способами можно расставить 7 книг на книжной полке ?
Количество способов P7 = 7 ! = 5040.
2. Сколько слов можно получить всевозможными перестановками букв из слова “КОЛУН” ?
Ясно, что всего перестановок букв будет 5 ! = 120. Каждая перестановка даёт уникальное слово, т.к. одинаковых букв в слове нет.