Combinatorial principles

조합론(combinatorics)에서 결과를 증명하는 것에서, 몇 가지 유용한 조합론적 규칙 또는 조합론적 원칙이 공통적으로 인식되고 사용됩니다.

합의 법칙(rule of sum), 곱의 법칙(rule of product), 및 포함–제외 원리(inclusion–exclusion principle)는 종종 열거(enumerative) 목적으로 사용됩니다. 전단사 증명(bijective proof)은 두 집합이 같은 원소의 숫자를 가지고 있음을 시연하기 위해 사용됩니다. 비둘기집 원리(pigeonhole principle)는 종종 어떤 것의 존재를 확인하거나 이산(discrete) 문맥에서 어떤 것의 최소 또는 최대 숫자를 결정하기 위해 사용됩니다.

많은 조합론적 항등식(combinatorial identities)이 이중 세는(double counting) 방법 또는 구별된 원소의 방법(method of distinguished element)에서 발생합니다. 생성 함수(generating function)와 재귀 관계(recurrence relation)는 수열을 조작하기 위해 사용될 수 있는 강력한 도구이고, 많은 조합론적 상황을 해결할 수 없으면 설명할 수 있습니다.

Rule of sum

합의 규칙은 만약 어떤 사건 (또는 어떤 일을 하는 방법)에 대해 a 가능한 결과가 있고 또 다른 사건 (또는 또 다른 일을 하는 방법)에 대해 b 가능한 결과가 있고, 두 사건이 동시에 발생할 수 없으면 (또는 둘의 일이 둘 다 수행될 수 없으면), 사건에 대해 a + b 가능한 총 결과 (또는 일 중 하나를 수행하기 위한 총 가능한 방법)가 있다는 직관적인 원칙입니다. 보다 공식적으로, 둘의 서로소 집합(disjoint sets)의 크기의 합은 그것들의 합집합의 크기와 같습니다.

Rule of product

곱의 규칙은 만약 어떤 일을 하는 a 방법과 또 다른 일을 하는 b 방법이 있으면, 두 가지 모두를 하는 a · b 방법이 있다는 또 다른 직관적 원칙입니다.

Inclusion–exclusion principle

Inclusion–exclusion illustrated for three sets

포함–제외 원리는 여러 집합의 합집합 크기, 각 집합의 크기, 및 집합의 각 가능한 교집합의 크기와 관련이 있습니다. 가장 작은 예제는 두 집합이 있을 때입니다: A와 B의 합집합에 있는 원소의 숫자는 A와 B에서 원소 숫자의 합에서 교집합의 원소의 숫자를 뺀 것과 같습니다.

일반적으로, 이 원리에 따라, 만약 A₁, …, A_n가 유한 집합이면, 다음입니다:

{\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}

Rule of division

나눗셈의 규칙은 만약 n 방법에서 수행될 수 있는 절차를 사용하여 수행될 수 있고, 모든 각 방법 w에 대해, n 방법 중 정확히 d가 방법 w에 해당하면 작업을 수행하기 위한 n/d 방법이 있다고 말합니다.

Bijective proof

전단사 증명은 한 집합에서 나머지 하나의 집합으로 전단사 함수(bijective function) (일-대-일 대응)를 찾음으로써 두 집합이 같은 원소의 숫자를 가짐을 증명합니다.

Double counting

이중 세는 것은 집합의 크기를 두 가지 방법으로 세는 두 표현식을 같게 하는 기법입니다.

Pigeonhole principle

비둘기집 원리는 만약 a 항목이 b 상자 중 하나에 각각 넣으면 (여기서 a > b), 상자 중 하나는 하나보다 많은 항목이 들어 있다는 것입니다. 이것을 사용하여 우리는, 예를 들어, 일부 특정 속성을 갖는 집합에 일부 원소가 있음을 시연할 수 있습니다.

Method of distinguished element

구별된 원소의 방법은 어떤 결과를 입증하기 위해 집합의 "구별된 원소"를 선택합니다.

Generating function

생성 함수는 그것의 계수가 수열의 항에 해당하는 무한하게 많은 항을 갖는 다항식으로 생각될 수 있습니다. 그 수열의 이러한 새로운 표현은 특정 수열과 관한 항등식과 닫힌 형식을 찾기 위한 새로운 방법을 엽니다. 수열 a_n의 (보통의) 생성 함수는 다음입니다:

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

Recurrence relation

재귀 관계는 선행 항의 관점에서 수열의 각 항을 정의합니다. 재귀 관계는 수열의 이전의 미지수 속성으로 이어질 수 있지만, 일반적으로 수열의 항에 대해 닫힌-형식 표현(closed-form expression)이 더 바람직합니다.

References

van Lint, J.H.; Wilson, R.M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press. ISBN 0-521-00601-5.