조합론(combinatorics)에서, 전단사 증명(bijective proof)은 두 유한 집합(finite set) A와 B 사이의 전단사 함수(bijective function) (즉, 일-대일-일(one-to-one) 및 위로의(onto) 함수) f : A → B, 또는 두 조합론적 클래스(combinatorial class) 사이에 크기-보존하는 전단사 함수를 찾고, 따라서 그것들이 같은 크기의 원소, |A| = |B|를 가짐을 입증하는 증명(proof) 기법입니다. 그 기법이 유용한 하나의 장소는 우리가 A의 크기를 알기를 원하지만, 그것의 원소를 세는 직접적인 방법을 찾을 수 없는 곳입니다. A에서 일부 B로의 전단사를 설정함으로써 만약 B가 더 쉽게 셀 수 있으면 그 문제를 해결합니다. 그 기법의 또 다른 유용한 특색은 전단사 자체의 본성이 종종 각 집합 또는 두 집합에 대한 강력한 통찰력을 제공한다는 것입니다.
Basic examples
Proving the symmetry of the binomial coefficients
이항 계수의 대칭은 다음임을 말합니다:
\(\quad\displaystyle {n \choose k} = {n \choose n-k}. \)
이것은 크기 n의 집합에서 k 대상의 조합과 정확히 같은 만큼이 크기 n 집합에서 n − k 대상의 조합이 있음을 의미합니다.
A bijective proof
증명의 핵심 아이디어는 간단한 예제에서 이해될 수 있습니다: n 명의 어린이 그룹에서 아이스크림 콘으로 보상할 k를 선택하는 것은 그것을 보상하지 않을 n − k 어린이를 선택하는 것과 정확히 같은 효과를 냅니다.
보다 추상적이고 일반적으로, 같을 것이라고 주장되는 두 양은 임의의 n-원소 집합 S의, 각각, 크기 k와 n − k의 부분집합을 셉니다. A를 S의 모든 k-원소 부분집합의 집합이라고 놓고, 집합 A는 크기 \(\tbinom{n}{k}\)를 가집니다. B를 S의 모든 n−k 부분집합의 집합으로 놓고, 집합 B는 크기 \(\tbinom{n}{n-k}\)를 가집니다. 두 집합 A와 B 사이에는 단순한 전단사가 있습니다: 그것은 모든 각 k-원소 부분집합 (즉, A의 구성원)을 S의 남아있는 n − k 원소를 정확히 포함하는 그것의 여집합(complement)과 결합하고, 따라서 B의 구성원입니다. 보다 공식적으로, 이것은 함수형 표기법(functional notation)을 사용하여, X에 대해 \(f(X)=X^c\)에 의해 정의된 f : A → B, S의 임의의 k-원소 부분집합과 S에서 취한 여집합으로 쓰일 수 있습니다. f가 전단사임을 보이기 위해, 먼저 \(f(X_1)=f(X_2)\), 즉, \(X_1^c = X_2^c\)임을 가정합니다. \(X_1=X_2\)를 얻기 위해, 집합의 여집합의 여집합은 원래 집합이라는 사실을 사용하여, (S에서) 각 변의 여집합을 취합니다. 이것은 f가 일-대-일(one-to-one)이라는 것을 보여줍니다. 이제 B에서 S의 임의의 n−k-원소 부분집합, 말하자면 Y를 취합니다. S에서 그것의 여집합, \(Y^c\)는 k-원소 부분집합이고, 따라서 A의 원소입니다. \(f(Y^c)=(Y^c)^c=Y\)이므로, f는 역시 위로의(onto)이고 따라서 전단사입니다. 그 결과는 이제 이들 유한 집합 사이에 전단사의 존재가 그들이 같은 크기, 즉, \(\tbinom{n}{k} = \tbinom{n}{n-k}\)를 가짐을 보이기 때문에 따릅니다.
Other examples
전단사 증명을 인정하는 문제는 이항 계수 항등식에 국한되지 않습니다. 문제의 복잡성이 증가함에 따라, 전단사 증명은 매우 정교해질 수 있습니다. 이 기법은 조합론(combinatorics), 그래프 이론(graph theory), 및 숫자 이론(number theory)과 같은 이산 수학(discrete mathematics)의 분야에서 특히 유용합니다.
조합론에서 전단사 증명의 가장 고전적인 예제는 다음을 포함합니다:
- 프뤼퍼 수열(Prüfer sequence), 분류된 나무(labeled tree)의 숫자에 대해 케일리의 공식(Cayley's formula)의 증명을 제공합니다.
- 로빈슨-휘안스테드 알고리듬(Robinson-Schensted algorithm), 대칭 그룹(symmetric group)에 대해 번사이드(Burnside)의 공식의 증명을 제공합니다.
- 영 다이어그램(Young diagram)의 활용(Conjugation), 특정 정수 분할(integer partitions)의 숫자에 대한 고전적 결과의 증명을 제공합니다.
- 오각 숫자 정리(pentagonal number theorem)의 전단사 증명.
- 카탈랑 숫자(Catalan number)에 대해 공식의 전단사 증명.
See also
- Binomial theorem
- Schröder–Bernstein theorem
- Double counting (proof technique)
- Combinatorial principles
- Combinatorial proof
- Categorification
Further reading
- Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 143984884X, ISBN 978-1439848845.
External links
- "Division by three" – by Doyle and Conway.
- "A direct bijective proof of the hook-length formula" – by Novelli, Pak and Stoyanovsky.
- "Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees" – by Gilles Schaeffer.
- "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – by Doron Zeilberger.
- "Partition Bijections, a Survey" – by Igor Pak.
- Garsia-Milne Involution Principle – from MathWorld.