조합론(combinatorics)에서, 이중 세는 것은, 역시 둘의 방법에서 세는 것이라고 불리며, 한 집합(set)의 크기를 세는 두 가지 방법임을 시연함으로써 두 표현식이 같음을 보여주는 조합론적 증명(combinatorial proof) 기법입니다. van Lint & Wilson (2001)이 "조합론에서 가장 중요한 도구 중 하나"라고 부르는 이 기법에서, 우리는 집합의 크기에 대해 둘의 구별되는 표현으로 이어지는 두 가지 관점에서 유한 집합(finite set)을 설명합니다. 두 표현은 같은 집합의 크기와 같으므로, 그것들은 서로 같습니다.
Examples
Multiplication (of natural numbers) commutes
이것은 어린 아이들에게 곱셈을 가르칠 때 자주 사용되는 이중 셈의 간단한 예제입니다. 이러한 문맥에서, 자연수(natural number)의 곱셈은 반복된 덧셈으로 소개하고, 그런-다음 직사각형 격자에 배열된 항목의 숫자를, 두 가지 다른 방법으로, 셈으로써 교환적(commutative)임을 보여줍니다. 격자가 \(n\) 행과 \(m\) 열을 가진다고 가정합니다. 우리는 먼저 각각 \(m\) 항목의 \(n\) 행을 합함으로써 항목을 세고, 그런-다음 두 번째로 각각 \(n\) 항목의 \(m\) 열을 합함으로써 항목을 세고, 따라서 \(n\)과 \(m\)의 특정 값에 대해 \(n \times m = m \times n\)임을 보입니다. 증명은 아니지만, 우리가 선택하는 (실제 크기의) 임의의 예제에 대해, 곱셈이 교환하는 것을 분명히 보여줍니다.
Forming committees
이중 세는 방법의 한 가지 예제는 위원회가 \(n\) 명으로 구성될 수 있는 방법의 숫자를 계산하며, 원하는 숫자의 사람들 (심지어 그들 중 0명)이 위원회의 일부가 되도록 허용합니다. 즉, 우리는 \(n\)-원소 집합이 가질 수 있는 부분집합(subset)의 숫자를 셉니다. 위원회를 구성하는 한 가지 방법은 각 사람에게 위원회에 참여할지 여부를 선택하도록 묻는 것입니다. 각 사람은 예 또는 아니오의 두 가지 선택을 가지고 이들 선택은 다른 사람들의 선택과 독립입니다. 그러므로 \(2\times 2\times \cdots 2 = 2^n\) 가능성이 있습니다. 대안적으로, 우리는 위원회의 크기가 0에서 \(n\) 사이의 어떤 숫자여야 함을 관찰할 수 있습니다. 각 가능한 크기 \(k\)에 대해, \(k\) 명의 위원회가 \(n\) 명으로부터 구성될 수 있는 방법의 숫자는 이항 계수(binomial coefficient)입니다:
\(\quad\displaystyle {n \choose k}.\)
그러므로 가능한 위원회의 총 수는 \(k=0,1,2,\dots,n\)에 걸쳐 이항 계수의 합입니다. 두 표현을 같게 하면 다음 항등식(identity)을 제공합니다:
\(\quad\displaystyle \sum_{k=0}^n {n \choose k} = 2^n,\)
이것은 이항 정리(binomial theorem)의 특별한 경우입니다. 유사한 이중 세는 방법은 보다 일반적인 다음 항등식을 입증하기 위해 사용될 수 있습니다:
\(\quad\displaystyle \sum_{k=d}^n {n\choose k}{k\choose d} = 2^{n-d}{n\choose d}\)
(Garbano, Malerba & Lewinter 2003; Klavžar 2006).
Handshaking lemma
이중 세는 논증으로 공통적으로 입증되는 또 다른 정리는 모든 각 무-방향 그래프(undirected graph)가 홀수 차수(degree)의 짝수 개의 꼭짓점(vertices)을 포함한다는 말합니다. 즉, 발생 가장자리(edges)의 개수가 홀수를 가지는 꼭짓점의 개수는 짝수여야 합니다. 좀 더 구어체로 말하면, 몇몇 사람들이 악수를 하는 파티에서, 짝수 명의 사람들이 홀수 명의 다른 사람들과 악수를 했음에 틀림없습니다; 이러한 이유로, 결과는 악수 보조정리(handshaking lemma)로 알려져 있습니다.
이중 셈으로써 이를 증명하기 위해, \(d(v)\)를 꼭짓점 \(v\)의 차수로 놓습니다. 그래프에서 꼭짓점-가장자리 발생의 횟수가 두 가지 다른 방법에서: 꼭짓점의 차수를 합산함으로써, 또는 모든 각 가장자리에 대해 두 번 발생을 셈으로써 계산될 수 있습니다. 그러므로
\(\quad\displaystyle \sum_v d(v) = 2e\)
여기서 \(e\)는 가장자리의 개수입니다. 꼭짓점의 차수의 합은 따라서 짝수(even number)이며, 만약 꼭짓점의 홀수가 홀수 차수를 가졌다면 방생할 수 없는 것입니다. 이 사실은, 이 증명과 함께, 1736년에 처음 그래프 이론(graph theory)의 연구를 시작했던 쾨니히스베르크의 일곱 다리(Seven Bridges of Königsberg)에 대한 레온하르트 오일러(Leonhard Euler)의 논문에서 나타났습니다.
Counting trees
\(n\)의 구별되는 꼭짓점의 집합으로 형성될 수 있는 서로 다른 트리(trees)의 숫자 \(T_n\)은 무엇입니까? 케일리의 공식(Cayley's formula)은 답 \(T_n=n^{n-2}\)을 제공합니다. Aigner & Ziegler (1998)는 이 사실의 네 가지 증명을 나열합니다; 그들은 짐 피트먼에 의한 이중 세는 증명, 네 번째에 대해 "그것들 중 가장 아름다운 증명"이라고 씁니다.
Pitman의 증명은 \(n\) 꼭짓점을 뿌리 트리(rooted tree)를 그것으로부터 형성하기 위해 빈 그래프(empty graph)에 추가될 수 있는 방향화된 가장자리의 수열의 개수를 두 가지 다른 방법으로 계산합니다. 그러한 수열을 형성하는 한 가지 방법은 \(T_n\) 가능한 비-뿌리 트리 중 하나로 시작하여, \(n\) 꼭짓점 중 하나를 루트로 선택하고, 그것의 \(n-1\) (방향화된) 가장자리를 추가하기 위해 \((n-1)!\) 가능한 수열 중 하나를 선택하는 것입니다. 그러므로, 이러한 방법으로 형성될 수 있는 수열의 총 수는 \(T_n n(n-1)! = T_n n!\)입니다.
이들 가장자리 수열을 세는 또 다른 방법은 가장자리를 하나씩 빈 그래프에 추가하고, 각 단계에서 사용할 수 있는 선택의 수를 세는 것입니다. 만약 우리가 이미 \(n-k\) 가장자리의 모음을 더해 왔으면, 이들 가장자리에 의해 형성된 그래프가 \(k\) 트리를 갖는 뿌리 [[Tree_(graph_theory)#Forest|숲(forest)]]이 되도록, 다음 가장자리에 대해 더하려는 \(n(k-1)\) 선택이 있습니다: 그것의 시작 꼭짓점은 그래프의 \(n\) 꼭짓점 중 임의의 하나일 수 있고, 그것의 끝나는 꼭짓점은 시작하는 꼭짓점을 포함하는 트리의 뿌리가 아닌 \(k-1\) 뿌리 중 임의의 하나일 수 있습니다. 그러므로, 만약 우리가 첫 번째 단계, 두 번째 단계, 등의 선택 수를 함께 곱하면, 전체 선택의 개수는
\(\quad\displaystyle \prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.\)
가장자리 수열의 숫자에 대해 이들 두 공식을 같게 하면 케일리의 공식을 초래합니다:
\(\quad\displaystyle \displaystyle T_n n!=n^{n-2}n!\)
및
\(\quad\displaystyle \displaystyle T_n=n^{n-2}.\)
Aigner와 Ziegler가 설명하는 것처럼, 그 공식과 그 증명은 임의의 ''k''에 대해 ''k'' 트리를 갖는 뿌리 숲의 수를 세기 위해 일반화될 수 있습니다.
See also
Additional examples
- 방데르몽드 항등식(Vandermonde's identity), 이중 셈으로 입증될 수 있는 이항 계수의 합에 대한 또 다른 항등식.
- 제곱 피라미드 숫자(square pyramidal number). 처음 \(n\) 제곱수(square number)의 합과 삼차 다항식 사이의 상등은 \(x\), \(y\), 및 \(z\)의 세-쌍을 이중 셈으로써 보일 수 있으며, 여기서 \(z\)는 다른 두 숫자 중 하나보다 큽니다.
- Lubell–Yamamoto–Meshalkin inequality. 집합 가족에 대한 이 결과의 Lubell의 증명은 상등이 아닌 부등식(inequality)을 증명하기 위해 사용된 순열(permutation)에 대한 이중 세는 논증입니다.
- 페르마의 작은 정리의 증명(Proofs of Fermat's little theorem). 이중 셈에 의한 나눔가능성(divisibility) 증명: 임의의 소수(prime) \(p\)와 자연수 \(A\)에 대해, 둘 이사의 구별되는 기호를 가지는 \(A\)-기호 알파벳에 걸쳐 \(A^p-A\) 길이-\(p\) 단어가 있습니다. 이것들은 순환 이동(circular shift)에 의해 서로 변환될 수 있는 \(p\) 단어의 집합으로 그룹화될 수 있습니다; 이것 집합은 목걸이(necklaces)라고 불립니다. 그러므로, \(A^p-A=p\cdot{}\) (목걸이의 개수)이고 \(p\)p로 나뉠 수 있습니다.
- 이차 상호관계의 증명(Proofs of quadratic reciprocity). 아인슈타인(Eisenstein)에 의한 증명은 삼각형에서 격자점을 이중으로 셈으로써 또 다른 중요한 숫자-이론적(number-theoretic) 사실을 도출합니다.
Related topics
- 전단사 증명(bijective proof). 이중 셈은 한 집합을 두 가지 방법으로 계산하는 것과 관련이 있지만, 전단사 증명은 두 집합의 원소가 일대일로 대응한다는 것을 보여줌으로써 한 방법으로 두 집합을 계산하는 것을 포함합니다.
- 포함–제외 원리(inclusion–exclusion principle), 같은 합집합에 대한 또 다른 공식과 함께, 이중 세는 논증의 일부로 사용될 수 있는 집합의 합집합(union)의 크기에 대한 공식.
References
- Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag. Double counting is described as a general principle on page 126; Pitman's double counting proof of Cayley's formula is on pp. 145–146.
- Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
- Garbano, M. L.; Malerba, J. F.; Lewinter, M. (2003), "Hypercubes and Pascal's triangle: a tale of two proofs", Mathematics Magazine, 76 (3): 216–217, doi:10.2307/3219324, JSTOR 3219324.
- Klavžar, Sandi (2006), "Counting hypercubes in hypercubes", Discrete Mathematics, 306 (22): 2964–2967, doi:10.1016/j.disc.2005.10.036.
- van Lint, Jacobus H.; Wilson, Richard M. (2001), A Course in Combinatorics, Cambridge University Press, p. 4, ISBN 978-0-521-00601-9.