Прямое произведение множеств

Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов х и у, расположенных в определенном порядке. Две пары <x, y>, <u, v> считаются равными тогда и только тогда, когда x=u, y=v.

Упорядоченная n-ка элементов х1, …, хn обозначается <x1, …, xn>.

Определение. Прямым произведением множеств X и Y называется множество , элементами которого являются все возможные упорядоченные пары <x, y>, такие, что .

Определение. Прямым произведением множеств Х1, Х2, …, Хn называется совокупность всех упорядоченных n-ок <x1, …, xn> таких, что . Если Х1=Х2=…Хn, то пишут .

Пример 7.

1. Пусть X={1, 2, 3}, Y={0, 1}. Тогда ; .

2. Пусть Х – множество точек отрезка [0, 1], а Y – множество точек отрезка [1, 2]. Тогда - множество точек квадрата с вершинами в точках (0, 1), (0, 2), (1, 1), (1,2).

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

Например. Пусть А = { а1, а2 }, В = { в1, в2, в3 }. Тогда

А В = { (а1, в1), (а1,в2), (а1,в3), (а2,в1), (а2,в2), (а2, в3) }.

Определение. Пусть Х – конечное множество. Декартовы степени множества Х определяются формулами

Х = Х, Х = Х Х, …, Х = Х Х.

Определение. Пусть А и В непустые множества. Обозначим через В - множество отображений, действующих из А в В, т.е. f В ” f: А ’ В. Множество В называется множеством степень.

Для конечных множеств справедливы следующие правила.

Правило суммы. Если | А | = n, | В | = m, то | А В | = n+ m - | А) В |,

и | А В | = m+ n в том и только в том случае, когда А) В = Ш.

Правило произведения. Если | А | = n, | B | = m, то | А В | = n· m.

Правило степени. Если | А | = n, | В | = m, то | А | = n .

Если Х – конечное множество, то

|Х | = | Х | .

Правило включения-исключения. Пусть Х ,…, Х – конечные множества, тогда справедлива формула

| Х Х … Х | = (| Х | + … + | Х |) – (| Х ) Х | + | Х ) Х | + … +

+ | Х ) Х |) + (| Х ) Х ) Х | + … + | Х ) Х ) Х |) + … +

+ (-1) | Х ) Х )…)Х |

Замечание. Правило суммы является следствием этой формулы.

Основной принцип комбинаторики.

Если А ~ В, то | А | = | В |. Этот принцип является главным рабочим инструментом комбинаторики, т.е. он позволяет переносить изучение свойств с одного множества на другое, когда природа элементов не важна. Например, если | А | = n, то с элементами множества А можно работать как с числами 0, 1, …, n-1.

Задача. Из города А в город В ведет три дороги, а из города В в город С – четыре. Сколькими способами можно добраться из города А в город С через город В?

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

| АВ ВС | = | АВ | · | ВС | = 3 · 4 = 12.

Задача. Из города А в город В ведет три дороги, из города В в город С – четыре. Из А в С есть пять дорог, не проходящих через В. Сколькими способами можно попасть из А в С?

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

| АВС | + | АС | = 12 + 5 = 17.

Задача Сколько существует способов разослать семь писем в различные организации, если доставка осуществляется четырьмя курьерами?

Обозначим через К и П – множество курьеров и множество писем. Каждый способ доставки определяется указанием для каждого письма, какой из курьеров его доставляет, т.е. способ доставки это отображение множества писем во множество курьеров.

Тогда число способов доставки писем определяется по правилу степени и будет

равно

| К | = | К | = 4 = 16 384.

Задача. В кабину лифта девятиэтажного дома вошло три пассажира. Каждый из пассажиров может выйти на любом из восьми этажей. Сколькими способами может осуществиться разгрузка лифта.

Обозначим через П и Э множество пассажиров и множество этажей. Способ разгрузки лифта – это указание, на каком этаже выходит конкретный пассажир, т.е. сопоставление пассажиру этажа, на котором он выходит. Тогда число способов разгрузки лифта определяется по правилу степени и будет равно

| Э | = | Э | = 8 = 512.