Транзитивные замыкания отношений

Графическое представление операций композиций матриц

Дэнумераторы размещения.

Производящие функции.

Комбинаторика.

Общие правила комбинаторики.

1) Правило суммы: если искомый объект а можно выбрать m - способами, а объект b n – способами, то выбор либо а, либо b можно сделать m + n –способами.

2) Правило произведения: если объект а можно выбрать n – способами, и, если после каждого такого выбора объект b будет выбираться m – способами, то (аb) m*n.

I) Задача размещения: размещением из n элементов по к называется к - расстановка, состоящая из n различных предметов.

А_n^k = n!\(n – k)!

II) Будем рассматривать размещение без повторов из n различных элементов. Но в каждое размещение будет включаться n – элемент. Такие расстановки, отличающиеся порядком, называются n – перестановками. Р_n = n!, n = 0, P_n = 1.

III) Задача сочетания: к сочетаниям из n элементов называется всевозможные к – расстановки, состоящие из этих элементов и отличающиеся друг от друга составом, но не порядком.

=

Сочетания без повторений и их свойства.

1) Формула сочетаний

=

2) = +

3) ⁿ

4) ^k = 0

Пусть есть некоторая последовательность элементов а₀, а₁, а₂ … а_n. Элементы последовательности упорядочены, но не обязательно различны. Производящей функцией для последовательности будет:

А(t) = а₀ + а₁t + а₂t² + а₃t³ + … ①

Экспоненциальной производящей функцией будет:

А(t) = а₀ + а₁t + а₂t²\2! + а₃t³\3! + … ②

В общем виде представим функцию:

G(t) = а₀f(t) + а₁f₁(t) + … ③

Единственное требование, образующее функцию ③, является её линейная независимость.

Для получения дэнумератора размещения воспользуемся соотношениями:

= \k!

d_n(t) = (1 + t)ⁿ = t^k = t^k\k!

Получим экспоненциальную производящую функцию, её коэффициенты представляют собой размещения из n по k. Составим производящую функцию для размещения без повторений:

d_n(t) = ^kt^k\n!, n^k – число размещений без повторений.

Матрицу соотношений можно представить в ином виде – строкам ставится в соответствии В, а столбцам А, то есть матрица транспонируется.

RÌ A × B

SÌ B×C

M(S) = [ ]

А соответствия определяются

Если отношение R и S представляются графически, то и графически изображения изображаются на одном чертеже.

Построим отношение Ì A x c

Можно упростить схему следующим образом

На этом чертеже соединены стрелками те элементы и которые, уже на построенном графике, соединены путем двух стрелок, причем первая стрелка сплошная, а вторая нет.

Это операция выполняется над отношениями подмножеств. Транзитивным замыканием отношений R называется отношение, которая выполняется для элементов (x,y), причем x, y Ì A, в том и только в том случае, если существует цепочка элементов.

Тогда существует операция:

Если, то такая цепочка существует и (эквивалентны), отсюда следует, что R и R (с крышкой), и вообще <->, причем n, n – композиция отношений.

Используется операция объединения замыканием. Транзитивное замыкание отношения R равно объединению всех степеней этого R (с крышкой) = отношения

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