Комбинаторика (комбинаторный анализ) - раздел дискретной математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Например, сколькими способами можно выбрать 6 карт из колоды, состоящей из 36 карт, или сколькими способами можно составить очередь, состоящей из10 человек и т.д. Каждое правило в комбинаторике определяет способ построения некоторой конструкции, составленной из элементов исходного множества и называемой комбинацией. Основная цель комбинаторики состоит в подсчете количества комбинаций, которые можно составить из элементов исходного множества в соответствии с заданным правилом. Простейшими примерами комбинаторных конструкций являются перестановки, размещения и сочетания.
Рождение комбинаторики связано с работами Б. Паскаля и П. Ферма по поводу азартных игр, большой вклад внесли Лейбниц, Бернулли, Эйлер. В настоящее время интерес к комбинаторике связан с развитием компьютеров. Нас в комбинаторике будет интересовать возможность определения количественно различных подмножеств конечных множеств для вычисления вероятности классическим способом.
|
|
Для определения мощности множества, которое соответствует тому или иному событию, полезно разобраться с двумя правилами комбинаторики: правило произведения и правило суммы (иногда их называют принципами умножения и сложения соответственно).
Правило nроизведения: пусть из некоторого конечного множества
1-й объект можно выбрать k 1 способами,
2-ой объект – k 2 способами,
n -ый объект - kn способами. (1.1)
Тогда произвольный набор, перечисленных n объектов из данного множества можно выбрать k 1, k 2, …, kn способами.
Пример 1. Сколько существует трехзначных чисел с разными цифрами?
Решение. В десятичной системе исчисления десять цифр: 0,1,2,3,4,5,6,7,8,9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте - любая из оставшихся 9 цифр, кроме выбранной. На последнем месте любая из оставшихся 8 цифр.
По правилу произведения 9·9·8 = 648 трёхзначных чисел имеют разные цифры.
Пример 2. Из пункта в пункт ведут 3 дороги, а из пункта в пункт – 4 дороги. Сколькими способами можно совершить поездку из в через ?
Решение. В пункте есть 3 способа выбора дороги в пункт , а в пункте есть 4 способа попасть в пункт . Согласно принципу умножения, существует 3×4 = 12 способов попасть из пункта в пункт .
Правило суммы: при выполнении условий (1.1), любой из объектов можно выбрать k 1 +k 2 +…+kn способами.
Пример 3. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих, 3 зеленых карандаша.
|
|
Решение. Один карандаш, по правилу суммы, можно выбрать 5+7+3 = 15 способами.
Пример 4. Пусть из города в город можно добраться одним авиамаршрутом, двумя железнодорожными маршрутами и тремя автобусными маршрутами. Сколькими способами можно добраться из города в город ?
Решение. Все условия принципа сложения здесь выполнены, поэтому, в соответствии с этим принципом, получим 1+2+3 = 6 способов.
Рассмотрим пример, иллюстрирующий различие принципов умножения и сложения.
Пример 5. В магазине электроники продаются три марки телевизоров и два вида видеомагнитофонов. У покупателя есть возможности приобрести либо телевизор, либо видеомагнитофон. Сколькими способами он может совершить одну покупку? Сколько различных комплектов, содержащих телевизор и магнитофон, можно приобрести в этом магазине, если покупатель собирается приобрести в паре и телевизор, и видеомагнитофон?
Решение. Один телевизор можно выбрать тремя способами, а магнитофон – другими двумя способами. Тогда телевизор или магнитофон можно купить 3+2=5 способами.
Во втором случае один телевизор можно выбрать тремя способами, после этого видеомагнитофон можно выбрать двумя способами. Следовательно, в силу принципа умножения, купить телевизор и видеомагнитофон можно 3×2 = 6 способами.
Рассмотрим теперь примеры, в которых применяются оба правила комбинаторики: и принцип умножения, и принцип сложения.
Пример 6. В корзине лежат 12 яблок и 10 апельсинов. Ваня выбирает либо яблоко, либо апельсин. После чего Надя выбирает из оставшихся фруктов и яблоко и апельсин. Сколько возможно таких выборов?
Решение. Ваня может выбрать яблоко 12 способами, апельсин – 10 способами. Если Ваня выбирает яблоко, то Надя может выбрать яблоко 11 способами, а апельсин – 10 способами. Если Ваня выбирает апельсин, то Надя может выбрать яблоко 12 способами, а апельсин – 9 способами. Таким образом, Ваня и Надя могут сделать свой выбор способами.
Пример 7. Есть 3 письма, каждое из которых можно послать по 6 адресам. Сколькими способами это можно сделать?
Решение. В данной задаче мы должны рассмотреть три случая:
а) все письма рассылаются по разным адресам;
б) все письма посылаются по одному адресу;
в) только два письма посылаются по одному адресу.
Если все письма рассылаются по разным адресам, то число таких способов легко находится из принципа умножения: n 1 = 6×5×4 = 120 способов. Если все письма посылаются по одному адресу, то таких способов будет n 2 = 6. Таким образом, остается рассмотреть только третий случай, когда только 2 письма посылаются по одному адресу. Выбрать какое-либо письмо мы можем 3 способами, и послать его по какому-либо выбранному адресу можем 6 способами. Оставшиеся два письма мы можем послать по оставшимся адресам 5 способами. Следовательно, послать только два письма по одному адресу мы можем n 3=3×6×5=90 способами. Таким образом, разослать 3 письма по 6 адресам в соответствие с принципом сложения можно
способами.
Обычно в комбинаторике рассматривается идеализированный эксперимент по выбору наудачу k элементов из n. При этом элементы: а) не возвращаются обратно (схема выбора без возвращений); б) возвращаются обратно (схема выбора с возвращением).
1. Схема выбора без возвращений
Размещением из n элементов по k называют любой упорядоченный набор из k элементов, принадлежащих n - элементному множеству. Различные размещения отличны друг от друга или порядком элементов, или составом.
Число размещений из n элементов по k обозначается и вычисляется по формуле
(1.2)
где n! = 1×2×3×…× n, 1! = 1, 0! = 1.
Пример 8. В соревнованиях участвует 10 человек, трое из них займут 1, 2, 3 место. Сколько существует различных вариантов?
Решение. В этом случае важен порядок распределения мест. Число различных вариантов равно
|
|
.
Перестановкой из n элементов называют размещение из n элементов по n. Число перестановок из n элементов обозначают Pn и вычисляют по формуле
(1.3)
Пример 9. Сколько существует способов расстановки 10 книг на полке?
Решение. Общее число способов расстановки определяется как число перестановок (1.3) из 10 элементов и равно Р 10 = 10! = 3628 800.
Сочетанием из n элементов по k называется любой набор из k элементов, принадлежащих n - элементному множеству. Различные сочетания отличаются друг от друга только составом.
Число сочетаний из n элементов по k обозначается и вычисляется по формуле
(1.4)
Справедливы тождества:
Пример 10. Сколько существует способов выбора трех человек из десяти.
Решение. В данном случае при выборе для нас важен только состав наборов по три человека, порядок выбора роли не играет, поэтому, в отличие от предыдущего примера, число способов выбора подсчитаем по формуле сочетаний (1.4)
.
2. Схема выбора с возвращениями
Если при выборе k элементов из n, элементы возвращаются обратно и упорядочиваются, то говорят, что это размещения с nовторениями.
Число размещений с повторениями:
(1.5)
Пример 11. В гостинице 10 комнат, каждая из которых может разместить четырех человек. Сколько существует вариантов размещения, прибывших четырех гостей?
Решение. Каждый следующий гость из 4 может быть помещён в любую из 10 комнат, так как рассматривается идеализированный опыт, поэтому общее число размещений, по формуле размещений с повторениями (1.5), равно
.
Если при выборе k элементов из n элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с nовторениями. Число сочетаний с повторениями из n элементов по k определяется:
(1.6)
Пример 12. В магазине продается 10 видов тортов. Очередной покупатель выбил чек на три торта. Считая, что любой набор товаров равновозможен, определить число возможных заказов.
Решение. Число равновозможных заказов по формуле (1.6) равно
.