본문으로 건너뛰기

7. Advanced Counting Techniques

7.1. Recurrence Relations​

Recurrence Relations​

모든 Integer nn에 대해 n≥n0n\geq n_0이고 n0≥0n_0\geq 0인 {an}\{a_n\}의 Recurrence relation(점화식)은 ana_n을 Sequence의 이전 Term(a0,a1,…,an−1a_0, a_1, \dots , a_{n-1})에 대한 Express로 표현하는 Equation이다.
Sequence가 Recurrence relation을 만족한다면 Sequence를 Solution of a recurrence relation(재귀 관계의 해)라고 부른다.

팁

Example

Sequence {an}\{a_n\}가 an=an−1−an−2(n=2,3,4,… )a_n=a_{n-1}-a_{n-2}(n=2,3,4, \dots)를 만족할 때 a0=3,a1=5a_0=3, a_1=5일 때 a2,a3a_2, a_3의 Value

  • Solution
    a2=a1−a0=5−3=2,a3=a2−a1=2−5=−3a_2=a_1-a_0=5-3=2, a_3=a_2-a_1=2-5=-3으로 구할 수 있다.
팁

Example

an=2an−1−an−2a_n=2a_{n-1}-a_{n-2}가 n=2,3,4,…n=2,3,4,\dots에서 Recurrence relation 성립 여부

  • Solution
    Nonnegative integer nn에 대해 an=3na_n=3n이라고 가정하면 n≥2n\geq 2일 때 2an−1−an−2=2(3(n−1))−3(n−2)=3n=an2a_{n-1}-a_{n-2}=2(3(n-1))-3(n-2)=3n=a_n이 성립한다.

    Nonnegative integer nn에 대해 an=2na_n=2^n이라고 가정하면 n≥2n\geq 2일 때 2an−1−an−2=2(2(n−1))−2(n−2)=2n−2n−2≠an2a_{n-1}-a_{n-2}=2(2(n-1))-2(n-2)=2^n-2^{n-2}\not=a_n으로 성립하지 않는다.
    Nonnegative integer nn에 대해 an=5a_n=5라고 가정하면 n≥2n\geq 2일 때 2an−1−an−2=2(5)−5=5=an2a_{n-1}-a_{n-2}=2(5)-5=5=a_n으로 성립한다.

Sequence의Initial condition은 Recurrence relation이 적용되기 이전의 Term들을 지정한다.
Initial condition은 Sequence를 고유하게 결정한다.

Modeling with Recurrence Relations​

팁

Example

Compound Interest
연 11%의 복리이자를 제공하는 은행의 저축 계좌에 10000원을 예치할 경우 30년 후 계좌 금액

  • Solution
    nn년 후 계좌 금액을 PnP_n으로 정의할 경우 nn년 후 계좌 금액은 n−1n-1년 후 계좌 금액에 nn년 차 이자를 더한 것이므로 {Pn},Pn=Pn−1+0.11Pn−1=1.11Pn−1,P0=10000\{P_n\}, P_n=P_{n-1}+0.11P_{n-1}=1.11P_{n-1}, P0=10000이다.
    Initial condition을 대입하여 Pn=(1.11)n⋅10000P_n=(1.11)^n\cdot 10000임을 알 수 있다.
    Recurrence relation과 Induction hypothesis에 따라 Pn+1=(1.11)Pn=(1.11)n+1⋅10000P_{n+1}=(1.11)P_n=(1.11)^{n+1}\cdot 10000이다.
    따라서 30년 후 계좌 금액은 P30=(1.11)30⋅10000=228922.97P_{30}=(1.11)^{30}\cdot 10000=228922.97로 구할 수 있다.
팁

Example

Rabbits and the Fibonacci Numbers
한 쌍의 어린 토끼(수컷, 암컷)가 섬에 놓이고 토끼 한 쌍은 2개월이 지나면 각 토끼 쌍은 매달 새로운 쌍을 생산할 때 nn개월 후 섬에 있는 토끼 쌍의 수

  • Solution
    nn개월 후 토끼 쌍의 수를 fnf_n으로 나타낼 때 fnf_n은 Fibonacci sequence의 Term임을 증명할 수 있다.
    첫 달이 끝날 때 토끼 쌍의 수 f1=1f_1=1, 두 번째 달이 끝날 때 역시 f2=1f_2=1이다.
    두 달이 지난 토끼 쌍만 번식하므로 fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}이다.
    즉, nn개월 후 섬에 있는 토끼 쌍의 수는 nn번째 Fibonacci number가 된다.
팁

Example

The Tower of Hanoi
3개의 기둥에 다양한 크기의 원판으로 구성되어 있으며 첫 번째 기둥에 내림차순으로 원판들이 쌓여 있을 때 원판은 한 번에 하나, 다른 기둥으로만 옮길 수 있고 더 큰 원판이나 바닥에만 원판을 놓을 수 있을 때 nn개의 원판을 세 번째 기둥에 모두 다 옮기는 데 필요한 이동 횟수

  • Solution
    HnH_n을 nn개의 원판이 있는 The tower of hanoi의 해결 이동횟수라고 할 때 이전에 이동시킨 원판의 이동횟수의 두 배 + 1회가 해결 이동횟수임을 알 수 있다.
    즉 Hn=2Hn−1+1H_n=2H_{n-1}+1이고 H1=1H_1=1이 Initial condition이다.
    Hn=2Hn−1+1=2(2Hn−2+1)+1=22Hn−2+2+1=22(2Hn−3+1)+2+1=23Hn−3+22+2+1⋯=2n−1H_n=2H_{n-1}+1\\=2(2H_{n-2}+1)+1=2^2H_{n-2}+2+1\\=2^2(2H_{n-3}+1)+2+1=2^3H_{n-3}+2^2+2+1\\ \cdots \\ = 2^n-1
    로 H1H_1에서도 성립하는 Formula를 생성할 수 있다.
팁

Example

Codeword Enumeration
0이 짝수 개인 경우에만 10진 Number string을 유효한 Codeword로 간주할 때 ana_n이 유효한 nn자릿수 10진 Codeword의 가짓수 일 때 ana_n의 Recurrence relation

  • Solution
    먼저 a1a_1은 0을 제외한 한자리 수 이므로 9이다.
    이 때 유효한 Codeword에 유효하지 않은 Codeword를 붙여 Codeword로 만들 수 있다.
    즉 n−1n-1자리 Codeword에 Codeword가 아닌(1~9)를 붙이거나 Codeword가 아닌 Number string에 0을 붙여 Codeword를 만들 수 있다.
    전자는 9an−19a_{n-1}이고 후자는 10n−1−an−110^{n-1}-a_{n-1}이다.
    따라서 an=9an−1+(10n−1−an−1)=8an−1+10n−1a_n=9a_{n-1}+(10^{n-1}-a_{n-1})=8a_{n-1}+10^{n-1}임을 구할 수 있다.
팁

Example

n+1n+1개의 숫자 x0,x1,…,xnx_0, x_1, \dots, x_n의 Product의 순서를 지정하기 위해 괄호 치는 방법의 수 CnC_n에 대한 Recurrence relation

  • Solution
    CnC_n의 Recurrence relation을 도출하기 위해 x0⋅x1⋅...⋅xnx_0\cdot x_1 \cdot ... \cdot x_n의 Product에서 하나의 ⋅\cdot이 괄호 사이에 나와 있음을 인지해야 한다.
    예시로 C2=2C_2=2일 때 (x0⋅x1)⋅x2, x0⋅(x1⋅x2)(x_0\cdot x_1)\cdot x_2,\ x_0\cdot (x_1\cdot x_2)로 확인 가능하다.
    즉, 마지막 연산은 어떠한 수 사이에 Operation(⋅\cdot)이 존재하므로 괄호 삽입 방법 수는 Cn=C0Cn−1+C1Cn−2+⋯+Cn−2C1+Cn−1C0C_n=C_0C_{n-1}+C_1C_{n-2}+\cdots+C_{n-2}C_1+C_{n-1}C_0이므로 ∑k=0n−1CkCn−k−1\sum_{k=0}^{ n-1}C_kC_{n-k-1}임을 알 수 있다.
    Initial term C0=C1=1C_0=C_1=1임을 확인해 CnC_n의 Recurrence relation은 C(2n,n)n+1\frac{C(2n, n)}{n+1}가 성립함을 알 수 있다.
    추가적으로 위 Sequence {Cn}\{C_n\}은 Catalan number의 Sequence이다.

7.2. Solving Linear Recurrence Relations​

