ВОПРОС 4 (2)

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

Правило суммы: пусть имеется n попарно непересекающихся множеств A₁, A₂, …, A_n, содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно m₁ + m₂ + … + m_n.

Пример. Если на первой полке стоит X книг, а на второй Y, то выбрать книгу с первой или второй полки, можно X+Y способами.

Пример. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: По правилу суммы получаем 17+13=30 вариантов.

Кортеж - конечная последовательность (допускающая повторения) элементов какого-нибудь множества.

Правило произведения: пусть имеется n множеств A ₁, A ₂, …, A _n содержащих m ₁, m ₂, …, m _n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а₁, а₂,..., а_n), где а _i  А _i1 (i = 1, 2, …, n), равно m₁ · m₂ · … · m_n.

Пример. Если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Пример. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение. Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Выборки. Если из множества предметов выбирается некоторое подмножество, то его называют выборкой. Выборки бывают упорядоченные и неупорядоченные.

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

Пример. Из цифр 1, 2, 3, 4, 5 можно составить следующие трехзначные числа 123, 431, 524,...и т.д. Это упорядоченные трехэлементные выборки, так как 123 и 132 - разные числа.

Пример. Из 20 учащихся класса выбрать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.