콤비네이터얼 프루프

수학에서 조합 증명이라는 용어는 종종 두 가지 유형의 수학적 증명 중 하나를 의미하는 데 사용된다.

• 이중 세기에 의한 증거.조합적 정체성은 그 정체성의 다른 표현들을 얻기 위해 두 가지 다른 방법으로 신중하게 선택된 몇몇 요소들의 수를 세는 것으로 증명된다.그 표현들은 같은 대상을 세기 때문에 서로 동등해야 하고 따라서 정체성이 확립된다.
• 비굴한 증거.두 세트는 서로 간에 일대일 서신을 주고받는 편견을 보여줌으로써 동일한 수의 회원을 가지는 것으로 나타난다.

조합 증명이라는 용어는 조합학에서 어떤 종류의 기본적인 증명도 참조하기 위해 더 광범위하게 사용될 수 있다.그러나, 글래스(2003)가 벤자민&퀸(2003)에 대한 리뷰에서 쓰듯이, 이 두 가지 간단한 기술은 결합론과 숫자 이론에서 많은 이론들을 증명하기에 충분하다.

예

원형의 이중 계수 증명은 n-요소 집합의 k-결합(즉, k 크기의 부분 집합) 숫자$$$({\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ $){\${\$tbinom {n}{k}}}$에 대해 잘 알려진 공식에 대한 것이다.

${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}}$

여기서 직접의 주관적 증거는 불가능하다: 그 정체성의 오른쪽이 분수이기 때문에 그것에 의해 분명히 계산된 것은 없다(분모가 항상 분자를 고르게 나눈다는 것을 보는 것조차 약간의 생각이 필요하다).그러나 분자는 k 유한한 크기의 k 유한 집합, n - 1, ..., n - k + 1의 데카르트 제품을 계수하는 반면, 분모는 k-요소 집합의 순열을 계수한다(분모가 가장 분명히 계수하는 세트는 또 다른 데카르트 제품 k 유한 집합, 원하는 경우 명시적 바이어싱에 의해 설정된 순열을 매핑할 수 있다).이제 S를 반복 없이 n-element 세트에서 선택한 k-element의 시퀀스 집합으로 삼으십시오.On one hand, there is an easy bijection of S with the Cartesian product corresponding to the numerator ${\displaystyle n(n-1)\cdots (n-k+1)}$, and on the other hand there is a bijection from the set C of pairs of a k-combination and a permutation σ of k to S, by taking the elements of C in increasing order, and th이 순서를 σ에 의해 허용하여 S의 원소를 얻는다.계산하는 두 가지 방법은 방정식을 준다.