Linear homogeneous recurrence relation of degree(차수의 선형 동차 점화식)은 Real number c1,c2,…,ck(ck/not=0)c_1,c_2,\dots , c_k(c_k/not=0)에 대해 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}를 만족하는 Recurrence relation이다.
Sequence의 Term의 Degree는 모두 Constant이며 nn에 의해 변화하지 않기 때문에 Homogeneous(동차)이다.
ana_n이 Sequence의 이전 kk개의 Term으로 표현되기 때문에 Degree는 kk이다.
즉 Recurrence relation을 만족하는 Sequence는 Recurrence relation과 Initial condition에 의해 고유하게 결정(a0=C0,a1=C1,⋯ ,ak−1=Ck−1a_0=C_0, a_1=C_1, \cdots,a_{k-1}=C_{k-1})된다.

정보

Information

Recurrence relation Pn=(1.11)Pn−1P_n=(1.11)P_{n-1}은 Linear homogeneous recurrence relation of degree 1(1차 선형 동차 점화식), Recurrence relation fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}는 Linear homogeneous recurrence relation of degree 2, Recurrence relation an=an−5a_n=a_{n-5}는 Linear homogeneous recurrence relation of degree 5이다.

Recurrence relation an=an−1+an−22a_n=a_{n-1}+a^2_{n-2}는 Linear recurrence relation이 아니다.
Recurrence relation Hn=2Hn−1+1H_n=2H_{n-1}+1은 Homogeneous recurrence relation이 아니다.
Recurrence relation Bn=nBn−1B_n=nB_{n-1}은 Constant coefficient(상수 계수)가 없어 Linear homogeneous recurrence relation이 아니다.

Solving Linear Homogeneous Recurrence Relations with Constant Coefficients​

Linear homogeneous recurrence relation을 해결하기 위한 기본 접근법은 an=rna_n=r^n(단, rr은 Constant) 형태의 Solution을 찾는 것이다.
an=c1an−1+c2an−2+⋯+ckan−k if and only if rn=c1rn−1+c2rn−2+⋯+ckrn−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots +c_ka_{n-k}\ if\ and\ only\ if\ r^n=c_1r^{n-1}+c_2r^{n-2}+\cdots+c_kr^{n-k}
이기에 양 변을 rn−kr^{n-k}로 나누고 우항을 좌항으로 옮기면 rk−c1rk−1−c2rk−2−⋯−ck−1r−ck=0r^k-c_1r^{k-1}-c_2r^{k-2}-\cdots -c_{k-1}r-c_k=0이 된다.
따라서 Sequence {an}\{a_n\}이 an=rna_n=r^n형태일 때 rr이 Last equation의 Solution일 경우에만 이 Sequence는 Solution이 된다.
이 Equation은 Recurrence relation의 Characteristic equation(특성 방정식)이라고 하며 이의 Solution을 Characteristic root(특성 근)이라고 한다.
Characteristic root은 Recurrence relation의 모든 Solution을 위한 Explict solution(명시적 공식)을 제공하는 데 사용될 수 있다.

정보

Theorem

Real number c1,c2c_1, c_2에 대해 r2−c1r−c2=0r^2-c_1r-c_2=0의 두 개의 서로 다른 Root r1,r2r_1, r_2가 존재할 때 {an}\{a_n\}은 Recurrence relation n=0,1,2,…n=0,1,2,\dots에 대해서 an=c1an−1+c2an−2 if and only if an=α1r1n+α2r2na_n=c_1a_{n-1}+c_2a_{n-2}\ if\ and\ only\ if\ a_n=\alpha_1r_1^n+\alpha_2r_2^n인 Constant α1,α2\alpha_1, \alpha_2가 존재하며 성립

  • Proof
    이 Theorem을 증명하기 위해 r1,r2r_1, r_2가 Characteristic equation의 Root임과 α1,α2\alpha_1, \alpha_2가 Constant일 때 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n인 Sequence {an}\{a_n\}이 Recurrence relation의 Solution임을 보여야 하며, Sequence {an}\{a_n\}이 Solution일 경우 어떤 Constant α1,α2\alpha_1, \alpha_2에 대해 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n임을 보여야 한다.
    an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n일 때 Sequence {an}\{a_n\}이 Recurrence relation의 Solution임을 보이기 위해 r1,r2r_1,r_2가 r2−c1r−c2=0r^2-c_1r-c_2=0의 Root이므로 r12=c1r1+c2,r22=c1r2+c2r_1^2=c_1r_1+c_2, r_2^2=c_1r_2+c_2가 성립한다.
    위 식들을 이용하여 c1an−1+c2an−2=c1(α1r1n−1+α2r2n−1)+c2(α1r1n−2+α2r2n−2)=α1r1n−2(c1r1+c2)+α2r2n−2(c1r2+c2)=α1r1n−2r12+α2r2n−2r22=α1r1n+α2r2n=anc_1a_{n-1}+c_2a_{n-2}=c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})\\ = \alpha_1r_1^{n-2}(c_1r_1+c_2)+\alpha_2r_2^{n-2}(c_1r_2+c_2)\\ = \alpha_1r_1^{n-2}r_1^2+\alpha_2r_2^{n-2}r_2^2\\ = \alpha_1r_1^n+\alpha_2r_2^n \\ = a_n
    로 {an}\{a_n\}이 an=α1r1n+α2r2na_n = \alpha_1r_1^n+\alpha_2r_2^n이 Recurrence relation의 Solution임을 보여준다.
    Recurrence relation an=c1an−1+c2an−2a_n=c_1a_{n-1}+c_2a_{n-2}의 모든 Solution {an}\{a_n\}이 Constant α1,α2\alpha_1,\alpha_2와 n=0,1,2,…n=0,1,2,\dots에 대해 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n의 형태를 가지는 것을 보이기 위해 {an}\{a_n\}이 Recurrence relation의 Solution이라고 가정하고 Initial condition a0=C0,a1=C1a_0=C_0, a_1=C_1이 성립한다고 가정한다.
    Sequence {an}\{a_n\}이 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n의 형태를 가질 때 동일한 Initial condition이 만족됨을 보여주면 된다.
    즉, a0=C0=α1+α2,a1=C1=α1r1+α2r2a_0=C_0=\alpha_1+\alpha_2, a_1=C_1=\alpha_1r_1+\alpha_2r_2
    위 두 Equation을 α1,α2\alpha_1, \alpha_2로 풀 수 있다.
    첫 Equation으로 α2=C0−α1\alpha_2=C_0-\alpha_1임을 이용하여 두 번째 Equation을 전개하면 C1=α1r1+(C0−α1)r2=α1(r1−r2)+C0r2C_1=\alpha_1r_1+(C_0-\alpha_1)r_2=\alpha_1(r_1-r_2)+C_0r_2이다.
    즉 α1=C1−C0r2r1−r2\alpha_1=\frac{C_1-C_0r_2}{r_1-r_2}이고, α2=C0−α1=C0−C1−C0r2r1−r2=C0r1−C1r1−r2\alpha_2=C_0-\alpha_1=C_0-\frac{C_1-C_0r_2}{r_1-r_2}=\frac{C_0r_1-C_1}{r_1-r_2}이다.
    위 Expression들이 α1,α2\alpha_1,\alpha_2가 r1≠r2r_1\not=r_2여야 성립한다.
    따라서 α1,α2\alpha_1, \alpha_2의 이 값으로 {an}\{a_n\}은 α1r1n+α2r2n\alpha_1r_1^n+\alpha_2r_2^n를 만족하며 두 개의 Initial condition을 만족한다.
    {an},{α1r1n+α2r2n}\{a_n\},\{\alpha_1r_1^n+\alpha_2r_2^n\} 둘 다 Recurrence relation an=c1an−1+c2an−2a_n=c_1a_{n-1}+c_2a_{n-2}의 Solution이며 n=0,n=1n=0, n=1일 때의 Initial condition을 모두 만족한다.
    Linear homogeneous recurrence relation of degree 2는 두 개의 Initial condition을 가지고 유일한 Solution을 가지므로 두 Solution이 동일하다는 결론을 낼 수 있다.
    즉 모든 Nonnegative integer nn에 대해 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n이다.
    Constant coefficient를 가진 Linear homogenoeous recurrence relation of degree 2가 Constant α1,α2\alpha_1, \alpha_2에 대해 an=α1r1n+α2r2na_n=\alpha_1r_1^n+\alpha_2r_2^n 형태여야 함을 보여줌으로 증명하였다.
팁

Example

Recurrence relation an=an−1+2an−2a_n=a_{n-1}+2a_{n-2}의 a0=2,a1=7a_0=2,a_1=7일 때 Solution

  • Solution
    위 Theorem을 이용하여 r2−r−2=0r^2-r-2=0의 Root r=−1,r=2r=-1, r=2를 이용하여{an}\{a_n\}은 Recurrence relation an=α12n+α2(−1)na_n=\alpha_12^n+\alpha_2(-1)^n과 필요 충분 조건이 된다.
    a0=2=α1+α2,a1=7=α1⋅2+α2⋅(−1)a_0=2=\alpha_1+\alpha_2, a_1=7=\alpha_1 \cdot 2+\alpha_2\cdot(-1)임을 이용하여 α1=3,α2=−1\alpha_1=3, \alpha_2=-1임을 구할 수 있다.
    즉 an=3⋅2n−(−1)na_n=3\cdot 2^n-(-1)^n이 Recurrence realtion의 Solution이다.
