예제 5.38 그림과 같은 모양의 종이에 서로 다른 가지 색을 사용하여 색칠하려고 한다 이웃한 사. 다리꼴에는 서로 다른 색을 칠하고 맨 위의 사다리꼴과 맨 아래의 사다리꼴에 서로 다른 색을 칠한, 다. 개의 사다리꼴에 색을 칠하는 방법의 수를 구하시오.
예제 5.39 를 모두 사용하여 만든 다섯 자리 문자열 중에서 다음 세 조건을 만족시키 는 문자열의 개수는?
가 첫째 자리에는
( ) 가 올 수 없다.
나 셋째 자리에는
( ) 도 올 수 없고 도 올 수 없다.
다 다섯째 자리에는
( ) 도 올 수 없고 도 올 수 없다.
① ② ③ ④ ⑤
예제 5.40
박자는 4분음을 한 박으로 하여 한 마디가 네 박으로 구성된다 예를 들어.
박자 한 마디는 분 음표( )♩ 또는 분 음표( )♪ 만을 사용하여 ♩♩♩♩ 또는 ♪♩♪♩♩와 같이 구성할 수 있다. 분 음표 또는 분 음표만 사용하여
박자의 한 마디를 구성하는 경 우의 수를 구하시오.
제 6 장
점화식
6.1 점화식
점화식
양의 정수 에 대하여 무한수열 가 다음 두 조건을 만족시키는 무한수열이라 하자.
(1) ⋯ 의 값이 미리 주어져있다.
각
(2) ⋯에 대하여 는 ⋯ 의 값에 따라 결정된다.
이 때, ⋯ 의 값을 의 초기조건이라 하고 (2)를 의 점화식이라 한다.
예제 6.1 1과 로 이루어진2 자리수 중 이 연속으로 나오지 않는 수의 개수를1 이라 할 때, 에 대한 점화식을 구하시오 또한 연속으로 세 번 이상은 나오지 않는 수의 개수를. 1 이라 할 때, 에 대한 점화식을 구하시오.
예제 6.3 베나레스에는 세계의 중심이 있고 그 곳에는 아주 큰 사원이 있다 이 사원에는 높이. 정도 되는 다이아몬드 막대 개가 있다 그 중 하나는 장의 순금으로 된 구멍 뚫린 원판을
50cm 3 . 64
크기가 큰 것부터 아래로 놓여있다 원판을 한 장씩 옮기어 빈 막대 중 어느 한 곳으로 옮기되 한 번. 에 한 장씩 옮겨야 하고 절대로 작은 원판 위에 큰 원판을 올려 놓을 수 없다고 한다 원판 한 장을. 옮기는데 초가 걸린다고 할 때 원판을 모두 옮기는데 걸리는 최소시간을 구하시오1 . .
예제 6.4 다음 그림과 같은 규칙으로 구슬이 배열되어 있다.
단계에서의 구슬의 개수를 이라 할 때 두 항, 과 사이의 점화관계(recurrence 를 구하고
relation) , 을 에 관한 다항식으로 나타내시오.
예제 6.5 다음과 같이 정의된 무한수열 를 결정하시오.
(1) ⋯
(2) ≡ ≤ ⋯
동차선형점화식 무한수열 가
⋯ ⋯
와 같은 꼴의 점화식을 만족할 때 이 점화식을, 차의 동차선형점화식이라 한다 또한.
차의 다항식
⋯
를 의 고유다항식이라 하고 을 의 고유방정식이라 한다.
정리 6-1 동차선형점화식
무한수열 의 고유다항식이 이고 고유방정식의 해가 라 할 때, 다음이 성립한다.
(1) ≠ 이면 ⋯이다.
(2) 이면 ⋯이다.
예제 6.6 다음과 같이 정의된 점화식으로부터 무한수열 를 결정하시오.
(1) ⋯
(2) ⋯
정리 6-2비동차선형점화식
비동차선형점화식
⋯ ⋯
을 만족하는 무한수열의 일반해는 다음과 같다.
동차선형점화식의 일반해를 구한다
(1) .
비동차선형점화식의 특수해를 한다
(2) .
에서 구한 해를 결합하여 비동차선형점화식의 일반해를 구한다
(3) (1),(2) .
특히, 가 차 다항식이면 (2)의 특수해고 차 다항식으로 인 형태이면 의 형태로 두고 특수해를 구한다.
예제 6.7 다음과 같이 정의된 점화식으로부터 무한수열 를 결정하시오.
(1) ⋯
(2) ⋯
(3) ⋯
6.2 생성함수
생성함수
수열 ⋯ 에 대하여,
∞
으로 정의한 함수를 생성함수(generating 라고 한다 일반적으로 확률분야에서 평균이나 분산을 구할 때 자주 쓰는
funtion) . ,
수이다 또한 방정식.
은 음이 아닌 정수)
의 음이 아닌 정수해의 개수를 구할 때도 이용할 수 있다. ≤ ≤ 이므로 다항식
⋯ ⋯ ⋯
의 전개식의 항 중에서 의 계수는 첫 번째 인수에서의 두 번째 인수에서의 , 세 번째 인수에서의 의 곱 이 이 되는 가지 수이므로 우리가 구하고자 하는 해의 수는 의 전개식의 의 계수가 된다 즉. 의 계수 이 구하는 값이다.
예제 6.8 다음과 같이 정의된 수열 의 생성함수를 구하시오.
(1) ⋯
(2) ⋯
(3) ⋯
(4)
⋯예제 6.9 수열 의 생성함수가 아래와 같을 때 수열, 을 구하시오.
(1) (2) (3)
(4)
예제 6.10 세 종류의 물건을 중복을 허락해서 뽑는다고 할 때 각각, 1개 이상 뽑히 도록 개를 선택하는 방법의 수를 이라고 할 때, ⋯ 의 생성함수를 이용하여
을 구하여라.
예제 6.11 생성함수를 이용하여 30개의 똑같은 공을 개의 서로 다른 상자에 넣을 때 첫 상자에는5 , 개 이하가 되도록 넣는 방법의 수를 구하시오
10 .
예제 6.12 생성함수를 이용하여 다음과 같이 정의된 점화식으로부터 무한수열 를 결정하시오.
⋯