${\displaystyle n(n-1)\cdots(n-k+1)={\binom {n}{k}k!,}$

그리고 k로 나눈 후! 이렇게 하면${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$ k${\displaystyle }$) ${\$에 대해 명시된 공식으로 이어진다$.$ 일반적으로 계산식이 분열을 포함한다면 유사한 이중 계수 인수(존재하는 경우)가 ID에 대한 가장 직접적인 결합 증거를 제공하지만 이중 계수 인수는 si에 국한되지 않는다.공식이 이런 형태의 등록금

다음은 동일한 정체성에 대한 보다 간단하고 비공식적인 결합 증명이다.

${\displaystyle {\binom {n}{k}k!(n-k)!=n!}$

n명의 사람들이 박물관에 들어가고 싶어하지만 박물관은 k명의 사람들을 위한 공간만 있다고 가정해보자.우선 n명 중에서 어느 k명을 들어갈 수 있는지 선택한다.정의로 이를 수행하는 ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{방법}}{}}$에는${\displaystyle }$(${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$k ) $displaystyle {\$tbinom {$n}{k}}}$이(가) 있다.이제 k명에게 한 번에 한 개씩 지불할 수 있도록 단일 파일 라인으로 주문하십시오.이 k사이즈 세트를 퍼머하는 방법은 k!가 있다.다음으로, 외부에 남아 있어야 하는 n -k를 한 줄로 주문하여 나중에 다른 사람들이 떠나면서 한 번에 하나씩 입력할 수 있도록 한다.이를 위한 (n - k) 방법이 있다.하지만 지금 우리는 n명의 그룹 전체를 주문했는데, n! 방법으로 할 수 있는 것이다.그래서 양쪽 모두 n명의 사람들을 주문하는 방법의 수를 세고 있다.분할에서는 (${\displaystyle n\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$)${\$에 대해 잘 알려진 공식을 산출한다$.$

결합 증명의 이점

스탠리(1997)는 그 해법에 대한 두 가지 다른 증거와 함께₂ 콤비네이터 열거 문제(k 하위 집합 S₁, S, ... S의_k 시퀀스 수를 계산하여 하위 집합이 빈 공통 교차점을 갖는 것과 같은 n개의 항목 집합에서 형성될 수 있다)의 예를 제시한다.조합이 아닌 첫 번째 증명은 수학적 유도와 생성 기능을 사용하여 이 유형의 시퀀스 수가 (2^k -1)임을 알아낸다.ⁿ두 번째 증거는 세트 {1, 2, ..., k}, 세트 {1, 2, ..., k}, 그리고 세트^k {1,ⁿ 2, ..., n}부터 세트 {1, 2, ..., k}의 적절한 하위 집합의 2^k -1의 적절한 하위 집합이 있다는 관찰에 근거한다.계수할 시퀀스는 이러한 기능과 일대일 대응으로 배치될 수 있으며, 여기서 주어진 하위 집합 시퀀스에서 형성된 함수는 각 요소 i를 세트 {j i_j ∈ S}에 매핑한다.

스탠리는 "위의 결합 증명서가 우리의 이전 증거보다 훨씬 짧을 뿐만 아니라, 간단한 답변의 이유를 완전히 투명하게 한다.여기서 일어난 것처럼 가장 먼저 떠오르는 증거가 고역적이고 비합법적인 것으로 밝혀지지만, 최종적인 대답은 단순한 결합적 증거를 암시하는 경우가 종종 있다."비결합 증명보다 더 큰 우아함과 그들이 묘사하는 구조에 더 큰 통찰력 때문에, 스탠리는 조합 증명들이 다른 증명들보다 더 선호되어야 한다는 일반적인 원리를 형성하고, 알려진 수학적인 사실들에 대한 조합 증명들을 찾는 많은 문제들을 연습하고 있다.o는 다른 수단을 통해서 진실하다.

주관적 증명과 이중 계산 증명의 차이

스탠리 명확하고 이중으로 계산 증명bijective에 이르며, 두 종류의 예를 제공하지만, 조합적 증거의 두 종류의 차이는 예 아이그너 및이 제공하는 볼 수 있으나 교정 케일리의 공식을 지글러(1998년)가nn− 2 다른 나무 a로부터 형성될 수 있어 있다고 말하는 공로를 세우지 않는다sen개 노드의 t.아이그너와 지글러는 이 정리에 대한 네 가지 증거를 나열하는데, 그 중 첫 번째는 비주사적이며 마지막은 이중 계수론이다.그들은 또한 다섯 번째 주관적 증거에 대한 자세한 내용은 언급하지 않았다.

이 공식에 대한 가장 자연스러운 실험적인 증거를 찾는 방법은 n-노드 나무와 n 멤버가^{n − 2} 있는 일부 개체 집합 사이의 편차를 찾는 것이다. 예를 들어, 각각 1부터 n까지의 범위에서 n - 2 값의 시퀀스를 찾을 수 있다.이러한 바이어싱은 각 트리의 Prufer 시퀀스를 사용하여 얻을 수 있다.어떤 나무도 Prufer 시퀀스로 고유하게 인코딩될 수 있고, 어떤 Prufer 시퀀스도 나무로 고유하게 디코딩될 수 있다. 이 두 결과는 Cayley의 공식에 대한 생물학적인 증거를 제공한다.

아이그너와 지글러가 주고 안드레 조이알에게 공로를 인정받은 대안적 생물학적 증거는 한편으로 지정된 두 개의 노드가 있는 n-노드 나무들(상호 같을 수도 있음)과 다른 한편으로 n-노드가 지시하는 사이비 숲 사이의 편차를 포함한다.T_n n-노드 트리가 있으면 2개의 지정된 노드를 가진 nT²_n 트리가 있다.그리고 사이비 포리스트는 각각의 노드에 대해 해당 노드에서 바깥으로 확장되는 에지의 끝점을 지정하여 결정할 수 있다. 단일 에지의 끝점에 대해 가능한 선택사항(자체 루프를 허용하는 것)이 n개 있고 따라서 가능한 사이비 포리스트가 n개ⁿ 있다.라벨이 붙은 두 개의 노드와 사이비 포리스트가 있는 나무들 사이의 편견을 발견함으로써 조이알의 증거는_n T = n을^{n − 2} 보여준다.

마지막으로 아이그너와 지글러가 제시한 케이리 공식의 네 번째 증명은 짐 핏먼 때문에 이중 계수 증명이 된다.이 증거에서 Pitman은 n-노드 빈 그래프에 추가될 수 있는 지시된 가장자리 시퀀스를 하나의 뿌리가 있는 나무로 간주하고, 그러한 시퀀스의 수를 두 가지 다른 방법으로 카운트한다.나무와 나무의 뿌리, 그리고 나무의 가장자리에 대한 순서를 선택함으로써 이러한 유형의 시퀀스를 도출하는 방법을 보여줌으로써, 그는 이러한 유형의 Tn! 가능한_n 시퀀스가 있음을 보여준다.그리고 부분 시퀀스가 하나의 가장자리로 확장될 수 있는 방법의 수를 세면서, 그는 nn^{n − 2}! 가능한 시퀀스가 있다는 것을 보여준다.동일한 에지 시퀀스 세트의 크기에 대해 이 두 가지 공식을 동일시하고 n!의 공통 인자를 취소하면 Cayley의 공식으로 이어진다.

관련개념

• 결합증명에 사용되는 이중계수와 편향의 원리는 더 큰 결합원리의 가족의 예로 볼 수 있는데, 이 원리는 비둘기구멍 원리와 같은 다른 생각들도 포함하고 있다.
• 동일성을 조합하여 증명하는 것은 숫자를 세트별로 대체함으로써 그 아이덴티티에 더 많은 구조를 추가하는 것으로 볼 수 있다. 마찬가지로, 분류는 카테고리별로 세트를 대체하는 것이다.

참조

• Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pp. 141–146, ISBN 3-540-40460-0.

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions, vol. 27, Mathematical Association of America, ISBN 978-0-88385-333-7.

• Glass, Darren (2003), Read This: Proofs that Really Count, Mathematical Association of America.

• Stanley, Richard P. (1997), Enumerative Combinatorics, Volume I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, pp. 11–12, ISBN 0-521-55309-1.