팁

Example

위 Theorem을 활용하여 Fibonacci number의 Explicit formula 정의

  • Solution
    Fibonacci number의 Recurrence relation은 fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}임과 Initial condition이 f0=0,f1=1f_0=0, f_1=1임을 이용하여 r2−r−1=0r^2-r-1=0의 Root r=1±52r=\frac{1\pm \sqrt 5}{2}임을 알 수 있다.
    위 Theorem을 활용하여 fn=α1(1+52)n+α2(1−52)nf_n=\alpha_1(\frac{1+\sqrt 5}{2})^n+\alpha_2(\frac{1-\sqrt 5}{2})^n을 만족하는 Constant α1,α2\alpha_1,\alpha_2를 구해야 한다.
    f0=α1+α2=0,f1=α11+52+α21−52=1f_0=\alpha_1+\alpha_2=0, f_1=\alpha_1\frac{1+\sqrt 5}{2}+\alpha_2\frac{1-\sqrt 5}{2}=1을 만족하는 Constant α1=15,α2=−15\alpha_1=\frac{1}{\sqrt 5}, \alpha_2=\frac{-1}{\sqrt 5}임을 알 수 있다.
    즉 Finobacci number의 Explicit formula는 fn=15(1+52)n−15(1−52)nf_n=\frac{1}{\sqrt 5}(\frac{1+\sqrt 5}{2})^n-\frac{1}{\sqrt 5}(\frac{1-\sqrt 5}{2})^n이다.

위 Theorem은 Root가 동일할 때 활용할 수 없었다.
r0r_0가 Characteristic equation an=nr0na_n=nr_0^n의 중복 Root일 때 다른 Theorem을 활용할 수 있다.

정보

Theorem

Real number c1,c2(c2≠0)c_1, c_2(c_2 \not= 0)일 때 r2−c1r−c2=0r^2-c_1r-c_2=0가 Root를 하나만 가질 때 {an}\{a_n\}은 n−0,1,2,…n-0, 1, 2,\dots일 때 an=c1an−1+c2an−2a_n=c_1a_{n-1}+c_2a_{n-2}와 an=α1r0n+α2nr0na_n=\alpha_1r_0^n+\alpha_2nr_0^n가 필요 충분 조건의 Solution이 된다.

팁

Example

an=6an−1−9an−2,a0=1,a1=6a_n=6a_{n-1}-9a_{n-2}, a_0=1, a_1=6인 Recurrence relation의 Solution

  • Solution
    r2−6r+9=0r^2-6r+9=0의 Root는 r=3r=3 뿐이므로 an=α13n+α2n3na_n=\alpha_13^n+\alpha_2n3^n을 만족하는 Constant를 찾으면 된다.
    a0=1=α1,a1=6=α1⋅3+α2⋅3a_0=1=\alpha_1,a_1=6=\alpha_1\cdot 3+\alpha_2\cdot 3이기에 α1=1,α2=1\alpha_1=1, \alpha_2=1이다.
    즉 위 recurrence relation의 Solution인 ana_n은 an=3n+n3na_n=3^n+n3^n이다.

Degree가 2 이상이고 Characteristic equation이 서로 다른 Root를 가질 때의 Constant coefficient를 가지는 Linear homogeneous recurrence relation의 Solution을 구하는 Theorem은 아래와 같다.

정보

Theorem

Linear homogeneous recurrence relation of degree kk

  • Proof
    Order(차수)가 kk인 Linear homogeneous recurrence relation an=c1an−1+⋯+ckan−ka_n=c_1a_{n-1}+\cdots+c_ka_{n-k}에 ai=ri(1≥i≥n,r≠0)a_i=r^i(1\geq i\geq n, r\not=0)을 대입해
    rn=c1rn−1+c2rn−2+⋯+ckrn−kr^n=c_1r^{n-1}+c_2r^{n-2}+\cdots+c_kr^{n-k}가 되며 정리하여 rk−c1xk−1−⋯−ck=0r^k-c_1x^{k-1}-\cdots-c_k=0으로 나타낼 수 있다.
    이 Equation은 Order가 kk인 Equation이므로 kk개의 Root를 가지고, ck≠0c_k\not=0일 경우 Root는 0이 될 수 없다.
    Root를 r1,r2,…,rkr_1, r_2, \dots,r_k로 둘 경우 모든 ii에 대해 an=rina_n=r_i^n은 Recurrence relation의 Solution이 된다(이를 Fundamental solution(기본해)라고 한다.).
    Linear homogeneous recurrence relation의 Solution h1(n),⋯ ,hk(n)h_1(n),\cdots,h_k(n)에 대해 임의의 Constant α1,⋯ ,αk\alpha_1,\cdots,\alpha_k에 대해 H(n)=∑i=1rαihi(n)H(n)=\sum_{i=1}^r\alpha_ih_i(n)도 Solution이 된다.
    위 Characteristic equation의 서로 다른 kk개의 Root r1,⋯ ,rkr_1,\cdots,r_k에 대해 an=α1r1n+α2r2n+⋯+αkrkna_n=\alpha_1r_1^n+\alpha_2r_2^n+\cdots+\alpha_kr_k^n이고 Initial condition을 대입하여 해결할 수 있다.
팁

Example

an=6an−1−11an−2+6an−3,a0=2,a1=5,a2=15a_n=6a_{n-1}-11a_{n-2}+6a_{n-3},a_0=2,a_1=5,a_2=15

  • Solution
    r3−6r2+11r−6r^3-6r^2+11r-6이 Characteristic polynomial이다.
    Characteristic root는 (r−1)(r−2)(r−3)(r-1)(r-2)(r-3)이기에 r=1,2,3r=1,2,3이다.
    위 Theorem을 활용하여 an=α1⋅1n+α2⋅2n+α3⋅3na_n=\alpha_1\cdot 1^n+\alpha_2\cdot 2^n+\alpha_3\cdot 3^n에 해당하는 Constant α1,α2,α3\alpha_1,\alpha_2,\alpha_3에 해당하는 값을 찾기 위해 Initial condition a0,a1,a2a_0,a_1,a_2를 이용하여 a0=2=α1+α2+α3,a1=5=α1+α2⋅2+α3⋅3,a2=15=α1+α2⋅4+α3⋅9a_0=2=\alpha_1+\alpha_2+\alpha_3,a_1=5=\alpha_1+\alpha_2\cdot 2+\alpha_3\cdot 3, a_2=15=\alpha_1+\alpha_2\cdot 4+\alpha_3\cdot 9로 α1=1,α2=−1,α3=2\alpha_1=1,\alpha_2=-1,\alpha_3=2임을 알 수 있다.
    즉 Sequence {an}\{a_n\}은 an=1−2n+2⋅3na_n=1-2^n+2\cdot 3^n임을 알 수 있다.

중복 Root를 가질 때 아래의 Theorem을 활용할 수 있다.

정보

Theorem

Real number c1,c2,…,.ckc_1, c_2, \dots,.c_k에 대해 Characteristic equation rk−c1rk−1−⋯−ck=0r^k-c_1r^{k-1}-\cdots-c_k=0이 tt 개의Distinct root r1,r2,…,rtr_1,r_2,\dots,r_t의 중복도 m1,m2,…,mt(∑i=1tmi=k)m_1,m_2,\dots,m_t(\sum_{i=1}^tm_i= k)일 때 Seqaunce {an}\{a_n\}이 다음 Recurrence relation의 Solution이 된다.
an=c1an−1+c2an−2+⋯+ckan−k if and only if an=(α1,0+α1,1n+⋯+α1,m1−1nm1−1)r1n+(α2,0+α2,1n+⋯+α2m,m2−1nm2−1)r2n+⋯+(αt,0+αt,1n+⋯+αt,mt−1nmt−1)rtna_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}\ if\ and\ only\ if\ a_n=(\alpha_{1,0}+\alpha_{1,1}n+\cdots+\alpha_{1,m_1-1}n^{m_1-1})r_1^n+(\alpha_{2,0}+\alpha_{2,1}n+\cdots+\alpha_{2m,m_2-1}n^{m_2-1})r_2^n+\cdots+(\alpha_{t,0}+\alpha_{t,1}n+\cdots+\alpha_{t,m_t-1}n^{m_t-1})r_t^n가 ai,ja_{i,j}가 1≤i≤t and 0≤j≤mi−11\leq i\leq t\ and\ 0\leq j\leq m_i-1인 Constant에서 성립한다.

팁

Example

