WikiDer > Подписанный набор

В математике подписанный набор это набор элементов вместе с присвоением знак (положительный или отрицательный) к каждому элементу набора.

Представление

Знаковые множества могут быть представлены математически как упорядоченная пара из непересекающиеся множества, один набор для их положительных элементов и другой для их отрицательных элементов.^[1] В качестве альтернативы они могут быть представлены как Логическая функция, функция, домен которой является базовым беззнаковым набором (возможно, явно заданным как отдельная часть представления), а диапазон - двухэлементным набором, представляющим знаки.^[2][3]

Подписанные множества могут также называться ${ Displaystyle mathbb {Z} _ {2}}$-градуированные наборы.^[2]

Заявление

Знаковые множества являются фундаментальными для определения ориентированные матроиды.^[1]

Их также можно использовать для определения лица из гиперкуб. Если гиперкуб состоит из всех точек в Евклидово пространство данного измерения, чья Декартовы координаты находятся в интервале ${ displaystyle [-1, + 1]}$, то подписанное подмножество осей координат может использоваться для указания точек, координаты которых в подмножестве ${ displaystyle -1}$ или же ${ displaystyle +1}$ (согласно знаку в подписанном подмножестве) и чьи другие координаты могут быть где угодно в интервале ${ displaystyle [-1, + 1]}$. Это подмножество точек образует грань, коразмерность это мощность подписанного подмножества.^[4]

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

Перечисление

Количество подписанных подмножеств данного конечный набор из ${ displaystyle n}$ элементы ${ displaystyle 3 ^ {n}}$, а степень трех, потому что есть три варианта выбора для каждого элемента: он может отсутствовать в подмножестве, присутствовать с положительным знаком или присутствовать с отрицательным знаком.^[5] По той же причине количество подписанных подмножеств мощности ${ displaystyle r}$ является

${ displaystyle 2 ^ {r} { binom {n} {r}},}$

и их суммирование дает пример биномиальная теорема,

${ displaystyle sum _ {r} 2 ^ {r} { binom {n} {r}} = 3 ^ {n}.}$

Пересекающиеся семьи

Аналог Теорема Эрдеша – Ко – Радо. на пересекающихся семействах множеств верно и для множеств со знаком. Пересечение двух наборов со знаком определяется как набор элементов со знаком, которые принадлежат обоим и имеют одинаковый знак в обоих. Согласно этой теореме для любого набора подписанных подмножеств ${ displaystyle n}$- набор элементов, все имеют мощность ${ displaystyle r}$ и всех пар, имеющих непустое пересечение, количество подписанных подмножеств в коллекции не превышает

${ displaystyle 2 ^ {r-1} { binom {n-1} {r-1}}.}$

Например, пересекающееся семейство такого размера может быть получено путем выбора знака единственного фиксированного элемента и принятия в качестве семейства всех знаковых подмножеств мощности ${ displaystyle r}$ которые содержат этот элемент с этим знаком. За ${ Displaystyle г Leq п / 2}$ эта теорема немедленно следует из беззнаковой теоремы Эрдеша – Ко – Радо, поскольку беззнаковые версии подмножеств образуют пересекающееся семейство, и каждому беззнаковому набору может соответствовать не более ${ displaystyle 2 ^ {r-1}}$ подписанные наборы. Однако для больших значений ${ displaystyle r}$ требуется другое доказательство.^[3]

Рекомендации