Упорядоченной последовательностью элементов (кортежем) называют строку символов, в которой каждому символу отведено фиксированное место. Число символов последовательности называется ее длиной. Примерами кортежей являются телефонные номера, государственные номера автомашин, номера команд микропроцессора. Из этих примеров следует, что элементами кортежа могут быть элементы разных множеств. Например, автомобильные номера содержат арабские цифры и буквы, являющиеся элементами пересечения латинского и русского алфавита. Для множеств определена операция, порождающая такого рода элементы. Эта операция называется прямым или декартовым произведением множеств.
Декартовым произведением n множеств А1, А2, ..., А n называется множество, элементами которого являются упорядоченные последовательности элементов длины n ( a1, a2, ..., an) (называемые также кортежами длины n), в каждой из которых присутствует ровно один элемент каждого из перемножаемых множеств, а порядок их расположения в кортеже соответствует порядку следования перемножаемых множеств..
Примерами таких кортежей являются элементы булеана конечного множества, заданные с применением характеристической функции.
Декартово произведение обозначается следующим образом:
А1 ´ А2 ´ ... ´ Аn= {(a1,a2, ... , an)| a1 ÎA1, a2 Î A2, ... , an Î Аn)}.
Декартово произведение множества А на себя n раз называется n-ой декартовой степенью множества А., обозначается Аn. Например, если R - множество действительных чисел, то R2 - множество точек действительной плоскости.
Если n=0, то по определению А0=Æ.
Декартово произведение не коммутативно. Например, если А={1, 2}, B={a, b}, то
А ´ В ={(1,a), (1,b), (2,a), (2,b)}, а B ´ A = {(a,1), (a,2), (b,1), (b,2)}.
Основное свойство упорядоченных последовательностей длины n (упорядоченных n-ок) состоит в том, что они равны тогда и только тогда, когда их одноименные элементы равны между собой. Например, ( a1, a2 , ..., an)=( b1, b2, ..., bn) тогда и только тогда, когда a1= b1, a2= b2, ..., an= bn.
Упорядоченные двойки называются парами, тройки - тройками и т.д.
Упорядоченные множества, элементами которых являются вещественные числа, называются точками пространства или векторами. В этом смысле можно говорить о проекции точек на координатные оси. Проекция упорядоченной n-ки на i-ю координату определяется следующим образом:
Прi(a1, a2, ..., an) = ai.
Проекция упорядоченной последовательности более, чем на одну координату есть вектор. Например,
Прi,j,k( a1, a2, ..., an)= (ai, aj, ak).
Проекция кортежа на пустое множество координат называется пустым кортежем и обозначается
Пр Æ (а1, a2, ..., an) = L.
Кортеж длины n будем обозначать а(n) .
Если элементами множества являются кортежи фиксированной длины, то к такому множеству может быть применена операция проектирования. При этом проекция множества кортежей одинаковой длины на одну или более координат есть множество проекций кортежей исходного множества на эти координаты. Например, если М ={(1,2,3,4), (2,4,1,3), (3,2,4,5)}, то проекции этого множества на одну и две координаты имеют вид:
ПР3M = {3,1,4}, ПР 1,3M = {(1,3), (2,1), (3,4)}.
Если М=А х В, то ПР 1М = А, ПР2М = В.
Если М Í А х В, то ПР1М Í А, ПР2М Í В.
Свойства декартова произведения:
(М1 È М2) х М3 = (М1 х М3) È (М2х М3),
(М1 Ç М2) х М3 = (М1 х М3) Ç (М2х М3),
(М1\М2) х М3 = (М1 х М3) \ (М2 х М3),
(Т1 х М2) Ç (М1 х Т2) = Т1 х Т2, если Ti Í Мi.
Если в произведении один из сомножителей есть пустое множество, то произведение по определению пусто.
Элементы комбинаторики
Спросил меня Голос в пустыне дикой:
-Сколько в море растет земляники?
-Столько же, сколько селедок соленых
Растет на березах и елках зеленых.
Комбинаторика - это теория конечных множеств. Предметом комбинаторики является подсчет мощностей некоторых конечных множеств, элементы которых получены по определенным правилам из элементов других конечных множеств. Мы рассмотрим несколько задач, имеющих различные приложения в разных областях математики.
Основным методом комбинаторики является метод математической индукции. Он состоит в следующем:
Если некоторое свойство, заданное на множестве целых неотрицательных чисел, справедливо для 1, и если, каково бы ни было целое положительное число n, из справедливости этого свойства для n вытекает справедливость его для n+1, то это свойство справедливо для всех положительных целых чисел.
Иначе, если В(х) - одноместный предикат, определенный на множестве целых положительных чисел, то приведенное выше определение можно переписать следующим образом:
.
Чтобы доказать методом математической индукции некоторое свойство, необходимо
1. Доказать справедливость этого свойства для единицы.
2. Для произвольного n доказать справедливость индукционного вывода:
.
3. Если это удается сделать, то доказываемое утверждение справедливо.
Такое доказательство называется доказательством по индукции. Его первая часть называется базисом индукции, вторая - индукционным шагом. При проведении индукционного шага посылку импликации, т.е. предложение B(n) называют предположением индукции, а B( n+1) –индукционным заключением.
Основными правилами, используемыми в методе математической индукции, являются правило умножения и правило сложения.
Нередко метод индукции используется не для доказательства свойств целых чисел, а при рассмотрении каких-либо других объектов, занумерованных этими числами. Именно так он будет использоваться в комбинаторных задачах, к рассмотрению которых мы переходим.
Комбинаторными соединениями называются слова конечной длины, составленные из букв конечного алфавита по заранее определенным правилам. Рассмотрим некоторые из них и правила подсчета их числа.
РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ
Размещениями с повторением из n элементов по m называются комбинаторные соединения, представляющие собой слова длины m в алфавите объемом n, различающиеся либо самими буквами, либо их порядком.
Пусть А = {a1, a2, ..., an) - конечный алфавит, состоящий из n букв, и пусть 
- число слов в алфавите А, имеющих длину m, буквы в которых могут повторяться. Например, возможно слово а1(m), т.е. содержащее одну единственную букву. Возможны любые произвольные сочетания, включающие вхождения некоторых букв произвольное число раз и в произвольном порядке.
Теорема Число размещений с повторениями длины m в алфавите объемом n равно 
= nm.
Доказательство: Можно дать еще одно определение этому комбинаторному соединению: это все элементы декартовой n-й степени алфавита: , 
. Докажем теорему методом математической индукции по m.
1. Базис: При m =1 число Q(1) различных слов, которые могут быть образованы в алфавите А, равно его мощности, т.е. n. Следовательно, Q(1)= 
= n1=n. Базис индукции доказан.
2. Индукционное предположение: пусть для некоторого m доказано, что Q(m)= = nm. Определим число слов в длины m+1 при этом предположении. Все слова длины m+1 можно получить, приписывая справа к каждому слову длины m какую-нибудь букву алфавита. Очевидно, каждое слово длины m можно дополнить n способами, т.е. общее число слов длины m+1 окажется в n раз больше числа слов длины m. Следовательно, Q(m+1)=Q(m)*n= n*nm=nm+1= 
.
Доказательство окончено.
РАЗМЕЩЕНИЯ БЕЗ ПОВТОРЕНИЙ
Это комбинаторные соединения, представляющие собой слова длины m в алфавите объемом n, различающиеся составом букв или их порядком, в каждое из которых любая буква может войти не более одного раза.
Теорема: Число размещений без повторения длины m в алфавите объемом n равно 
.
Доказательство: Докажем теорему методом математической индукции по m.
1. Базис: При m=1 число Q(1) различных бесповторных слов в алфавите А равно его мощности, т.е. n. Подставляя m=1 в условие теоремы, получим n!/(n-1)!=n. Таким образом, базис индукции справедлив.
2. Индукционное предположение: пусть при некотором m число размещений без повторений Q(m) = 
. Определим число слов длины m+1, являющихся размещениями без повторений. Все такие слова можно получить, приписывая к каждому слову длины m одну из неиспользованных в слове букв алфавита А. Следовательно, каждое слово длины m порождает n-m слов длины m+1. Следовательно, число Q(m+1) слов длины m+1 равно
Q(m)*(n-m)= 
(n-m)= 
.
Теорема доказана. Разумеется, это доказательство имеет смысл только в случае, когда n > m.
ПЕРЕСТАНОВКИ
Это слова длины n в алфавите объемом n, в которых одна и та же буква не может повторяться. Т.е. это размещения без повторений из n по n. Число перестановок обозначается Рn.
Теорема: Pn = n!
Доказательство автоматически следует из выражения для числа размещений без повторений. По определению 0!=1.
СОЧЕТАНИЯ ИЗ n ЭЛЕМЕНТОВ ПО m Это слова длины m в алфавите объемом n, различающиеся составом букв, но не их порядком, причем буквы в словах могут появляться не более одного раза. Число таких соединений обозначается как 
Теорема: 
Доказательство. В соответствии с определением, сочетания есть размещения без повторений из n элементов по m, в которых слова с одинаковыми наборами букв являются одним и тем же словом сочетаний. Поэтому их число может быть определено как
Q(m)= 
.
Следствия
1. 
- следует из определения.
2. 
- так как все пустые слова одинаковы.
3. 
ª Возможно следующее доказательство этого свойства. Известно, что
где 
это биномиальные коэффициенты, определяющие число слагаемых вида xiyn - i в сумме. В частном случае, когда х=1 и у=1 получаем непосредственно
требуемое выражение 
§
4. 
ª Доказывается аналогично доказательству свойства 3 в предположении, что х=1, у=-1. §
Задача: Доказать что мощность булеана конечного множества А равна 2|A|.
ª Мощность булеана конечного n- элементного множества есть число всех его подмножеств. Ранее мы без доказательства ввели утверждение, что |P(A)| = 2|A|. Так как 
есть не что иное, как число m-элементных подмножеств n-элементного множества, то указанная сумма действительно определяет число всех возможных подмножеств конечного множества.
Треугольник Паскаля
Рассмотрим рекуррентную по n процедуру определения биномиальных коэффициентов, т.е. определение 
если известно 
Пусть число r- элементных подмножеств (n+1)-элементного множества равно и известно, как определить И пусть |А | = n и мощность множества А È {a0} равна n + 1.Тогда r- элементные подмножества множества А È {a0} будут состоять из подмножеств двух типов: тех, которые не содержат элемент а0, число их будет равно 
, и тех, которые содержат элемент а0. Последние можно получить, взяв все (r-1) - элементные подмножества множества А, и добавив к каждому из них а0. Тогда число r - элементных подмножеств (n + 1)-элементного множества определится, как 
Это рекуррентное соотношение используется для построения таблицы биномиальных коэффициентов, в которой коэффициенты расположены рядами друг над другом. Строки следуют в порядке возрастания n, а позиция коэффициента в ряду указывает число m подмножеств ранга 0,1,2,…,n, причем 0 £ m £ n, 0 £ n £ N.
Таблица биномиальных коэффициентов приводится в математических справочниках и имеет вид, представленный на Рис. 1.
Рисунок 1 Треугольник Паскаля
Дата: 2019-03-05, просмотров: 295.