Recurrence relation an=−3an−1−3an−2−an−3,a0=1,a1=−2,a2=−1a_n=-3a_{n-1}-3a_{n-2}-a_{n-3}, a_0=1,a_1=-2,a_2=-1의 Solution

  • Solution
    Characteristic equation r3+3r2+3r+1=0r^3+3r^2+3^r+1=0의 Root r=−1r=-1뿐이다.
    (r+1)3(r+1)^3
    위 Theorem을 사용하여 an=α1,0(−1)n+α1,1n(−1)n+α1,2n2(−1)na_n=\alpha_{1,0}(-1)^n+\alpha_{1,1}n(-1)^n+\alpha_{1,2}n^2(-1)^n에 Initial condition을 대입하여 a0=1=α1,0,a1=−2=−α1,0−α1,1−α1,2,a2=−1=α1,0+2α1,1+4α1,2a_0=1=\alpha_{1,0},a_1=-2=-\alpha_{1,0}-\alpha_{1,1}-\alpha_{1,2},a_2=-1=\alpha_{1,0}+2\alpha_{1,1}+4\alpha_{1,2}에 해당하는 Constant가 α1,0=1,α1,1=3,α1,2=−2\alpha_{1,0}=1,\alpha_{1,1}=3,\alpha_{1,2}=-2임을 알 수 있다.
    Theorem에 따라 an=(1+3n−2n2)(−1)na_n=(1+3n-2n^2)(-1)^n임을 알 수 있다.

Linear Nonhomogeneous Recurrence Relations with Constant Coefficients​

Linear nonhomogeneous recurrence relation(선형 비동차 점화식)은 Linear homogeneous recurrence relation에 nn에만 의존하고 0이 아닌 Function F(n)F(n)이 추가된 것이다.

정보

Theorem

