주차 문제와 케일리의 공식, 그리고 조합적 증명

다음과 같은 상황을 생각한다. 대의 자동차들이 있고, 개의 주차 스팟 이 일렬로 주어져있다. 각각의 자동차마다 선호하는 주차스팟이 하나씩 있으며, 번째 자동차의 선호 스팟을 라 한다. 이 자동차들이 일렬로 들어가며 각각 차례로 원하는 스팟에 주차하되, 만약 그곳에 다른 차가 이미 있었다면 다음 스팟에 주차를 시도한다고 한다. (만약 다음 스팟에도 차가 있으면 그 다음 스팟을 보는 식) […]

Read More 주차 문제와 케일리의 공식, 그리고 조합적 증명

소수의 무한성

소수는 무수히 많이 존재한다. 정수론에서 가장 근본에 위치하는 기본적인 명제이면서 수학의 역사에서 가장 중요한 역할을 차지하는 결과물 중의 하나인 명제이다. 유클리드가 귀류법으로 증명한 이래 수많은 다양한 증명이 등장했는데, 피타고라스의 정리가 200가지가 넘는다해도 사실 많은 증명들은 다소 대동소이한 경우가 많은 반면 이쪽은 정말 그야말로 완벽히 다른 분야의 맥락에서 증명되는 경우도 많아 더 의미가 있다고 봄. 대부분 […]

Read More 소수의 무한성

조합적으로 증명하는 삼각함수식

탄젠트와 시컨트의 정의만 알면 바로 증명되는 항등식인데 이것을 조합적으로 보일 수 있다. 그를 위해선 몇 가지 해석적인 작업이 조금 필요함. 일전에 “의 조합적 증명“에서 소개했던 교대순열이란게 있다. 교대순열은 를 만족시키는 순열. 부등호가 < > < > … 으로 정의되는 경우도 있으며 위 글 역시 그러한데, 여기서는 > < > < …으로 정의하고, < > < > […]

Read More 조합적으로 증명하는 삼각함수식

두 집합 사이의 거리에 대한 두 증명

두 유한집합 에 대해, 의 값을 다음과 같이 정의한다. (단 둘 다 공집합인 경우는 제외한다) 이 값은 두 집합 사이의 상관관계를 나타내는 척도가 된다. 예컨대 이면 0이 되고, 인 경우는 1이 되는 등, 상대적으로 겹치는 정도가 클 수록 0에 가까워져 일종의 거리처럼 생각할 수 있게 된다. 이것이 실제로 수학에서 정의되는 거리(metric)가 되려면 다음과 같은 삼각부등식이 […]

Read More 두 집합 사이의 거리에 대한 두 증명

π < 2φ의 조합적 증명

황금비 에 대해 가 성립한다는 것을 조합적으로 증명한 논문[1]을 읽었다. (타이틀이 자동적으로 대문자화되는 바람에 Π < 2Φ이 되어버림… 그리스 문자까지 변환할 줄은 몰랐다;) 요는 피보나치 수 과 오일러 수 (Eulerian number 말고 Euler number. 보통 교대순열(alternating permutation)의 개수로 정의된다)의 곱이 n!보다 크거나 같고, 과 이기 때문에 으로 증명이 끝난다는 것. 여기서 을 조합적으로 보인 것이다. […]

Read More π < 2φ의 조합적 증명