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

Нам известно, как находят декартово произведение конечных множеств. Например, если А = {х, у, 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.

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

12. Основные понятия:

Множество, элемент множества, характеристическое свойство элементов множества, подмножество, равные множества, пересечение множеств, объединение множеств, вычитание множеств, дополнение подмножества, декартово произведение множеств.