Nonhomogeneous linear recurrence relation의 Solution이 {an(p)}\{a_n^{(p)}\}일 때 an=c1an−1+c2an−2+⋯+ckan−k+F(n)a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}+F(n)으로 표현할 수 있으며 모든 Solution은 {an(h)}\{a_n^{(h)}\}가 Associated homogeneous recurrence relation(수반 동차 점화식) an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}의 Solution인 {an(p)+an(h)}\{a_n^{(p)}+a_n^{(h)}\}의 형태를 가짐

  • Solution
    an(p){a_n^{(p)}}가 Nonhomogeneous linear recurrence relation의 Solution이므로 an(p)=c1an−1(p)+c2an−2(p)+⋯+ckan−k(p)+F(n)a_n^{(p)}=c_1a_{n-1}^{(p)}+c_2a_{n-2}^{(p)}+\cdots+c_ka_{n-k}^{(p)}+F(n)임을 알 수 있다.
    {bn}\{b_n\}을 위 Recurrence relation의 Particular solution(특수해)라고 할 때 bn=c1bn−1+c2bn−2+⋯+ckbn−k+F(n)b_n=c_1b_{n-1}+c_2b_{n-2}+\cdots+c_kb_{n-k}+F(n)이다.
    bn−an(p)=c1(bn−1−an−1(p)+⋯+ck(bn−k−an−k(p))b_n-a_n^{(p)}=c_1(b_{n-1}-a_{n-1}^{(p)}+\cdots+c_k(b_{n-k}-a_{n-k}^{(p)})을 이용하여 {bn−an(p)}\{b_n-a_n^{(p)}\}이 {an(h)}\{a_n^{(h)}\}임을 알 수 있다.
    즉 모든 nn에 대해 bn=an(p)+an(h)b_n={a_n^{(p)}+a_n^{(h)}}임을 알 수 있다.
정보

Theorem

{an}\{a_n\}이 Nonhomogeneous recurrence relation an=c1an−1+⋯+ckan−k+F(n)a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+F(n)이고 F(n)=(btnt+bt−1nt−1+b1n+b0)snF(n)=(b_tn^t+b_{t-1}n^{t-1}+b_1n+b_0)s^n일 때의 Solution일 때 ss가 Associated linear homogeneous recurrence relation의 Characteristic equation의 Root가 아닐 때 (ptnt+pt−1t−1+⋯+p1n+p0)sn(p_tn^t+p_{t-1}^{t-1}+\cdots+p_1n+p_0)s^n 형태의 Solution이 존재하며 ss가 이 Characteristic equation의 중복도 mm인 Root일 때 Particular solution의 형태는 nm(ptnt+pt−1nt−1+⋯+p1n+p0)snn^m(p_tn^t+p_{t-1}n^{t-1}+\cdots+p_1n+p_0)s^n

팁

Example

an=5an−1−6an−2+7na_n=5a_{n-1}-6a_{n-2}+7^n의 모든 Solution

  • Solution
    Linear nonhomogeneous recurrence relation이므로 Associated homogeneous recurrent relation an=5an−1−6an−2a_n=5a_{n-1}-6a_{n-2}의 Solution은 an(h)=α1⋅3n+α2⋅2na_n^{(h)}=\alpha_1\cdot 3^n+\alpha_2\cdot 2^n이다.
    F(n)=7nF(n)=7^n이므로 an(p)=C⋅7na_n^{(p)}=C\cdot 7^n이다.
    C⋅7n=5C⋅7n−1−6C⋅7n−2+7nC\cdot 7^n=5C\cdot 7^{n-1}-6C\cdot 7^{n-2}+7^n을 이용하여 49C=35C−6C+4949C=35C-6C+49임을 이용해 C=4920,an(p)=(4920)7nC=\frac{49}{20},a_n^{(p)}=(\frac{49}{20})7^n임을 알 수 있다.
    따라서 모든 Solution은 an=α1⋅3n+α2⋅2n+(4920)7na_n=\alpha_1\cdot 3^n+\alpha_2\cdot 2^n+(\frac{49}{20})7^n임을 알 수 있다.
팁

Example

an=∑k=1nka_n=\sum_{k=1}^nk일 때 an=an−1+nan=a_{n-1}+n의 Solution

  • Solution
    ana_n의 Associated linear homogenoeus recurrence relation이 an=an−1a_n=a_{n-1}이다.
    an(h)=c(1)n=ca_n^{(h)}=c(1)^n=c이므로 F(n)=n=n(1)nF(n)=n=n(1)^n이고 s=1s=1은 Order가 1인 Characteristic equation의 Root이므로 Particular solution의 형태는 n(p1n+p0)=p1n2+p0nn(p_1n+p_0)=p_1n^2+p_0n이다.
    Recurrence relation에 대입하여 p1n2+p0n=p1(n−1)2+p0(n−1)+np_1n^2+p_0n=p_1(n-1)^2+p_0(n-1)+n임을 알 수 있다.
    간단히 요약하여 n(2p1−1)+(p0−p1)=0n(2p_1-1)+(p_0-p_1)=0이기에 2p1−1=0,p0−p1=0,p0=p1=122p_1-1=0,p_0-p_1=0,p_0=p_1=\frac{1}{2}임을 알 수 있다.
    즉, an(p)=n2+n2=n(n+1)2a_n^{(p)}=\frac{n^2+n}{2}=\frac{n(n+1)}{2}이 Particular solution이다.
    Original recurrence relation an=an−1+n=an(h)+an(p)=c+n(n+1)2a_n=a_n-1+n=a_n^{(h)}+a_n^{(p)}=c+\frac{n(n+1)}{2}에 대해 a1=1,c+1⋅22=c+1a_1=1, c+1\cdot\frac{2}{2}=c+1, 즉 c=0c=0이기에 an=n(n+1)2a_n=\frac{n(n+1)}{2}임을 알 수 있다.

7.3. Divide-and-Conquer Algorithms and Recurrence Relations​

Divide-and-Couquer Recurrence Relations​

Recursive algorithm이 크기 nn의 문제를 aa개의 Subproblem으로 나눠 각 하위 Subproblem의 크기가 nb\frac{n}{b}라고 할 때 Algorithm의 Conquer step에서 Subproblem의 Solution을 원래 Problem의 Solution으로 결합하기 위해 g(n)g(n)개의 추가 작업이 필요할 때 f(n)f(n)이 크기 nn의 문제를 해결하는 데 필요한 작업 수를 나타낼 때 ff는 f(n)=af(nb)+g(n)f(n)=af(\frac{n}{b})+g(n)의 관계로 나타내며 Divide-and-conquer recurrence relation이라 한다.

팁

Example

Binary search algorithm이 크기가 nn인 Search sequence에서 Element를 찾는 과정을 크기 n2\frac{n}{2}인 Search sequence에서 이 Element를 찾는 Binary search로 줄인다.
이 Reduction을 구현하기 위해 List의 어느 절반을 고를 지와 List에 남아있는 Element가 남아있는지 비교하는 것이기 때문에 nn이 짝수라면 f(n)=f(n/2)+2f(n)=f(n/2)+2가 된다.

팁

Example

Merge sort algorithm은 nn개의 Element를 정렬할 List를 n2\frac{n}{2} Element를 가진 두 개의 List로 나눈 다음 n2\frac{n}{2} Element를 가진 두 개의 Sorted list로 나눈 후 n2\frac{n}{2} Element를 가진 두개의 Sorted list를 하나의 Sorted list로 병합하는 데 nn보다 적은 비교를 사용하기에 총 Merge sort의 비교 수는 M(n)M(n)보다 작을 때 M(n)=2M(n/2)+nM(n)=2M(n/2)+n이 된다.

팁

Example

Fast multiplication of Integer는 Divide-and-conquer technique을 사용하여 효율적으로 Integer들의 Product를 구할 수 있다.
en rodml 2n2n-bit integer를 각각 nn-bit 씩 두 개의 Block으로 나누고 원래의 Product는 두 개의 2n2n-bit integer의 Product에서 nn-bit의 세 번의 Product, Sum, Bit shift로 줄어든다.

a=(a2n−1a2n−2⋯a1a0)2a=(a_{2n-1}a_{2n-2}\cdots a_1a_0)_2, b=(b2n−1b2n−2⋯b1b0)2b=(b_{2n-1}b_{2n-2}\cdots b_1b_0)_2일 때 A1=(a2n−1⋯an+1an)2A_1=(a_{2n-1}\cdots a_{n+1}a_n)_2, A0=(an−1⋯a1a0)2A_0=(a_{n-1}\cdots a_1a_0)_2, B1=(b2n−1⋯bn+1bn)2B_1=(b_{2n-1}\cdots b_{n+1}b_n)_2, B0=(bn−1⋯b1b0)2B_0=(b_{n-1}\cdots b_1b_0)_2일 때 a=2nA1+A0a=2^nA_1+A_0이고 b=2nB1+B0b=2^nB_1+B_0이므로 ab=(22n+2n)A1B1+2n(A1−A0)(B1−B0)+(2n+1)A0B0ab=(2^{2n}+2^n)A_1B_1+2^n(A_1-A_0)(B_1-B_0)+(2^n+1)A_0B_0이다.

이 Identity의 중요한 사실은 두 개의 2n2n-bit integer를 Product하는 데 nn-bit integer의 세 Product와 함께 Addition, Subtraction, Shift를 사용할 수 있음을 보여준다.
f(n)f(n)을 두 개의 nn-bit integer의 Product에 필요한 총 Bit operation 수라면 f(2n)=3f(n)+Cnf(2n)=3f(n)+Cn이 된다.

팁

Example

두 개의 n×nn\times n martrix를 Martrix multiplication의 Definition을 사용하여 n3n^3회의 Product와 n2(n−1)n^2(n-1)회의 Addition이 필요하다는 것을 보여주었다.
즉 두 n×nn\times n martrix를 계산하는 데 O(n3)O(n^3)만큼의 Operation이 필요하다.
Fast matrix multiplication은 두 nn이 짝수인 n×nn\times n matrix의 Product를 구하기 위한 Divide-and-conquer algorithm이다.
두 개의 n2×n2\frac{n}{2}\times\frac{n}{2} matrix의 Product를 7회 수행하고 n2×n2\frac{n}{2}\times\frac{n}{2} matrix의 Addition을 15회 수행하도록 Matrix multiplication을 줄일 수 있다.
f(n)f(n)을 n×nn\times n matrix끼리의 Multiplication이사용한 Operation의 수라고 할 때 nn이 짝수라면
f(n)=7f(n/2)+15n2/4f(n)=7f(n/2)+15n^2/4가 성립한다.

정보

Theorem

ff가 Increasing function이며 f(n)=af(n/b)+cf(n)=af(n/b)+c라는 Recurrence relation을 만족할 때(단 nn은 bb로 나누어떨어지고 a≥1a\geq 1, b>1b > 1, cc는 Positive integer)
a>1a>1일 경우 O(nlogba)O(n^{log_ba})이고 a=1a=1일 경우 O(log n)O(log\ n)이며
추가적으로 kk가 Positive integer일 때 n=bkn=b^k, C1=f(1)+ca−1, C2=−ca−1C_1=f(1)+\frac{c}{a-1},\ C_2=\frac{-c}{a-1}일 때 f(n)=C1nlogba+C2f(n)=C_1n^{log_ba}+C_2

  • Proof
    n=bkn=b^k이기에 g(n)=cg(n)=c로 놓으면f(n)=akf(1)+∑j=0k−1ajc=akf(1)+c∑j=0k−1ajf(n)=a^kf(1)+\sum_{j=0}^{k-1}a^jc=a^kf(1)+c\sum_{j=0}^{k-1}a^j이고 a=1a=1일 때 f(n)=f(1)+ckf(n)=f(1)+ck(k=log⁡bnk=\log_bn)
    n≠bkn\not=b^k일 때 bk<n<bk+1b^k<n<b^{k+1}인 Positive integer kk에 대해 ff는 Increasing function이기에 f(n)≤f(bk+1)=f(1)+c(k+1)=(f(1)+c)+ck≤(f(1)+c)+clog⁡bnf(n)\leq f(b^{k+1})=f(1)+c(k+1)=(f(1)+c)+ck\leq (f(1)+c)+c\log_bn
    이 성립하기에 두 경우 다 a=1a=1일 때 f(n)f(n)은 O(log⁡n)O(\log n)이다.
    a>1a>1일 때 Geometric progression의 Sum formula에 의해 ak=alog⁡bn=nlog⁡baa^k=a^{\log_bn}=n^{\log_ba}이기에 C1=f(1)+c/(a−1), C2=−c/(a−1)C_1=f(1)+c/(a-1),\ C_2=-c/(a-1)일 때 f(n)=akf(1)+c(ak−1)/(a−1)=ak[f(1)+c/(a−1)]−c/(a−1)=C1nlog⁡ba+C2f(n)=a^kf(1)+c(a^k-1)/(a-1)=a^k[f(1)+c/(a-1)]-c/(a-1)=C_1n^{\log_ba}+C_2
    가 성립한다.
    n≠bkn\not=b^k일 때 앞전과 같이 bk<n<bk+1b^k<n<b^{k+1}를 만족하는 Nonnegative integer kk에 대해 ff가 Increasing function이기에 k≤log⁡bn<k+1k\leq \log_bn<k+1이기에f(n)≤f(bk+1)=C1ak+1+C2≤(C1a)alog⁡bn+C2≤(C1a)nlog⁡ba+C2f(n)\leq f(b^{k+1})=C_1a^{k+1}+C_2\leq (C_1a)a^{\log_bn}+C_2\leq (C_1a)n^{\log_ba}+C_2가 성립하며 f(n)f(n)은 O(nlog⁡ba)O(n^{\log_ba})이다.
팁

Example

Increasing function f(n)=5f(n/2)+3f(n)=5f(n/2)+3일 때 Positive integer kk에 대해 f(2k)f(2^k)와 f(n)f(n)의 Estimate

  • Solution
    위 Theorem을 이용하여 a=5,b=2,c=3,n=2ka=5, b=2, c=3, n=2^k일 때 f(n)=5k[f(1)+3/(5−1)]+[−3/(5−1)]=5k(314)−34f(n)=5^k[f(1)+3/(5-1)]+[-3/(5-1)]=5^k(\frac{31}{4})-\frac{3}{4}이고 Increasing function이기에 Estimate를 구할 수 있고 f(n)f(n)은 O(nlog⁡5)O(n^{\log5})이다.
정보

Theorem

Master theorem
ff가 Increasing function일 때 Recurrence relation f(n)=af(n/b)+cndf(n)=af(n/b)+cn^d에 대해 Positive integer kk에 대해 n=bkn=b^k일 때 a≥1a\geq 1, b>1b>1인 Integer, cc가 Positive real number, dd가 Nonnegative real number일 때 f(n)f(n)은 a<bda<b^d일 때 O(nd)O(n^d), a=bda=b^d일 때 O(ndlog⁡n)O(n^d\log n), a>bda>b^d일 때 O(nlog⁡ba)O(n^{\log_ba})가 성립

  • Proof
    시간 있을 때 정리
팁

Example

두 개의 nn-bit integer를 곱하기 위해 Fast multiplication의 Bit operation 수의 Estimate

  • Solution
    이전 Example에서 Fast multiplication의 n%2=0n\%2=0일 때 f(n)=3f(n/2)+Cnf(n)=3f(n/2)+Cn이다(f(n)f(n)은 두 개의 nn bit Integer를 Multiplication하는 데 필요한 Operation 수).
    따라서 Master theorem에 의해 f(n)f(n)은 O(nlog⁡3)O(n\log 3)이다.

7.4. Generating Functions​

Generating Functions​

Sequence a0,a1,⋯ ,ak,⋯a_0, a_1, \cdots, a_k, \cdots(aia_i는 Real number)의 Generating function(생성 함수)는 G(x)=a0+a1x+⋯+akxk+⋯=∑k=0∞akxkG(x)=a_0+a_1x+\cdots+a_kx^k+\cdots=\sum_{k=0}^{\infin}a_kx^k이며 이를 Ordinary generating function(일반 생성 함수)라고도 한다.

팁

Example

Positive integer mm에 대해 ak=C(m,k)a_k=C(m, k)라고 할 때 Sequence a0,a1,⋯ ,ama_0, a_1, \cdots, a_m의 Generating function

  • Solution
    G(x)=C(m,0)+C(m,1)x+⋯+C(m,m)xmG(x)=C(m,0)+C(m,1)x+\cdots+C(m,m)x^m이고 Binomial theorem에 따라 G(x)=(1+x)mG(x)=(1+x)^m이 되게 된다.

Useful Facts About Power Series​

Generating function이 Counting problem을 해결하는 데 사용될 때 일반적으로 Formal power series(형식적 멱급수)로 간주된다.

정보

Theorem

f(x)=∑k=0∞akxkf(x)=\sum_{k=0}^{\infin}a_kx^k이고 g(x)=∑k=0∞bkxkg(x)=\sum_{k=0}^{\infin}b_kx^k일 때 f(x)+g(x)=∑k=0∞(ak+bk)xkf(x)+g(x)=\sum_{k=0}^{\infin}(a_k+b_k)x^k이고 f(x)g(x)=∑k=0∞(∑j=0kajbk−j)xkf(x)g(x)=\sum_{k=0}^{\infin}(\sum_{j=0}^ka_jb_k-j)x^k

팁

Example

f(x)=1/(1−x)2f(x)=1/(1-x)^2일 때 Coefficient a0,a1,⋯a_0,a_1,\cdots 값

  • Solution
    1/(1−x)=1+x+x2+⋯1/(1-x)=1+x+x^2+\cdots(단 ∣x∣<1|x|<1)이다.
    Therem을 사용할 경우 f(x)=1/(1−x)2=∑k=0∞(∑j=0k1)xk=∑k=0∞(k+1)xkf(x)=1/(1-x)^2=\sum_{k=0}^{\infin}(\sum_{j=0}^k1)x^k=\sum_{k=0}^{\infin}(k+1)x^k이다.

Real number uu, Nonnegative integer kk에 대한 Extended binomial coefficient (uk)\binom{u}{k}는 k>0k>0일 때 u(u−1)⋯(u−k+1)k!\frac{u(u-1)\cdots(u-k+1)}{k!}이고 k=0k=0일 경우 1이다.

팁

Example

(−23),(1/23)\binom{-2}{3}, \binom{1/2}{3}의Extended binomial coefficient

  • Solution
    (−23)\binom{-2}{3}의 경우 u=−2,k=3u=-2, k=3이기에 (−23)=(−2)(−3)(−4)3!=−4\binom{-2}{3}=\frac{(-2)(-3)(-4)}{3!}=-4, (1/23)\binom{1/2}{3}의 경우
    (1/23)=(1/2)(1/2−1)(1/2−2)3!=116\binom{1/2}{3}=\frac{(1/2)(1/2-1)(1/2-2)}{3!}=\frac{1}{16}이다.
정보

Theorem

The extended binomial theorem
∣x∣<1|x|<1인Real number u,xu, x에 대해 (1+x)u=∑k=0∞(uk)xk(1+x)^u=\sum_{k=0}^{\infin}\binom{u}{k}x^k

팁

Example

(1+x)−n,(1−x)−n(1+x)^{-n}, (1-x)^{-n}의 Generating function(단 nn은 Positive integer)

  • Solution
    (1+x)−n=∑k=0∞(−1)kC(n+k−1,k)xk(1+x)^{-n}=\sum_{k=0}^{\infin}(-1)^kC(n+k-1, k)x^k이고,
    (1−x)−n=∑k=0∞C(n+k−1,k)xk(1-x)^{-n}=\sum_{k=0}^{\infin}C(n+k-1, k)x^k이다.

Counting Problems and Generating Functions​

G(x)a_k
(1+x)n=∑k=0nC(n,k)xk=1+C(n,1)x+C(n,2)x2+⋯+xn(1+x)^n\\=\sum_{k=0}^nC(n,k)x^k\\=1+C(n,1)x+C(n,2)x^2+\cdots+x^nC(n,k)C(n,k)
(1+ax)n=∑k=0nC(n,k)akxk=1+C(n,1)ax+C(n,2)a2x2+⋯+anxn(1+ax)^n\\=\sum_{k=0}^nC(n,k)a^kx^k\\=1+C(n,1)ax+C(n,2)a^2x^2+\cdots+a^nx^nC(n,k)akC(n,k)a^k
(1+xr)n=C(n,k)xrk=1+C(n,1)xr+C(n,2)x2r+⋯+xrn(1+x^r)^n\\=C(n,k)x^{rk}\\=1+C(n, 1)x^r+C(n,2)x^{2r}+\cdots+x^{rn}C(n,k/r)C(n, k/r) if $$r
1−xn+11−x=∑k=0nxk=1+x+x2+⋯+xn\frac{1-x^{n+1}}{1-x}\\=\sum_{k=0}^nx^k\\=1+x+x^2+\cdots+x^n1 if k≤n;0k\leq n;0 otherwise
11−x=∑k=0∞xk=1+x+x2+⋯\frac{1}{1-x}\\=\sum_{k=0}^\infin x^k\\=1+x+x^2+\cdots1
11−ax=∑k=0∞akxk=1+ax+a2x2+⋯\frac{1}{1-ax}\\=\sum_{k=0}^\infin a^kx^k\\=1+ax+a^2x^2+\cdotsaka^k
11−xr=∑k=0∞xrk=1+xr+x2r+⋯\frac{1}{1-x^r}\\=\sum_{k=0}^\infin x^{rk}\\=1+x^r+x^{2r}+\cdots1 if $$r
1(1−x)2=∑k=0∞(k+1)xk=1+2x+3x2+⋯\frac{1}{(1-x)^2}\\=\sum_{k=0}^\infin (k+1)x^k\\=1+2x+3x^2+\cdotsk+1k+1
1(1−x)n=∑k=0∞C(n+k−1,k)xk=1+C(n,1)x+C(n+1,2)x2+⋯\frac{1}{(1-x)^n}\\=\sum_{k=0}^\infin C(n+k-1,k)x^k\\=1+C(n,1)x+C(n+1,2)x^2+\cdotsC(n+k−1,k)=C(n+k−1,n−1)C(n+k-1,k)=C(n+k-1,n-1)
1(1+x)n=∑k=0∞C(n+k−1,k)(−1)kxk=1−C(n,1)x+C(n+1,2)x2−⋯\frac{1}{(1+x)^n}\\=\sum_{k=0}^\infin C(n+k-1, k)(-1)^kx^k\\=1-C(n,1)x+C(n+1,2)x^2-\cdots(−1)kC(n+k−1,k)=(−1)kC(n+k−1,n−1)(-1)^kC(n+k-1,k)=(-1)^kC(n+k-1,n-1)
1(1−ax)n=sumk=0∞C(n+k−1,k)akxk=1+C(n,1)ax+C(n+1,2)a2x2+⋯\frac{1}{(1-ax)^n}\\=sum_{k=0}^\infin C(n+k-1, k)a^kx^k\\=1+C(n,1)ax+C(n+1,2)a^2x^2+\cdotsC(n+k−1,k)ak=C(n+k−1,n−1)akC(n+k-1,k)a^k=C(n+k-1,n-1)a^k
ek=∑k=0∞xkk!=1+x+x22!+x33!+⋯e^k\\=\sum_{k=0}^\infin \frac{x^k}{k!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots1k!\frac{1}{k!}
ln⁡(1+x)=∑k=0∞(−1)k+1kxk=x−x22+x33−x44+⋯\ln(1+x)\\=\sum_{k=0}^\infin \frac{(-1)^{k+1}}{k}x^k\\=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots(−1)k+1k\frac{(-1)^{k+1}}{k}
팁

Example

Generating function을 사용하여 nn가지의 서로 다른 종류의 rr개 Object를 선택하는 방법의 수를 구하되 각 종류의 Object를 최소한 하나 이상 선택

  • Solution
    nn가지 종류의 Object는 Generating function G(x)G(x)는 (x+x2+⋯ )(x+x^2+\cdots)의 형태의Sequence {ar}\{a_r\}의 element가 되며 Sequence {ar}\{a_r\}은 각 종류의 Object를 최소한 하나 이상 선택해야 할 경우 nn가지의 서로 다른 종류의 rr개의 Object를 선택하는 방법의 수가 된다.
    즉 G(x)=(x+x2+⋯ )n=xn(1+x+x2+⋯ )=xn(1−x)nG(x)=(x+x^2+\cdots)^n=x^n(1+x+x^2+\cdots)=\frac{x^n}{(1-x)^n}이다.
    Extended binomial theorem을 사용하여 G(x)=xn/(1−x)n=xn⋅(1−x)−n=xn∑r=0∞(−nr)(−x)r=xn∑r=0∞(−1)rC(n+r−1,r)(−1)rxr=∑r=0∞C(n+r−1,r)xn+r=∑t=n∞C(t−1,t−n)xt=∑r=n∞C(r−1,r−n)xrG(x)\\=x^n/(1-x)^n\\=x^n\cdot (1-x)^{-n}\\=x^n\sum_{r=0}^\infin\binom{-n}{r}(-x)^r\\=x^n\sum_{r=0}^\infin (-1)^rC(n+r-1,r)(-1)^rx^r\\=\sum_{r=0}^\infin C(n+r-1, r)x^{n+r}\\=\sum_{t=n}^\infin C(t-1, t-n)x^t \\=\sum_{r=n}^\infin C(r-1,r-n)x^r
    이 된다.
    Summation을 옮기기 위해 t=n+rt=n+r로 설정하여 r=0r=0일 때 t=nt=n, n+r−1=t−1n+r-1=t-1이 되게 된다.

Using Generating Functions to Solve Recurrence Relations​

팁

Example

a0=2a_0=2이고 ak=3ak−1a_k=3a_{k-1}을 만족하는 Recurrence relation을 해결

  • Solution
    G(x)G(x)를 Sequence {ak}\{a_k\}의 Generating function으로 둘 경우 G(x)=∑k=0∞akxkG(x)=\sum_{k=0}^\infin a_kx^k가 된다.
    xG(x)=∑k=0∞akxk+1=∑k=1∞ak−1xkxG(x)=\sum_{k=0}^\infin a_kx^{k+1}=\sum_{k=1}^\infin a_{k-1}x^k이다.
    G(x)−3xG(x)=∑k=0∞akxk−3∑k=1∞ak−1xk=a0+∑k=1∞(ak−3ak−1)xk=2(∵a0=2,ak=3ak−1)G(x)-3xG(x)\\=\sum_{k=0}^\infin a_kx^k-3\sum_{k=1}^\infin a_{k-1}x^k\\=a_0+\sum_{k=1}^\infin(a_k-3a_{k-1})x^k\\= 2(\because a_0=2, a_k=3a_{k-1})
    가 되므로 G(x)−3xG(x)=(1−3x)G(x)=2G(x)-3xG(x)=(1-3x)G(x)=2이므로 G(x)=21−3xG(x)=\frac{2}{1-3x}가 된다.
    Identity 1/(1−ax)=∑k=0∞akxk1/(1-ax)=\sum_{k=0}^\infin a^kx^k를 사용하여 G(x)=2∑k=0∞3kxk=∑k=0∞2⋅3kxkG(x)=2\sum_{k=0}^\infin 3^kx^k=\sum_{k=0}^\infin 2\cdot 3^kx^k이므로 ak=2⋅3ka_k=2\cdot 3^k이다.
팁

Example

7.1.에서 다룬 Codeword가 0이 짝수개 포함된 nn자리 10진수 일 때 ana_n을 길이 nn의 유효한 Codeword 수라고 할 때 an=8an−1+10n−1a_n=8a_{n-1}+10^{n-1}임과 a1=9a_1=9임을 이용하여 Generating function을 사용해 Explicit formula todtjd

  • Solution
    a0=1a_0=1로 설정하여 Generating function 작업을 간소화하면 a1=8a0+100=9a_1=8a_0+10^0=9로 성립한다.
    Recurrence relation 양 변에 xnx^n을 곱해 anxn=8an−1xn+10n−1xna_nx^n=8a_{n-1}x^n+10^{n-1}x^n을 얻을 수 있다.
    G(x)=∑n=0∞anxnG(x)=\sum_{n=0}^\infin a_nx^n을 Sequence {an}\{a_n\}의 Generating function으로 둘 경우 마지막 Equation의 양 변을 n=1n=1 부터 시작하여 Sum할 경우
    G(x−1)=sumn=1∞anxn=∑n=1∞(8an−1xn+10n−1xn)=8∑n=1∞an−1xn+∑n=1∞10n−1xn=8x∑n=0∞anxn+x∑n=0∞10nxn=8xG(x)+x/(1−10x)G(x-1)\\=sum_{n=1}^\infin a_nx^n=\sum_{n=1}^\infin (8a_{n-1}x^n+10^{n-1}x^n)\\=8\sum_{n=1}^\infin a_{n-1}x^n+\sum_{n=1}^\infin 10^{n-1}x^n\\=8x\sum_{n=0}^\infin a_nx^n+x\sum_{n=0}^\infin 10^nx^n\\=8xG(x)+x/(1-10x)
    이기에 G(x)=1−9x(1−8x)(1−10x)G(x)=\frac{1-9x}{(1-8x)(1-10x)}이다.
    정리를 통해 G(x)=12(11−8x+11−10x)G(x)=\frac{1}{2}(\frac{1}{1-8x}+\frac{1}{1-10x})이기에 안의 11−8x\frac{1}{1-8x}를 ∑n=0∞8nxn\sum_{n=0}^\infin 8^nx^n으로, 11−10x\frac{1}{1-10x}을 ∑n=0∞10nxn\sum_{n=0}^\infin 10^nx^n으로 변환하여 묶으면 G(x)=12(∑n=0∞8nxn+∑n=0∞10nxn)=∑n=0∞12(8n+10n)xnG(x)=\frac{1}{2}(\sum_{n=0}^\infin 8^nx^n+\sum_{n=0}^\infin 10^nx^n)=\sum_{n=0}^\infin \frac{1}{2}(8^n+10^n)x^n이므로 an=12(8n+10n)a_n=\frac{1}{2}(8^n+10^n)이다.

Proving Identities via Generating Functions​

팁

Example

Generating function을 사용하여 ∑k=0nC(n,k)2=C(2n,n)\sum_{k=0}^nC(n,k)^2=C(2n,n)임을 보임

  • Solution
    Binomail theorem을 통해 C(2n,n)C(2n, n)은 (1+x)2n(1+x)^{2n}에서 xnx^n의 Coefficient이다.
    (1+x)2n=[(1+x)n]2=[C(n,0)+C(n,1)x+⋯+C(n,n)xn]2(1+x)^2n\\=[(1+x)^n]^2\\=[C(n,0)+C(n,1)x+\cdots+C(n,n)x^n]^2
    이고 xnx^n의 Coefficient의 Expression은 C(n,0)C(n,n)+C(n,1)C(n,n−1)+⋯+C(n,n)C(n,0)C(n,0)C(n,n)+C(n,1)C(n,n-1)+\cdots+C(n,n)C(n,0)이기에 ∑k=0nC(n,k)2\sum_{k=0}^nC(n,k)^2과 같다.

7.5. Inclusion-Exclusion​

The Principle of Inclusion-Exclusion​

팁

Example

이산 수학 수업에서 모든 학생은 컴퓨터 과학이나 수학 전공이거나 둘 다일 수 있을 때 컴퓨터 과학 전공이 25명, 수학 전공이 13, 둘 다 전공이 8일 때 수업의 학생 수

  • Solution
    이전에 다뤘던 Principle of Inclusion-Exclusion을 이용하여 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B|이기에 30이다.

Principle of inclusion-exclusion을 여러 Set에도 사용 가능하며, 반복하여 적용하는 것과 같다.

팁

Example

총 1232명의 스페인어 과정 수강생, 879명의 프랑스어 과정 수강생, 114명의 러시아어 과정 수강생이고 스페인어와 프랑스어 과정을 수강한 수강생은 103명, 스페인어 러시아어는 23명, 프랑스어와 러시아어는 14명 일 때 2092명의 학생이 스페인어나 프랑스어 러시아어를 수강했을 때 세 언어 과정을 수강한 수강생의 수

  • Solution
    스페인, 프랑스, 러시아어 수강생 Set을 S,F,RS,F,R로 둘 때 ∣S∣=1232,∣F∣=879,∣R∣=114,∣S∩F∣=103,∣S∩R∣=23,∣F∩R∣=14,∣S∪F∪R∣=2092|S|=1232, |F|=879,|R|=114,|S\cap F|=103, |S\cap R|=23, |F\cap R|=14, |S\cup F\cup R|=2092임을 이용하여 ∣S∪F∪R∣=∣S∣+∣F∣+∣R∣−∣S∩F∣−∣S∩R∣−∣F∩R∣+∣S∩F∩R∣|S\cup F\cup R|=|S|+|F|+|R|-|S\cap F|-|S\cap R|-|F\cap R|+|S\cap F\cap R|이기에 2092=1232+8790+114−103−23−14+∣S∩F∩R∣2092=1232+8790+114-103-23-14+|S\cap F\cap R|로 7임을 알 수 있다.
정보

Theorem

The principle of inclusion-exclusion
A1,A2,⋯ ,AnA_1, A_2, \cdots, A_n이 Finite set일 때 ∣A1∪A2∪⋯∪An∣=∑1≤i≤n∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+⋯+(−1)n+1∣A1∩A2∩⋯∩An∣|A_1\cup A_2\cup \cdots \cup A_n|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}|A_1\cap A_2\cap \cdots \cap A_n|이 성립한다.

7.6. Applications of Inclusion-Exclusion​

An Alternative Form of Inclusion-Exclusion​

AiA_i를 Property PiP_i를 가진 Element를 포함하는 Subset으로 지정할 경우 모든 Property PiP_i를 가진 Element Pi1,Pi2,…,PinP_{i_1},P_{i_2},\dots,P_{i_n}의 수를 Notation N(Pi1Pi2…Pin)N(P_{i_1}P_{i_2}\dots P_{i_n})로 표현한다.
즉, ∣Ai1∩Ai2∩⋯∩Aik∣=N(Pi1Pi2⋯Pik)|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|= N(P_{i_1}P_{i_2}\cdots P_{i_k})이다.

Property P1,P2,…,PnP_1,P_2,\dots, P_n이 없는 Element의 수를 Notation N(P1′P2′⋯Pn′)N(P'_1P'_2\cdots P'_n)으로 표현한다.
Set의 Element의 수를 NN으로 둔다면 N(P1′P2′⋯Pn′)=N−∑1≤i≤nN(Pi)+∑1≤i<j≤nN(PiPj)−⋯+(−1)nN(P1P2⋯Pn)N(P'_1P'_2\cdots P'_n)=N - \sum_{1\leq i\leq n}N(P_i)+\sum_{1\leq i<j\leq n}N(P_iP_j)-\cdots+(-1)^nN(P_1P_2\cdots P_n)으로 나타낼 수 있다.

팁

Example

x1+x2+x3=11x_1+x_2+x_3=11이며 x1≤3,x2≤4,x3≤6x_1\leq 3, x_2\leq 4, x_3\leq 6을 만족하는 Integer일 때 Solution 개수

  • Solution
    Principle of inclusion-exclusion을 활용하기 위해 P1P_1을 x>3x>3과 같이 역치를 하여 N(P1′P2′P3′)=N−N(P1)−N(P2)−N(P3)+N(P1P2)+N(P1P3)+N(P2P3)−N(P1P2P3)=78−36028−15+6+1+0−0=6N(P_1'P_2'P_3')=N-N(P_1)-N(P_2)-N(P_3)+N(P_1P_2)+N(P_1P_3)+N(P_2P_3)-N(P_1P_2P_3)=78-36028-15+6+1+0-0=6이 답이 된다.
    (N=C(3+11−1,11),N(P1)=C(3+7−1,7),N(P2)=C(3+6−1,6),N(P3)=C(3+4−1,4),N(P1P2)=C(3+2−1,2),N(P1P3)=C(3+0−1,0)=1,N(P2P3)=0,N(P1P2P3)=0N=C(3+11-1,11), N(P_1)=C(3+7-1,7),N(P_2)=C(3+6-1,6),N(P_3)=C(3+4-1,4),N(P_1P_2)=C(3+2-1,2),N(P_1P_3)=C(3+0-1,0)=1,N(P_2P_3)=0,N(P_1P_2P_3)=0)

The Sieve of Eratosthenes​

Principle of inclusion-exclusion을 이용하여 지정된 Positive integer를 초과하지 않는 Prime의 개수를 찾을 수 있으며 이를 The sieve of Eratosthenes라고 한다.
Composite number는 그 Number의 Square root를 초과하지 않는 Prime으로 나누어 떨어진다는 점을 활용하여 반복한다.

팁

Example

100 이하의 Prime 개수를 The sieve of Eratosthenes를 이용하여 구함

  • Solution
    100의 Square root 10 이하의 Prime set은 {2,3,5,7}\{2,3,5,7\}이다.
    이를 이용하여 위 Set의 Cardinality 4+N(P1′P2′P3′P4′)4+N(P_1'P_2'P_3'P_4')를 수행한다.
    N(P1′P2′P3′P4′)=N−N(P1)−⋯+N(P1P2)+⋯−N(P1P2P3)−⋯+N(P1P2P3P4)N(P_1'P_2'P_3'P_4')=N-N(P_1)-\cdots+N(P_1P_2)+\cdots-N(P_1P_2P_3)-\cdots+N(P_1P_2P_3P_4)이므로 N(P1′P2′P3′P4′)=99−⌊1002⌋−⋯+⌊1002⋅3⌋+⋯−⌊1002⋅3⋅5⌋−⋯+⌊1002⋅3⋅5⋅7⌋=21N(P_1'P_2'P_3'P_4')=99-\lfloor \frac{100}{2} \rfloor - \cdots +\lfloor{\frac{100}{2\cdot 3}}\rfloor+ \cdots -\lfloor{\frac{100}{2\cdot 3\cdot 5}}\rfloor-\cdots +\lfloor{\frac{100}{2\cdot 3\cdot 5\cdot 7}}\rfloor=21이다.\

    ![The sieve of Eratosthenes](./img/image (179).png)

The Number of Onto Functions​

Principle of include-exclude를 이용하여 mm개의 Element에서 nn개의 Element로 가는 Set의 Onto function 수를 구할 때도 사용할 수 있다.

정보

Theorem

Positive integer m,nm, n이 n≤mn\leq m일 때 nm−C(n,1)(n−1)m+C(n,2)(n−2)m−⋯+(−1)n−1C(n,n−1)⋅1mn^m-C(n,1)(n-1)^m+C(n,2)(n-2)^m-\cdots+(-1)^{n-1}C(n, n-1)\cdot 1^m이 mm개의 Element에서 nn개의 Element로 가는 Set의 Onto function의 수

팁

Example

다섯 가지 서로 다른 직무를 네 명의 서로 다른 직원에게 할당하는 방법의 개수

4명의 직원이 5개 중 최소 하나의 직무를 맡는 경우를 Cardinality가 5인 Set에서 Cardinality가 4인 Set으로의 Onto function 상황과 똑같다.
즉, 45−C(4,1)35+C(4,2)25−C(4,3)15=1024−972+192−4=2404^5-C(4,1)3^5+C(4,2)2^5-C(4,3)1^5=1024-972+192-4=240이다.

Derangements​

Derangement(교란 순열)은 원 위치에 아무 Object도 남기지 않은 Object의 Permutation이다.

팁

Example

Permutation 21453은 12345의 Derangement이나 21543은 Derangement가 아니다(Permutation 21543은 4의 위치가 고정되어 있음).

정보

Theorem

nn개의 Element로 이루어진 Derangement의 수는 Dn=n![1−11!+12!−13!+⋯+(−1)n1n!]D_n=n![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}]

  • Proof
    Permutation이 ii Element를 고정하면 Property PiP_i를 가진다고 할 때 Derangement의 수는 i=1,2,⋯ ,ni=1,2,\cdots,n에 대해 어떤 Property PiP_i를 갖지 않는 Property의 수이다.
    즉, Dn=N(P1′P2′⋯Pn′)D_n=N(P_1'P_2'\cdots P_n')이다.
    Permutation이기에 N=n!N=n!가 되고 N(Pi)=n−1N(P_i)=n-1이 된다.
    반복하여 M(P1P2⋯Pm)=(n−m)!M(P_1P_2\cdots P_m)=(n-m)!임을 이용하여 ∑1≤i1<i2<⋯<im≤nN(Pi1Pi2⋯Pim=C(n,m)(n−m)!\sum_{1\leq i_1 < i_2 < \cdots <i_m\leq n}N(P_{i_1}P_{i_2}\cdots P_{i_m}=C(n,m)(n-m)!임을 알 수 있다.
    Principle of include-exclude의 Formula를 이용하여 Dn=N(P1′P′2⋯P′n)=N−∑1≤i≤nN(Pi)+∑1≤i<j≤nN(PiPj)−⋯+(−1)nN(P1P2⋯Pn)=n!−C(n,1)(n−1)!+⋯+(−1)nC(n,n)(n−n)!=n!−n!1!(n−1)!(n−1)!+⋯+(−1)nn!n!0!0!=n![1−11!+⋯+(−1)n1n!]D_n=N(P'_1P'2\cdots P'n)=N - \sum{1\leq i\leq n}N(P_i)+\sum{1\leq i<j\leq n}N(P_iP_j)-\cdots+(-1)^nN(P_1P_2\cdots P_n)\\=n!-C(n,1)(n-1)!+\cdots+(-1)^nC(n,n)(n-n)!\\=n!-\frac{n!}{1!(n-1)!}(n-1)!+\cdots+(-1)^n\frac{n!}{n!}{0!}0!\\=n![1-\frac{1}{1!}+\cdots+(-1)^n\frac{1}{n!}]
    으로 증명 가능하다.