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

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

Если объект а можно выбрать m способами, а объект b - k способами (не такими, как а), то выбор «либо а, либо b» можно осуществить m + k способами.

З а д а ч а 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?

Р е ш е н и е. По условию задачи яблоко можно выбрать пятью способами, апельсин - четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу суммы, можно осуществить 5 + 4 = 9 способами.

Правило нахождения числа элементов декартова произведения двух множеств (называют в комбинаторике правилом произведения и формулируют в таком виде:

Если объект а можно выбрать т способами, а объект b - k способами, то пару (а, b) можно выбрать m · k способами.

З а д а ч а 2. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина?

Р е ш е н и е. По условию задачи яблоко можно выбрать пятью способами, апельсин - четырьмя. Так как в задаче речь идет о выборе пары (яблоко, апельсин), то ее, согласно правилу произведения, можно выбрать 5 · 4 = 20 способами.

З а д а ч а 3. Сколько всего двузначных чисел можно составить из цифр 7, 4 и 5 при условии, что они в записи числа не повторяются?

Р е ш е н и е. Чтобы записать двузначное число, надо выбрать цифру десятков и цифру единиц. Согласно условию на месте десятков в записи числа может быть любая из цифр 7, 4 и 5. Другим словами, выбрать цифру десятков можно тремя способами. После того как цифра десятков определена, для выбора цифры единиц остается две возможности, поскольку цифры в записи числа не должны повторяться. Так как любое двузначное число- это упорядоченная пара, состоящая из цифры десятков и цифры единиц, то ее выбор, согласно правилу произведения, можно осуществить 3 · 2 = 6 способами.

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

З а д а ч а 4. Сколько трехзначных чисел можно составить, используя цифры 7, 4 и 5?

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

З а д а ч а 5. Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?

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

Итак, цифру тысяч можно выбрать одним способом, цифру сотен - двумя, цифру десятков - двумя, цифру единиц - двумя. Чтобы узнать, сколько всего четырехзначных чисел можно составить из цифр 0 и 3, согласно правилу произведения, способы выбора каждой цифры надо перемножить: 1 · 2 · 2- · 2 = 8.

Таким образом, имеем 8 четырехзначных чисел.

З а д а ч а 6. Сколько трехзначных чисел можно записать, используя цифры 0, 1,3,6,7 и 9, если каждая из них может быть использована в записи только один раз?

Р е ш е н и е. Так как запись числа не может начинаться с нуля, то цифру сотен можно выбрать пятью способами; выбор цифры десятков можно осуществить также пятью способами, поскольку цифры в записи числа не должны повторяться, а одна из шести данных цифр будет уже использована для записи сотен; после выбора двух цифр (для записи сотен и десятков) выбрать цифру единиц из данных шести можно четырьмя способами. Отсюда, по правилу произведения, получаем, что трехзначных чисел (из данных шести цифр) можно образовать 5 · 5 · 4 = 100 способами.