Double counting (proof technique)

조합론(combinatorics)에서, 이중 세는 것은, 역시 둘의 방법에서 세는 것이라고 불리며, 한 집합(set)의 크기를 세는 두 가지 방법임을 시연함으로써 두 표현식이 같음을 보여주는 조합론적 증명(combinatorial proof) 기법입니다. van Lint & Wilson (2001)이 "조합론에서 가장 중요한 도구 중 하나"라고 부르는 이 기법에서, 우리는 집합의 크기에 대해 둘의 구별되는 표현으로 이어지는 두 가지 관점에서 유한 집합(finite set)을 설명합니다. 두 표현은 같은 집합의 크기와 같으므로, 그것들은 서로 같습니다.

Examples

Multiplication (of natural numbers) commutes

이것은 어린 아이들에게 곱셈을 가르칠 때 자주 사용되는 이중 셈의 간단한 예제입니다. 이러한 문맥에서, 자연수(natural number)의 곱셈은 반복된 덧셈으로 소개하고, 그런-다음 직사각형 격자에 배열된 항목의 숫자를, 두 가지 다른 방법으로, 셈으로써 교환적(commutative)임을 보여줍니다. 격자가 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 행과 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle m} 열을 가진다고 가정합니다. 우리는 먼저 각각 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle m} 항목의 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 행을 합함으로써 항목을 세고, 그런-다음 두 번째로 각각 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 항목의 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle m} 열을 합함으로써 항목을 세고, 따라서 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 과 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle m} 의 특정 값에 대해 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n \times m = m \times n} 임을 보입니다. 증명은 아니지만, 우리가 선택하는 (실제 크기의) 임의의 예제에 대해, 곱셈이 교환하는 것을 분명히 보여줍니다.

Forming committees

이중 세는 방법의 한 가지 예제는 위원회가 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 명으로 구성될 수 있는 방법의 숫자를 계산하며, 원하는 숫자의 사람들 (심지어 그들 중 0명)이 위원회의 일부가 되도록 허용합니다. 즉, 우리는 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} -원소 집합이 가질 수 있는 부분집합(subset)의 숫자를 셉니다. 위원회를 구성하는 한 가지 방법은 각 사람에게 위원회에 참여할지 여부를 선택하도록 묻는 것입니다. 각 사람은 예 또는 아니오의 두 가지 선택을 가지고 이들 선택은 다른 사람들의 선택과 독립입니다. 그러므로 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle 2\times 2\times \cdots 2 = 2^n} 가능성이 있습니다. 대안적으로, 우리는 위원회의 크기가 0에서 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 사이의 어떤 숫자여야 함을 관찰할 수 있습니다. 각 가능한 크기 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle k} 에 대해, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle k} 명의 위원회가 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 명으로부터 구성될 수 있는 방법의 숫자는 이항 계수(binomial coefficient)입니다:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle {n \choose k}.}

그러므로 가능한 위원회의 총 수는 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle k=0,1,2,\dots,n} 에 걸쳐 이항 계수의 합입니다. 두 표현을 같게 하면 다음 항등식(identity)을 제공합니다:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \sum_{k=0}^n {n \choose k} = 2^n,}

이것은 이항 정리(binomial theorem)의 특별한 경우입니다. 유사한 이중 세는 방법은 보다 일반적인 다음 항등식을 입증하기 위해 사용될 수 있습니다:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\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)로 알려져 있습니다.

이중 셈으로써 이를 증명하기 위해, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle d(v)} 를 꼭짓점 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle v} 의 차수로 놓습니다. 그래프에서 꼭짓점-가장자리 발생의 횟수가 두 가지 다른 방법에서: 꼭짓점의 차수를 합산함으로써, 또는 모든 각 가장자리에 대해 두 번 발생을 셈으로써 계산될 수 있습니다. 그러므로

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \sum_v d(v) = 2e}

여기서 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle e} 는 가장자리의 개수입니다. 꼭짓점의 차수의 합은 따라서 짝수(even number)이며, 만약 꼭짓점의 홀수가 홀수 차수를 가졌다면 방생할 수 없는 것입니다. 이 사실은, 이 증명과 함께, 1736년에 처음 그래프 이론(graph theory)의 연구를 시작했던 쾨니히스베르크의 일곱 다리(Seven Bridges of Königsberg)에 대한 레온하르트 오일러(Leonhard Euler)의 논문에서 나타났습니다.

Counting trees

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 의 구별되는 꼭짓점의 집합으로 형성될 수 있는 서로 다른 트리(trees)의 숫자 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle T_n} 은 무엇입니까? 케일리의 공식(Cayley's formula)은 답 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle T_n=n^{n-2}} 을 제공합니다. Aigner & Ziegler (1998)는 이 사실의 네 가지 증명을 나열합니다; 그들은 짐 피트먼에 의한 이중 세는 증명, 네 번째에 대해 "그것들 중 가장 아름다운 증명"이라고 씁니다.

Pitman의 증명은 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 꼭짓점을 뿌리 트리(rooted tree)를 그것으로부터 형성하기 위해 빈 그래프(empty graph)에 추가될 수 있는 방향화된 가장자리의 수열의 개수를 두 가지 다른 방법으로 계산합니다. 그러한 수열을 형성하는 한 가지 방법은 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle T_n} 가능한 비-뿌리 트리 중 하나로 시작하여, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 꼭짓점 중 하나를 루트로 선택하고, 그것의 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n-1} (방향화된) 가장자리를 추가하기 위해 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle (n-1)!} 가능한 수열 중 하나를 선택하는 것입니다. 그러므로, 이러한 방법으로 형성될 수 있는 수열의 총 수는 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle T_n n(n-1)! = T_n n!} 입니다.

이들 가장자리 수열을 세는 또 다른 방법은 가장자리를 하나씩 빈 그래프에 추가하고, 각 단계에서 사용할 수 있는 선택의 수를 세는 것입니다. 만약 우리가 이미 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n-k} 가장자리의 모음을 더해 왔으면, 이들 가장자리에 의해 형성된 그래프가 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle k} 트리를 갖는 뿌리 숲(forest)이 되도록, 다음 가장자리에 대해 더하려는 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n(k-1)} 선택이 있습니다: 그것의 시작 꼭짓점은 그래프의 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle n} 꼭짓점 중 임의의 하나일 수 있고, 그것의 끝나는 꼭짓점은 시작하는 꼭짓점을 포함하는 트리의 뿌리가 아닌 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle k-1} 뿌리 중 임의의 하나일 수 있습니다. 그러므로, 만약 우리가 첫 번째 단계, 두 번째 단계, 등의 선택 수를 함께 곱하면, 전체 선택의 개수는

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.}

가장자리 수열의 숫자에 대해 이들 두 공식을 같게 하면 케일리의 공식을 초래합니다:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \displaystyle T_n n!=n^{n-2}n!}

및

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle \displaystyle T_n=n^{n-2}.}

Aigner와 Ziegler가 설명하는 것처럼, 그 공식과 그 증명은 임의의 k에 대해 k 트리를 갖는 뿌리 숲의 수를 세기 위해 일반화될 수 있습니다.

Double counting (proof technique)

Examples

Multiplication (of natural numbers) commutes

Forming committees

Handshaking lemma

Counting trees

See also

Additional examples

Related topics

References