본문 바로가기

전체 글58

6.3. 램지 수(Ramsey number) 램지 수(Ramsey number) 특히, $R(p,q)$인 '램지 수'에 대해 관심이 많다. 이 경우, 유한개의 점이 있고 임의의 두 점을 한 개의 선분으로 연결한 것을 '클리크'로 생각하면 된다. $k-$클리크라 하면 정확히 $k$개의 점을 갖는 클리크를 뜻한다. 따라서 $R(p,q)$의 값은 빨간색 $p-$클리크 또는 파란색 $q-$클리크가 존재하도록 하는 가장 작은 자연수 $m-$클리크를 의미한다. 즉, $m-$클리크의 각 선분들을 $2$개의 색, 빨강과 파랑으로 무작위로 칠했을때 빨간색 $p-$클리크 또는 파란색 $q-$클리크를 포함한다는 것이다. 예를 들어, $R(3,3)=6$이다. $6-$클리크는 빨강과 파랑으로 무작위로 칠했을때 빨간색의 $3-$클리크 또는 파란색 $3-$클리크를 반드시 포.. 2022. 9. 18.
6.2 램지 정리(Ramzey's Theorem) '비둘기집 원리'를 일반화시킨 '램지 정리'를 살펴본다. 이 정리의 이해가 어려울 수도 있다. 그런데, 한 번 시도해볼 만하다. 자연수 $\boldsymbol{n}$, $\boldsymbol{t}$, $q_1,q_2,\cdots,q_n$ 가 주어졌다고 하자. 다음 조건을 만족시키는 최소 자연수 $R(q_1,q_2,\cdots,q_n; n, t)$가 존재한다. 임의의 집합 $S$의 "크기가 $t$인 부분집합($t-$부분집합)들의 집합"을 $\chi(S,t)$라고 표기하자. $\chi(S,t)$의 $n$조각으로의 분할 $\chi(S,t) = E_1 \cup E_2 \cup \cdots \cup E_n$, $(\forall i, j, \ E_i \cap E_j =\varnothing)$ 에 대하여 $|S| \.. 2022. 9. 18.
6.1 비둘기집 원리 제6장에서는 특정 종류의 수량이나 패턴, 혹은 배치와 관련된 문제를 다루기 위한 조합론의 근본적인 원리를 살펴보려 한다. 만일 비둘기가 $n$마리 있고 비둘기집이 $(n-1)$개가 있다면, 비둘기들이 비둘기 집을 찾아 들어가는 모든 가능한 경우를 고려할 때, 우리는 확신에 가득차며, 명백한 하나의 사실을 발견하게 된다. "적어도 어느 한 비둘기 집에는 2마리 이상의 비둘기가 있다." 비둘기가 $n$이상으로 충분히 많다면 이런 일은 반드시 발생한다. 그러므로 우리가 궁금한 것은 이런 일이 일어나는 '최소수의 존재'이다. 비둘기집 원리는 어느 비둘기집에 두 마리 이상의 비둘기가 있는지에 대해서는 알려지지 않는다. 단지 그런 수량을 갖는 비둘기 집의 존재성을 보장한 뿐이다. 즉, 특정한 수량의 존재성과 관련한.. 2022. 9. 18.
5.2 집합의 분할 원소의 개수가 유한개인 집합을 공집합이 아니고 서로소인 몇 개의 부분집합으로 나누는 것을 '집합의 분할'이라 한다. 원소의 개수가 $n$인 집합을 $k(1\leq k\leq n)$개의 부분집합으로 분할하는 방법의 수를 $S(n,k)$와 같이 나티내자. 이때 원소의 개수가 $n$인 집합을 분할하는 모든 방법의 수 $s(n)$는 $s(n) = S(n,1) + S(n,2) + \cdots+ S(n,n)$ 이다. $S(n,k)$는 서로 다른 $n$개의 공을 서로 같은 상자 $k$개에 빈 상자가 없도록 넣는 방법의 수와 같다. 두 자연수 $n,k(1 2022. 9. 18.
5.1 자연수의 분할 자연수 분할은 일종의 '블럭 놀이'로 생각할 수 있다. $n$개의 정사각형 모양의 납작한 블럭들을 서로 변끼리 서로 연결하여 어떤 모양을 만든다. 이때 그 모양에 따라 자연수 $n$의 분할들이 만들어진다. 이러한 블럭 놀이를 통해 얻을 수 있는 하니의 원리가 있다. "자연수 '$n$을 $k$이하의 자연수로 분할하는 방법의 수'는 '자연수 $n$을 $k$개 이하의 자연수로 분할하는 방법의 수'와 같다." 위의 문장에서 $n$을 $k$이하의 자연수로 분할하는 방법의 수와 자연수 $n$을 $k$개 이하의 자연수로 분할하는 방법의 수는 분명 다른 문장이다. 다음 그림을 통해 위의 사실을 이해할 수 있겠는가? 7을 3이하의 자연수로 분할하는 방법은 다음과 같다. 7 = 3+3+1 = 3+2+2 = 3+2+1+1 .. 2022. 9. 18.
4.3 지수 생성함수 앞에서 다룬 문제들의 생성함수는 대상의 정렬 순서를 고려하지 않는 경우였다. 정렬 순서를 고려한 대상의 배열을 계산할 때 유용한 생성함수는 무엇일까? 결론부터 얘기하면 그것은 다음의 '지수 생성함수'다!!! $\displaystyle A'(x) = a(0) + a(1) \cdot \left(\frac{x}{1!}\right) + a(2) \cdot \left(\frac{x^2}{2!}\right) + a(3) \cdot \left(\frac{x^3}{3!}\right) + \cdots$ 위의 생성함수의 계수 $a(r)$은 $'r$개의 대상을 나열하는 방법의 수'이다. 우리는 다음 형태의 생성함수에서 $A(x) = a(0) + a(1)x^1 +a(2)x^2 + a(3)x^3 + \cdots$ $x^r (r.. 2022. 9. 17.
4.2 생성함수의 계수 생성함수의 계수 $a(r)$을 중복집합 $\left\{\infty a, \infty b, \infty c \right\}$로부터 $r$개의 원소를 고르는 방법의 수라 하면 수열 $a(r)$에 대한 생성함수는 다음과 같음을 알 수 있다. $(1+x+x^2+\cdots)(1+x+x^2+\cdots)(1+x+x^2+\cdots)$ 이것의 계수를 일일히 전개하여 구하는 것은 꽤 번거롭다. 다른 수학적 기법은 없을까? 위의 생성함수의 계수 $a(r)$를 계산하기 위하여 이미 잘 알려진 여러 가지 대수적 기법을 활용해보자. $|x|＜1$일 때, 우리는 다음이 성립함을 알고 있다. $\displaystyle 1 + x + x^2+ x^3 + \cdots = \frac{1}{1-x}$ 이때 $\displaystyle .. 2022. 9. 17.
4.1 생성함수 셈하는 기법을 개발하는 것이 조합론에서 중요한 목표 중의 하나였다는 사실을 되새기자. 제4장에서는 셈하기에서 자주 이용되는 가장 강력한 도구 중에 하나인 '생성함수'에 대해 알아본다. 이 장의 내용은 일반 독자에게 생소하고 굉장히 신기할 수도 있다. 생성함수 수열 $a(r)$을 생각한다. 여기서$ r=0, 1, 2, 3, \cdots$이다. 이 수열에 대한 '생성함수'는 다음 급수로 정의된다. $A(x) = a(0) +a(1)x^1 +a(2)x^2 +a(3)x^3 +\cdots$ 위의 식은 $x$에 관한 다항식이고 $a(r)$은 그에 대한 계수이다. 나중에 확실히 알게되겠지만, 이 계수는 어떤 셈하기 문제에 대해 의미있는 수가 된다. 쉬운 예로 이항정리 $B(1,x) = C(n,0)x^0 + C(n,1).. 2022. 9. 17.

티스토리툴바