서명된 집합

수학에서 부호 집합은 집합의 각 원소에 부호(양 또는 음)를 할당하는 것과 함께 원소 집합이다.

표현

부호화된 집합은 순서가 지정된 쌍의 분리 집합으로 수학적으로 표현될 수 있으며, 하나는 양의 원소를 위한 것이고 다른 하나는 음의 원소를 위한 것이다.^[1]또는 부울 함수로 나타낼 수 있는데, 부울 함수는 도메인이 기본 미서명 집합이고(아마도 표현의 별도 부분으로 명시적으로 지정됨) 범위는 부호를 나타내는 2요소 집합이다.^[2][3]

서명된 세트는 $Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ -graded$$ 세트라고도 할 수 있다.^[2]

적용

서명된 세트는 지향성 매트로이드의 정의에 기초한다.^[1]

그것들은 또한 하이퍼큐브의 얼굴을 정의하는 데 사용될 수 있다.하이퍼큐브가 데카르트 좌표가 [${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle }$+ $1$ 간격인 특정 치수의 유클리드 공간에 있는 모든 점으로 구성된 경우, 좌표 축의 서명된 부분 집합을 사용하여 부분 집합 내의 좌표가${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle -1}$ 또는$$${\displaystyle }$+ ${\displaystyle 1}$ ${\displaysty$}인 점을 지정할 수 있다$.$$le$+1}($$서명된 부분 집합의 기호에 따름) 및 그 다른 좌표는${\displaystyle }$[${\displaystyle }$- 1,${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [-1,+1]}$ 간격의 어느 곳에 있을 수 있다$.$이 점의 부분집합은 얼굴을 형성하며, 그 부분집합은 서명된 부분집합의 카디널리티이다.^[4]

콤비네이터틱스

열거

$주어진{\displaystyle }$ n ${\displaystyle n}$ 요소의$$ 유한 집합의 부호화된 하위 집합 수는 ${\displaystyle {3n}^{}}$ ${\$의 세 가지 선택이 있기 때문에 3의 힘이다$.$^[5]동일한 이유로 카디널리티 $r{\displaystyle }$ ${\displaystyle r}$의 서명된 하위 집합 수는$$

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

그리고 이것들을 요약하면 이항 정리의 예를 들 수 있다.

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

교차 패밀리

집합의 교차 패밀리에 대한 Erdős-Ko-Rado 정리의 아날로그도 부호화된 집합에 적용된다.두 개의 서명된 집합의 교차점은 둘 다에 속하고 둘 다에 동일한 기호를 갖는 서명된 요소 집합으로 정의된다.이 정리에 따르면, $n{\displaystyle }$ ${\displaystyle n}$ -element$$ 집합의 서명된 하위 집합 집합 모음, 모두 카디널리티 $r{\displaystyle }$ ${\displaystyle r}$ 및 모든$$ 쌍이 비어 있지 않은 교차점을 갖는 경우, 집합에서 서명된 하위 집합의 수는 최대값이다.

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

예를 들어, 이 크기의 교차 패밀리는 단일 고정 요소의 기호를 선택하고 패밀리를 이 기호와 함께 이 요소를 포함하는$$ $카디널리티{\displaystyle }$ r ${\displaystyle r$}의 모든 서명 하위 집합으로 지정함으로써 얻을 수 있다.$r{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle n\mathrm{}}$/ 2 ${\displaystyle r\leq n/2}$의 경우 이$$ 정리는 부호 없는 버전의 하위 집합이 교차 패밀리를 형성하고 각 부호 없는 $집합$이 ${\displaystyle {\mathrm{최대}}^{}}$2 r -$$1 {\$displaystyle$2^{$r-1}$ 서명된 집합에 해당할 수 있으므로 부호 없는 Erds-Ko-Rado 정리에서 즉시 따르게 된다.그러나 $r{\displaystyle }$ ${\displaystyle r}$의 큰 값에 대해서는 다른$$ 증거가 필요하다.^[3]

참조