본문 바로가기

분류 전체보기58

7.3 생성함수와 점화식 생성함수와 점화식 사이의 관련성에 대하여 생각해 본다. 생성함수를 활용하여 점화식의 일반항을 구해 보려는 것이다. 우리는 이미 Counting에 관한 문제를 해결할 때, 생성함수가 수학적 도구로서 강력한 역할을 할수 있는 예를 살펴 보았다. 생성함수는 점화식을 풀 때도 유용하게 사용된다. 이 부분에 대한 내용은 다음 예제를 통해 간단히 살펴보는 것으로 이 글의 마지막 제7장을 마무리 한다. $a(0)=1, a(n)-2a(n-1) = 2^n \ (n\geq1)$ 다음 다항식을 $A(x) = a(0) + a(1)\cdot x + a(2)\cdot x^2 + a(3)\cdot x^3 + \cdots$ 수열 $\left\{a(n)\right\}$의 생성함수라 하자. 이때, $A(x)-a(0) = a(1)\cdo.. 2022. 9. 13.
7.2 점화식의 일반항 구하기 점화식의 유형별로 일반항을 구하는 방식에 대해 논한다. 점화식의 일반항을 구하는 이론적인 절차는 보통 '선형점화식'과 '비선형점화식'으로 구분하여 진행된다. 그리고 특성방정식과 같은 생소한 용어들을 접하게 된다. 이 글에서는 일반 독자들이 쉽게 이해할 수 있도록 다음과 같은 대표적인 4가지 유형에 대해 배운다. 여기서 배운 내용들을 활용하면 이와 유사한 여러 점화식에 응용이 가능하다. (1) $a(n+1) - a(n) = f(n)$ (2) $a(n+1) = f(n) \times a(n)$ (3) $a(n+1) = k\cdot a(n) + f(n)$ (단, $f(n)$이 $k^n$꼴을 포함하지 않은 경우) (4) $a(n+2) = p\cdot a(n+1) + q\cdot a(n)$ (1)의 경우 : (1).. 2022. 9. 13.
7.1 점화식 만들기 다음의 셈하기 문제에 대해 생각해 보자. 계단을 한 칸이나 두 칸 올라 $n$개의 계단을 오르는 방법의 수를 생각한다. 이 문제는 생각보다 그리 단순하지 않다. 이 글의 이전 부분에서 배운 방법들이 크게 도움이 되지 않는다. 그래서 이 문제는 다른 방법으로 접근할 필요가 있다. $n=1$인 경우, 분명히 1가지 방법만이 존재한다. $n=2$인 경우, 한 칸씩 두번 오르는 방법과 두 칸을 한 번에 오르는 2가지 방법 밖에 없다. $n=3$인 경우는 어떨까? 이 경우도 직접 일일이 세어보면 3가지 경우가 있다. 일반적으로, $a(n)$을 $n$개의 계단을 오르는 방법의 수라고 하자. 직접 좀 더 세어 보면 다음과 같은 연속적인 수들을 찾을수 있다. $a(n) = 5, a(n) = 8, \cdots$ 그러나 .. 2022. 9. 13.
7.0 제7장의 목차 제7장의 목차는 다음과 같다. 7.1 점화식 만들기 7.1 점화식 만들기 7.1 점화식 만들기 다음의 셈하기 문제에 대해 생각해 보자. 계단을 한 칸이나 두 칸 올라 $n$개의 계단을 오르는 방법의 수를 생각한다. 이 문제는 생각보다 그리 단순하지 않다. 이 글의 이전 부분에서 배운 방법 moda-paradise.tistory.com 7.2 점화식의 일반항 구하기 7.2 점화식의 일반항 구하기 7.2 점화식의 일반항 구하기 점화식의 유형별로 일반항을 구하는 방식에 대해 논한다. 점화식의 일반항을 구하는 이론적인 절차는 보통 '선형점화식'과 '비선형점화식'으로 구분하여 진행된다. 그리고 특성방정식과 같은 moda-paradise.tistory.com 7.3 생성함수와 점화식 7.3 생성함수와 점화식 7.3.. 2022. 9. 13.
6.0 제6장의 목차 제6장의 목차는 다음과 같다. 6.1 비둘기집 원리 6.1 비둘기집 원리 6.1 비둘기집 원리 제6장에서는 특정 종류의 수량이나 패턴, 혹은 배치와 관련된 문제를 다루기 위한 조합론의 근본적인 원리를 살펴보려 한다. 만일 비둘기가 $n$마리 있고 비둘기집이 $(n-1)$개가 있다면, 비둘기들 moda-paradise.tistory.com 6.2 램지정리(Ramzey's Theorm) 6.2 램지정리(Ramzey's Theorem) 6.2 램지정리(Ramzey's Theorem) '비둘기집 원리'를 일반화시킨 '램지 정리'를 살펴본다. 이 정리의 이해가 어려울 수도 있다. 그런데, 한 번 해볼만하다. 자연수 $\boldsymbol{n}$, $\boldsymbol{t}$, $q_1,q_2,\cdots,q_n.. 2022. 9. 13.
5.0 제5장의 목차 제5장의 목차는 다음과 같다. 5.1 자연수의 분할 5.1 자연수의 분할 5.1 자연수의 분할 자연수 분할은 일종의 '블럭 놀이'로 생각할 수 있다. $n$개의 정사각형 모양의 납작한 블럭들을 서로 변끼리 서로 연결하여 어떤 모양을 만든다. 이때 그 모양에 따라 자연수 $n$의 분할들이 만 moda-paradise.tistory.com 5.2 집합의 분할 5.2 집합의 분할 5.2 집합의 분할 원소의 개수가 유한개인 집합을 공집합이 아니고 서로소인 몇 개의 부분집합으로 나누는 것을 '집합의 분할'이라 한다. 원소의 개수가 $n$인 집합을 $k(1\leq k\leq n)$개의 부분집합으로 분할하는 방 moda-paradise.tistory.com 분할은 둘 또는 그 이상으로 나누어 쪼개는 것을 의미한다. .. 2022. 9. 13.
4.0 제4장의 목차 제4장의 목차는 다음과 같다. 4.1 생성함수 4.1 생성함수 4.1 생성함수 셈하는 기법을 개발하는 것이 조합론에서 중요한 목표 중의 하나였다는 사실을 되새기자. 제4장에서는 셈하기에서 자주 이용되는 가장 강력한 도구 중에 하나인 '생성함수'에 대해 알아본다. 이 moda-paradise.tistory.com 4.2 생성함수의 계수 4.2 생성함수의 계수 4.2 생성함수의 계수 생성함수의 계수 $a(r)$을 중복집합 $\left\{\infty a, \infty b, \infty c \right\}$로부터 $r$개의 원소를 고르는 방법의 수라 하면 수열 $a(r)$에 대한 생성함수는 다음과 같음을 알 수 있다. $(1+x+x^2+\cdo.. moda-paradise.tistory.com 4.3 지수 생성.. 2022. 9. 13.
3.5 부부문제 "남자와 여자가 교대로 앉고 임의의 아내는 자신의 남편 옆에는 앉지 않도록, $n(n\geq3)$쌍의 결혼한 부부들을 원탁에 둘러앉히는 방법의 수를 구하여라." 위의 문제를 해결하기 전에 우선 다음 문제에 대해 생각해 보자. "$X=\big\{1, 2, \cdots, n\big\}$에 대하여 $X$의 $r-$부분집합들 중에 연속한 자연수를 포함하지 않는 것의 개수는 $C(n-r-1, r) \ (0\leq r\leq n-r+1)$ 이다." 예를 들어, $X=\big\{1,2,\cdots,7\big\}$을 생각해보자. 연속된 자연수를 포함하지 않는 $X$의 모든 $3-$부분집합을 다 써보면 다음과 같이 $10$개이고, $C(7-3+1, 3)=10$이다. $\big\{1,3,5\big\}, \big\{1,3,.. 2022. 9. 13.

티스토리툴바