5.1. 특성 함수
함수는 관계의 특별한 경우입니다. 정의역과 공역이 관계를 가지고,
하나의 정의역이 하나의(공역의 원소)치역을 가지는 관계를 일반적으로 함수로 정의합니다.
함수의 정의는 해석학에서 엄밀하게 정의되어 있으므로
이번 장에서는 이산의 성질을 가지는 특성 함수와 순열에 대해 배워봅시다.
주어진 전체 집합 U를 정의할 때, A \subset U 이면,
f_A(x) = \left{ 1, x \in A \\ 0, x \not\in A 인 f_A를 정의 가능하고,
이 함수를 “특성 함수”(Characteristic Function)라고 정의합니다.
유명한 “디리클레 함수”(Dirichlet function)는 U가 실수 집합 ℝ 이고, A가 유리수 집합 ℚ인 특성 함수입니다.
x \in ℝ 에 대하여 x보다 크거나 같은 정수 값 중 가장 작은 정수 값을 ⌈x⌉로 표현 가능 하고,
이를 “천장함수”(Ceiling Function)라고 정의합니다.
x \in ℝ 에 대하여 x보다 작거나 같은 정수 값 중 가장 정수 값을 ⌊x⌋로 표현 가능 하고,
이를 “바닥함수”(Floor Function)라고 정의합니다.
5.2. 순열
집합 A가 정의 될 때, A에서 A로 가는 전단사 함수를 A의 “순열”(Permutation)이라고 표현합니다.
집합 A = {a_1, a_2, \ldots, a_n} 에서 집합 A = {a_1, a_2, \ldots, a_n}로 가는 하나의 전단사 함수 p(a_i) \in A가
p에 의해 a_i \in A에 대응되는 값이라고 한다면, p는 다음과 같이 표현 할 수 있습니다.
p = \left( a_1 & a_2 & \cdots & a_n \\ p(a_1) & p(a_2) & \cdots & p(a_n) \right)
A의 순열들을 구하는 것은 집합 A읜 원소들의 나열에 p(a_i)의 가능한 경우의 수를 모두 나열한 것과 같습니다.
이 중 하나의 경우는 항등 함수가 되고, 나머지는 p_i로 표현 가능 합니다.
임의의 순열 하나 또는 두 개를 “순열의 곱”으로 계산 가능합니다. ( 함수의 합성처럼 정의하면 될 것입니다. )
두 순열의 곱은 다른 어떤 순열과 같아지게 되는데 이 개념을 이용하여 “순환적 순열”을 정의 할 수 있습니다.
집합 A = {a_1, a_2, \ldots, a_n} 의 순열 p : A -> A, p(b_1) = b_2 \cdots p(b_{n-1}) = b_n, p(b_n) = b_1
( b_i는 순환을 이루는 일부 원소들, b_i에 속하지 않는 원소 a_i는 항등함수 p(a_i) = a_i로 정의됩니다. )
순열은 결국 닫힌 연산이고 전단사 이기에 항등 함수로 정의 된 영역을 제외 하더라도
모두 반드시 순환적으로 이어져 있게 됩니다.
집합 A가 정의 될 때, 두 순환적 순열 p_1, p_2 가 각 순환하는 원소 (b_{p_1}, \cdots), (b_{p_2}, \cdots) 중
어떤 것도 서로 같은 값의 짝을 찾을 수 없다면, (즉, 두 순열의 순환 고리가 맞닿는 부분이 없다면, )
두 순환적 순열은 “분단”(disjoint) 되었다고 표현합니다.
집합 A가 정의 될 때, 어떤 순환적 순열이 길이가 2인 경우 (즉, 순환 고리가 두 개의 원소로 되어있는 경우) 에는
특별히 “치환”(transposition)이라고 표현합니다. ( p = ( a_i, a_j ) , p( a_i ) = a_j \vee p( a_j ) = a_i => p := 치환 )
어떤 순환적 순열이 짝수 개의 치환으로 표현 가능하면, 해당 순열을 “짝수 순열”(Even Permutation)이라고 표현하고,
홀수 개의 치환으로 표현 가능하면, 해당 순열을 “홀수 순열”(Odd Permutation)이라고 표현합니다.