비주사적 증거

Bijective proof

결합학에서, 비주사적 증명은 한 세트를 다른 세트에 매핑하는 비주사적 함수를 발견함으로써, 두 세트의 원소가 동등하게 많거나, 두 조합 클래스의 세트가 동일한 크기를 가지고 있음을 증명하는 증명 기법이다.이 기법은 특정 세트의 요소 수에 대한 공식을 찾는 방법으로 유용할 수 있으며, 이를 카운트하기 쉬운 다른 세트와 일치시킨다.또한, 편향 자체의 본질은 종종 두 세트 모두에 대한 강력한 통찰력을 제공한다.

기본 예시

이항계수의 대칭성 입증

이항계수의 대칭에는 다음과 같이 명시되어 있다.

즉, n 크기 집합에 n - k 크기 집합에 n - k 사물의 조합이 있는 만큼 k 사물의 조합이 정확히 많다는 뜻이다.

주관적인 증거.

증거의 핵심 아이디어는 간단한 예에서 이해할 수 있다: n명의 아이들 그룹에서 아이스크림 콘으로 보상을 받을 k명의 아이들을 선택하는 것은, 아이스크림 콘을 거절당할 n - k명의 아이들을 선택하는 것과 정확히 같은 효과를 갖는다.

보다 추상적이고 일반적으로, 두 수량이 동일하다고 주장하는 수량은 n-요소 집합 S의 크기 k와 n - k의 하위 집합 각각을 계산한다.[1]A를 S의 모든 k-element 하위 집합의 집합으로 하고, A 집합의 크기는( k) Let B be the set of all n−k subsets of S, the set B has size . There is a simple bijection between the two sets A and B: it associates every k-element subset (that is, a member of A) with its complement, which contains precisely the remaining n − k elements of S, and hence is aB의 회원좀 더 형식적으로, 이것은 기능 표기법, 즉 f(X)에 의해 정의된 f : A → B = X에 대해 S의 모든 k-element 부분집합과 S에서 취한 보충수로서c 쓸 수 있다.f가 편향적이라는 것을 나타내려면 먼저 f(X1) = f(X2), 즉 X = X라고1c2c 가정한다.각1 측면의 보완점(S)을 이용하여, 집합의 보완점이 원래 집합이라는 사실을 이용하여 X = X를2 구한다.이것은 f가 일대일임을 보여준다.이제 B에 있는 S의 n-k-element subset을 취하라, Y라고 말한다.S, Y의c 그것의 보어는 A의 요소인 k-element subset이다.f(Yc) = (Yc)c = Y이기 때문에 f는 또한 위에 있고 따라서 편향된다.이 유한 집합들 사이에 바이어싱의 존재가 동일한 크기, 즉( )=( -k) 을(를) 갖는다는 것을 보여주기 때문에 이제 결과가 뒤따른다

기타 예

이항계수 정체성에만 국한된 것은 아니다.문제의 복잡성이 증가함에 따라, 주관적인 증거는 매우 정교해질 수 있다.이 기법은 조합론, 그래프 이론, 숫자 이론과 같은 이산 수학 영역에서 특히 유용하다.

조합학에서 가장 고전적인 비주사적 증명 사례로는 다음과 같은 것들이 있다.

참고 항목

참조

  1. ^ Mazur, David R. (2010), Combinatorics / A Guided Tour, The Mathematical Association of America, p. 28, ISBN 978-0-88385-762-5

추가 읽기

외부 링크