Перестановки. Бинарные отношения.

В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.

Число всех перестановок порядка n равно числу размещений из n по n, т.е. факториалу:

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

Бинарные отношения могут обладать различными свойствами, такими как

Рефлексивность: .

Антирефлексивность (иррефлексивность): .

Симметричность: .

Антисимметричность: .

Транзитивность: .

Связность: .

Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

Виды отношений

Рефлексивное транзитивное отношение называется отношением квазипорядка.

Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

Полное антисимметричное транзитивное отношение называется отношением линейного порядка.

Антирефлексивное асимметричное отношение называется отношением доминирования.