Принцип разбиения множеств

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

Пример 2.2.5. Для того чтобы записаться на курс программирования в весеннем семестре, студент должен выбрать два курса из Comp240, Comp225 и Comp326. Имеется шесть вариантов курса Comp240, семь вариантов курса Comp225 и пять вариантов курса Comp326. Сколько есть различных способов записаться на курс программирования. Считайте, что допустимы любые сочетания курсов.

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

Подзадача 1: Выбраны Comp240 и Comp225:

Подзадача 2: Выбраны Comp240 и Comp326:

Подзадача 1: Выбраны Comp225 и Comp326:

Окончательный ответ

=

=42+30+35=107.

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

Подсчет элементов дополнения

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

Пример 2.2.6. Сколько есть трехбуквенных слов, в которых какая-нибудь буква повторяется, если для формирования слов используются буквы из множества ?

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

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

(# слов с повторяющимися буквами) = (# всех слов)

# слов с повторяющимися буквами)

= =65.

Пример 2.2.7. Сколько трехзначных чисел начинается с 3 или 4?

Для решения этой задачи приходится использовать, как правило, суммы так и правило произведения. Трехзначные числа, о которых идет речь в задаче, естественным образом разбиваются на два непересекающихся множества. К одному из них относятся числа, начинающиеся с 3, а ко второму – с 4. Для подсчета чисел в первом множестве заметим, что существует один возможный исход для первой цифры (она должна быть равна 3), 10 исходов для второй и 10 исходов для последней цифры. По правилу произведения получаем, что всего чисел в первом множестве насчитывается . Аналогично можно подсчитать количество чисел второго множества. Оно тоже равно 100. Наконец, по правилу суммы получаем, что существует 100+100=200 трехзначных чисел, начинающихся с 3 или 4.

Пример 2.2.8. Государственный регистрационный знак легкового автомобиля состоит из трех цифр и трех букв русского алфавита (не считая кода города). Будем считать, что в номере можно задействовать любую последовательность букв и цифр. Сколько различных автомобильных номеров может выдать ГИБДД?

Решение. Каждую из трех букв номера можно выбрать из 33 букв алфавита. По правилу произведения число различных последовательностей из трех букв равно

Аналогично, число последовательностей трех цифр равно

Наконец, поскольку каждый из автомобильных номеров состоит из трех цифр и трех букв, правило произведения дает искомый ответ: 35937000 различных номеров может выдать ГИБДД.