Комбинаторика – это область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить с заданным объектом. Данный раздел математики занимается решением задач выбора и расположения элементов некоторого множества, в соответствии с заданными правилами.
К основным понятиям относят еще комбинаторные объекты, конфигурации и выборка. Правила, которые представляют собой метод построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций является перестановки, сочетания и размещения.
Выборкой является некоторая совокупность элементов некоторого множества, а число элементов в выборке называется длиной выборки.
Г. Дж. Райзер в своем труде выделяет в основном два типа задач.
В первом из них существование предписанной конфигурации сомнительно, и исследование состоит в попытках доказать это существование. Такие задачи называются задачи о проблеме существования.
Во втором типе задач существование конфигураций известно, а при исследованиях стремятся определить число конфигураций или дать их классификацию.
Такие задачи мы называем перечислительными. Вторая категория задач есть не что иное, как усовершенствование или очевидное расширение первой. Но на практике получается, что если существование конфигурации требует интенсивного исследования, то почти ничего нельзя сказать о соответствующей перечислительной задаче. С другой стороны, если перечислительная задача поддается решению, то соответствующая задача существования обычно решается тривиально.
Например, задача о покрытии шахматной доски костями домино. Рассматривается два случая: если квадраты на противоположных углах удалены и если – нет. В первом случаи – это невозможно, а во втором – возможно, причем многими способами.
Рассмотрим наиболее популярные и простые из них варианты решения комбинаторных задач.
1) Метод перебора различных вариантов:
a. когда конфигурации составляется из одинаковых элементов или из различных;
b. когда конфигурация содержат данный элемент ровно один раз, не более одного раза, хотя бы один раз, более одного раза;
c. когда порядок извлечения элементов будет существенным или несущественным при составлении конфигураций;
d. когда конфигурация образуется выбором элементов с возвращением или без возвращения.
2) Метод, основанный на правилах умножения и сложения.
3) Метод на основе формул для числа размещений, сочетаний, перестановок с повторением или без повторений.
Комментариев нет:
Отправить комментарий