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

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

Множества, составленные из каких либо элементов, называются комбинациями (соединениями).

Комбинации можно составить из элементов, безразлично какой природы, заданного конечного множества.

Пример 1. Сколько различных комбинаций по 2 буквы можно составить из 5 букв русского алфавита: А, Б, В, Г, Д?

Решение. Комбинации можно получить следующим образом: взять любую букву из названных (например, букву А) и приписать к ней еще одну букву. В результате получится пять двухсимвольных последовательностей: АА, АБ, АВ, АГ, АД. Но т. к. для рассмотрения было предложено 5 букв, то для каждой из них также получится 5 комбинаций. Всего получится 5´5=25 комбинаций.А если взять большее число символов в каждой комбинации (например, 3 или 4), то число комбинаций будет равно 5´5´5=125 и 5´5´5´5=625 соответственно.

Рассмотренный пример относится к задачам типа размещения с повторениями. Под повторениями в рассматриваемом примере понимаются комбинации, в которых символы одинаковые: АА, ББ, ВВ, ГГ, ДД.

Пример 2.

Для проведения экзамена создается комиссия из двух преподавателей. Сколько различных комиссий можно составить из 5 преподавателей?

Решение.

Обозначим преподавателей буквами A, B, C, D, Е. Тогда нетрудно записать все возможные комбинации для состава комиссий:

AB, AC, AD, АЕ, BC, BD, ВЕ, CD, СЕ, DE.

Таким образом, всего возможно составить 10 комиссий.

Но если бы и в первом и втором примерах шла речь о составлении различных комбинаций из большего числа объектов, то решить такие задачи простым перебором практически невозможно.

Для решения подобного рода задач применяются специальные формулы. Но прежде, чем рассмотреть эти формулы, выясним: что общего у этих примеров и в чем существует разница между ними.

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

Наряду с этим сходством в данных примерах выделяется и существенное отличие. Оно заключается в том, что в этих примерах совершенно по-разному понимаются слова «различные подмножества».

В первом примере порядок элементов важен, а во втором примере – нет. Так же в первом примере рассматриваются подмножества, состоящие из одинаковых элементов, т. е. комбинации с повторениями. Во втором примере такие комбинации невозможны.

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

ПРАВИЛА КОМБИНАТОРИКИ.

Пусть А_i (i=1,2,…n) – элементы конечного множества. Сформулируем два важных правила, часто применяемых при решении комбинаторных задач:

1)  Правило суммы.

Если элемент может быть выбран способами, элемент  – другими  способами,  – отличными от первых двух  способами и т. д.,  –  способами, отличными от первых (k-1), то выбор одного из элементов: или, или , …, или  может быть осуществлен способами.

Пример. Сколькими способами можно выбрать одну четную или одну нечетную цифру из числа 1234569?

Решение. Четную цифру можно выбрать тремя способами (2, 4, 6), нечетную можно выбрать четырьмя способами (1, 3, 5, 9). Следовательно, четную или нечетную цифру можно выбрать 3+4=7 способами