Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество данного n-элементного множества.

Формула числа сочетаний

(по определению считают, что

Пример:

Из 25 учащихся одного класса можно выделить пятерых для дежурства по школе способами, то есть способами.

Некоторые свойства числа сочетаний без повторений

(в частности, )

Схема поиска плана решения простейших комбинаторных задач:

Выбор правила:

Правило суммы

Если элемент А можно выбрать т способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами.

Правило произведения

Если элемент А можно выбрать m способами, а после этого элемент В — n способами, то А и В можно выбрать способами.

Объяснение и обоснование:

Понятие соединения. Правило суммы и произведения:

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

Выбранные (или выбранные и размещенные) группы элементов называют соединениями. Если все элементы полученного множества разные, получаем размещения без повторений, а если элементы могут повторяться — размещения с повторениями. В этом параграфе мы рассмотрим соединения без повторений.

Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения.

Правило суммы. Если на тарелке лежат 5 груш и 4 яблока, то выбрать один фрукт (грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде справедливо такое утверждение:

• если элемент А можно выбрать m способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами.

Уточним содержание этого правила, используя понятие множеств и операций над ними.

Пусть множество А состоит из m элементов, а множество В -из n элементов. Если множества А и В не пересекаются (то есть ), то множество А В состоит из элементов.

Правило произведения. Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5æ4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение:

• если элемент А можно выбрать m способами, а после этого элемент В — n способами, то А и В можно выбрать способами.

Это утверждение означает, что если для каждого из m элементов А можно взять в пару любой из n элементов В, то количество пар равно произведению .

В терминах множеств полученный результат можно сформулировать следующим образом. Если множество А состоит из т элементов, а множество В — из n элементов, то множество всех упорядоченных пар* (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй  множеству В (b ∈ В), состоит из элементов.

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

Упорядоченные множества:

При решении комбинаторных задач приходится рассматривать не только множества, в которых элементы можно записывать в любом порядке, но и так называемые упорядоченные множества. Для упорядоченных множеств существенным является порядок следования их элементов, то есть то, какой элемент записан на первом месте, какой на втором и т. д. В частности, если одни и те же элементы записать в разном порядке, то мы получим различные упорядоченные множества. Чтобы различить записи упорядоченного и неупорядоченного множеств, элементы упорядоченного множества часто записывают в круглых скобках, например (1; 2; 3) ≠ (1; 3; 2).

Рассматривая упорядоченные множества, следует учитывать, что одно и то же множество можно упорядочить по-разному. Например, множество из трех чисел {–5; 1; 3} можно упорядочить по возрастанию: (–5; 1; 3), по убыванию: (3; 1; –5), по возрастанию абсолютной величины числа: (1; 3; –5) и т. д.

* Множество всех упорядоченных пар (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй - множеству В (b ∈ В), называют декартовым произведением множеств А и В и обозначают А × В. Отметим, что декартово произведение В × А также состоит из m*n элементов.

Заметим следующее: для того чтобы задать конечное упорядоченное множество из n элементов, достаточно указать, какой элемент находится на первом месте, какой на втором,..., какой на n-м.

Размещения: