Конечных множеств

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

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

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

п(А´В) = п(А)^. п(В) = а ^. b.

Правило распространяется на случай t множеств, т.е. п(А₁ ´ А₂´... ´ А_t) = п(А₁)^. п(А₂)^.... ^. п(А_t).

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

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

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

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

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

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

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

*

Дата добавления: 2014-01-06