Декартово произведение множеств. Объединение комбинаторных конфигураций

Тема 3. ОТНОШЕНИЯ НА МНОЖЕСТВАХ

Бином Ньютона

Объединение комбинаторных конфигураций

Комбинаторные числа не всегда определяются непосредственно по известным комбинаторным конфигурациям. Часто используются различные способы сведения одних комбинаторных комбинаций к другим. Простейший из этих способов – метод включений и исключений. В этом методе комбинаторная комбинация представляет собой объединение других комбинаторных конфигураций, число которых легко вычислить непосредственно. Таким образом, возникает задача вычисления числа комбинаторных конфигураций в объединении. В простейшем случае справедлива формула.

Доказательство. Используем круги Эйлера.

A

B

Здесь можно выделить три непересекающихся между собой области: 1), 2) и 3) тогда множества А, В и представляются в виде:

Указанные в этих объединениях множества не пересекаются, поэтому можно воспользоваться правилом суммы для определения их мощности, т.е.

Подставим из первых двух равенств в 3е, получим

В более сложном случае имеет место равенство

Доказательство.

Пример. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

Всего натуральных чисел меньших тысячи 999.Из них

1) делятся на 3

2) делятся на 5

3) делятся на 7

4) делятся на 3 и 5

5) 7 делятся на 3 и 7

6) делятся на 5 и 7

7) делятся на 3, на 5 и на 7

В результате имеем

Такое название получила формула

.

Из неё в частности получается:

Коэффициенты называются биномиальными. Биномиальные коэффициенты обладают рядом замечательных свойств: они являются целыми положительными числами, крайние из них равны единице, коэффициенты, равно- отстоящие от концов одинаковы, они возрастают от краёв к середине, сумма всех коэффициентов равна.Особенно важное свойство. Пользуясь этим свойством строится так называемый треугольник Паскаля, состоящий из биномиальных коэффициентов

n =0
n =1
n =2
n =3
n =4
n =5

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

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

Упорядоченной парой называется запись вида, где на первом месте расположен элемент а, принадлежащий некоторому множеству А, а на втором месте – элемент. В частном случае множества А и В могут совпадать.

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

.

Пример. Пусть и. Тогда:

;

.

Заметим, что при этом. Далее

.

Отметим, что если множества А и В конечны и, то.

Прямое произведение множеств может быть изображено графически. Для этого используется диаграмма Венна. В частности, для множества из предыдущего примера она имеет вид

	x
А
	y
					B

В качестве следующего примера рассмотрим произведение множества вещественных чисел R на самого на себя. Множество или состоит из всех упорядоченных пар вещественных чисел. Их можно представить себе как координаты точек на плоскости. Множество называется декартовой плоскостью.

Декартовым произведением произвольного числа множеств называется множество

.

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

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

Пример. Пусть. Тогда множество состоит из всевозможных последовательностей нулей и единиц длины n. Такая последовательность называется булевым вектором (битовой строкой или строкой бит) длины n. Совокупность всех булевых векторов размерности n называется булевым кубом размерностью.

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