Число элементов в декартовом произведении конечных множеств

Нам известно, как находят декартово произведение конечных множеств. Например, если, А = {х, у, z}, а В = {m, p}, то, А х В = {(х, m), (х, р), (у, m), (у, р), (z, m), (z, р)}. Чтобы ответить на вопрос: «Сколько элементов в полученном множестве?», достаточно пересчитать их. А как определить число элементов в декартовом произведении множеств, не образуя его и не обращаясь к пересчету элементов?

Можно доказать, что если в множестве, А содержится, а элементов, а в множестве В — b элементов, то в декартовом произведении множеств, А и В содержится а* bэлементов, т. е.

n (А х В) = n (А) * n (В) = а * b. (3).

Правило распространяется на случай t множеств, т. е.

n (Ах, А х… х Аt) =n (А)*n (А) *…*n (Аt).

Например, если в множестве, А содержится 3 элемента, в множестве В — 4 элемента, в множестве С — 5 элементов, то в их декартовом произведении будет содержаться 3*4*5 = 60 упорядоченных наборов из трех элементов.

Полученные формулы можно использовать при решении задач.

Задача 1. У Маши 3 различных юбки и 4 различных кофты. Сколько различных комплектов, состоящих из юбки и кофты, она может составить?

Решение. Пусть, А — множество юбок у Маши, В — множество кофт. Тогда, по условию задачи, n (А) = 3, n (В) = 4. Требуется найти число возможных пар, образованных из элементов множества, А и В, т. е.n (А х В). Но согласно правилу n (А х В) =n (А)*n (В) = 3 * 4 = 12. Таким образом, из 3 юбок и 4 кофт Маша может составить 12 различных комплектов.

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

Решение. Запись любого двузначного числа состоит из двух цифр и представляет собой упорядоченную пару. В данном случае эти пары образуются из элементов множества, А = {5, 4, 7}. В задаче требуется узнать число таких пар, т. е число элементов в декартовом произведении, А х А. Согласно правилу n (А х А) =n (А)*n (А) = 3 * 3 = 9. Значит, двузначных чисел, записанных с помощью цифр 5, 4 и 7, будет 9.

Часто при решении задач, аналогичных рассмотренным выше, требуется не только ответить на вопрос о том, сколько существует возможных вариантов ее решения, но и осуществить перебор этих вариантов. Например, в задаче 2 можно предложить записать все двузначные числа, используя цифры 4, 5 и 7.

Существует единый подход к осуществлению такого перебора — строится схема, называемая деревом возможных вариантов. Она будет иметь вид:

Рис. 3.