置 換 [치ː환], substitution
1. 기본적인 의미
명사: 바꾸어 놓음2. 수학에서의 치환
2.1. 방정식에서의 치환
어떤 항, 수식을 하나의 문자로 바꾸는 일. 가령 홀수차 항이 없는 [math(x)]에 대한 [math(4)]차 방정식[1]에서 근을 구할 때 [math(x^2 = t)]로 치환하여 [math(t)]에 대한 [math(2)]차 방정식으로 바꾸어 풀면 용이하다.[2] 치환한 문자를 원래의 문자로 되돌리는 것을 '환원'이라고 하며, 부정적분을 계산할 때 적분 변수를 치환하여 적분( 치환적분)한 경우 마지막에 반드시 환원해야 한다.사차방정식의 특수한 형태인 복이차식([math(ax^4+bx^2+c=0)] 꼴)을 풀 때 [math(x^2=t)]로 치환하여 새로운 이차방정식으로 바꾸는 등 치환은 수학의 다양한 방면에서 여러모로 긴요한 테크닉이다.
연립방정식에서는 따로 '대입법'이라고 한다. 식 하나를 한 문자에 대한 식으로 정리한 뒤, 다른 식에서 환원해서 푸는 방법이다.
2.2. 군론에서의 치환
|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · #s-2.2 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
permutation
여러 개의 대상들이 주어졌을 때, 그것들의 순서를 바꾸는 일. 사다리타기를 생각해도 좋다. 영어 명칭이 고등학교 수학 과정에 나오는 순열과 똑같은데, 주어진 원소들 내에서 일부 혹은 전체의 순서를 맞바꾸는(permutate) 조작이라는 점에서 둘은 사실상 같은 것이기 때문이다. 실제로 치환의 개수는 순열로 표현할 수 있으며 하강 계승으로도 나타낼 수 있다.
군론에서 치환(순열)을 나타내는 방법에는 두 가지가 있는데 가장 기본적인 것은 다음과 같은 2행 표기법(two-line notation)[3]이다. 첫 번째 행에는 치환을 조작하기 전(항등치환)의 각 원소의 순서를 쓰며 두 번째 행에는 치환 이후의 순서를 표기한다. 아래 예시에서는 항등치환의 원소가 자연수이지만 [math(x_i)]로 나타내는 경우도 흔하다.
| [math(\sigma = \begin{pmatrix} 1 & 2 & 3 & \cdots\cdots \\ \sigma \left(1\right) & \sigma \left(2\right) & \sigma \left(3\right) & \cdots\cdots \end{pmatrix})] |
| [math(\sigma = \begin{pmatrix} \sigma \left(1\right) & \sigma \left(2\right) & \sigma \left(3\right) & \cdots\cdots \end{pmatrix})] |
이를테면
[math(\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix})]
는 [math(\sigma \left(1\right) = 2)], [math(\sigma \left(2\right) = 3)], [math(\sigma \left(3\right) = 1)][4]이며 원소 [math(x_i)]로 나타낸 치환 이후의 순서는 [math(\begin{matrix} x_3 & x_1 & x_2 \end{matrix})]가 된다. 1행 표기법으로는
[math(\sigma_{231} = \begin{pmatrix} 2 & 3 & 1 \end{pmatrix})]
이 된다.
2.2.1. 치환의 종류
-
항등치환
순서를 바꾸지 않는 치환. 일반적으로 [math(\varepsilon)]로 나타낸다. 뭐 이따위 치환도 있냐고 느낄 수도 있겠지만, 이름에서 알 수 있듯이 대칭군에서 항등원 역할을 하는, 정말 중요한 치환이다. 참고로 항등치환의 경우 원소가 1개뿐이라 그 자체. 즉 '1개의 치환'으로 항등치환이 표기되는 상황이라도 반드시 짝치환으로 취급한다.
-
호환
단 [math(2)]개만 맞바꾸는 것. 아래의 예에서는 [math(1)]과 [math(2)]만이 맞바뀌었으며, 1행 표기법에서는 [math(3)]과 [math(4)]가 종종 생략된다.[5]
[math(\sigma_{12} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 1 \end{pmatrix})]
모든 치환은 호환의 합성(곱)으로 표현되며, 그런 가정하에 아래의 개념이 성립한다. 그 외 다른 가정이 필요한데 각 항목에서 설명한다.
-
짝치환(우치환)
짝수 개 호환의 합성으로 표현되는 치환. 짝치환은 어떤 방식으로 표현하든 짝수 개의 호환이 필요하다.
-
홀치환(기치환)
홀수 개 호환의 합성으로 표현되는 치환. 홀치환은 어떤 방식으로 표현하든 홀수 개의 호환이 필요하다.
-
[math(p)]순환치환
[math(p)]개 원소들의 치환으로서, 이 종류의 치환을 [math(p)]번 합성하면 항등치환이 나온다.
아래의 경우는 [math(3)]순환치환이며 부동점은 [math(4)]이다.
[math(\sigma_{231} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{pmatrix} = \begin{pmatrix} 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 4 \end{pmatrix})]
보다 자세한 것은 대칭군 참조.
2.2.2. 치환 알고리즘
[math(\sigma_{123} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix})]의 2행표기법에서 1행 표기법으로는 [math( \left( 123 \right) )]으로 표기할수있다.집합P = {1,2,3}의 치환에서 이것을 순열 생성 알고리즘으로 돌리면
(123) , (132) ,(231) ,(312),(213),(321)로 6개 나온다. 이걸 다시 2행표기법으로 바꾸면
[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix})],[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix})]을 얻을수있다.
2.2.3. 순환군의 합성
예를 들어 집합S ={1,2,3}의 치환군 S,3, 에서 [math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix})] 하나의 원소에 의해 생성되는 군인 순환군은 합성함수(function composition)에서 보면[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )]
[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} )]이다.
즉, [math( \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} )],[math( \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} )],[math( \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} )] 3개이다.
순열의 홀짝성(parity)에서 우(짝)순열과 우(짝)순열의 합성은 우순열이고 기(홀)순열과 기(홀)순열의 합성은 우순열을 잘 보여주는 순환군이다.