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

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

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

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

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

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

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

Задача 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 она будет иметь вид (рис. 25):

Эта схема действительно похожа на дерево, правда, растет оно вниз, и у него нет ствола. То, что дерево растет как бы «вверх ногами», удобно при построении схем такого вида.

Знак * изображает корень дерева, ветвями которого являются различные варианты решения задачи. Чтобы получить двузначное число, надо сначала выбрать цифру десятков - для этого есть три варианта: 5, 4 или 7. Поэтому из * проведены три отрезка и на их концах поставлены цифры 5, 4 и 7. Затем надо выбрать цифру единиц, а для этого также есть три варианта: 5, 4 или 7. Поэтому от цифр 5, 4 и 7 проведено по три отрезка, на концах которых опять стоят цифры 5, 4 или 7. Чтобы прочитать полученные варианты, надо пройти по всем ветвям построенного дерева сверху вниз.

Упражнения

1. Множество А содержит 7 элементов. Сколько элементов в множестве В, если декартово произведение А´ В состоит из: а) 42 элементов; б) 7 элементов; в) А ´ В = 0.

2. Сколько различных наборов можно составить из книги и блокнота, если имеется 20 видов различных книг и 15 видов различных блокнотов?

3. Решите нижеприведенные задачи методом перебора всех возможных вариантов, а затем покажите, что решение этих задач связано с определением числа элементов декартова произведения множеств:

а) В костюмерной танцевального кружка имеются белые и розовые кофты, а также синие, черные и коричневые юбки. Сколько можно из них составить различных костюмов?

б) Сколько трехзначных чисел можно составить, используя цифры

в) На вершину горы ведут две дороги. Сколькими способами можно подняться и спуститься с нее?

4. Решите следующие задачи, построив дерево возможных вариантов:

а) У продавца имеется три вида мороженого: клубничное, сливочное и ореховое. Наташа и Катя решили купить по одной порции. Сколько существует вариантов такой покупки?

б) В понедельник в первом классе должно быть три урока: математика, чтение и физкультура. Сколько различных вариантов расписания можно составить на этот день?

в) Туристическая фирма планирует посещение туристами в Италии трех городов: Венеции, Рима и Флоренции. Сколько существует вариантов такого маршрута?

Не нашли, что искали? Воспользуйтесь поиском: