Counting, Recurrence Relation, Infinite Sets
1. Infinite Sets
1-1. Finite Sets
Definition 1
집합 A가 finite하려면 A가 empty하거나 특정 자연수 n에 대해 {1, 2, ..., n} 집합과 집합 A이 bijection 관계에 있어야 한다.
n은 A의 cardinality이다. cardinality A는 |A|로 표시된다.
1-2. Pigeonhole Principle
Theorem 1(Pigeonhole Principle)
만약 A와 B가 finite set이고, |A| = m, |B| = n이고, m > n이면, 함수 $f : A \rightarrow B$는 injection이 아니다. 즉 B의 image 중 둘 이상의 pre-image를 가지는 것이 무조건 있다.
Example 1
Theorem : Every integer has a multiple of itself whose decimal representation consists only of 0s and 1s.
Proof) For $n \in \mathbb{Z}$, f(x) = x%n : $A \rightarrow [0, n-1]$이고 A = {1, 11, 111, 1111, ...} 이라고 가정해보자.
|A|가 n+1이라면, |[0, n-1]| = n이기 때문에 Pigeonhole theorem에 의해 f는 injection이 아니다. 그러므로 $\exists a, b \in A$ such that $a \neq b \land f(a) = f(b)$. 이것은 a%n = b%n인 것을 의미한다. 따라서 (a-b)%n = 0이다. 그러므로 (a-b)는 n으로 나누어떨어지며, a-b는 1과 0으로만 구성된 십진수이다.
Theorem 2
A가 finite set이라면 cardinality of A는 unique하다.
Theorem 3
A와 B가 finite set일 때, $f : A \rightarrow B$인 bijection 함수 f가 있다면 |A| = |B|이다.
Theorem 4 (Rule of Sum)
만약 A와 B가 finite하고 disjoint 관계에 있다면(|A| = m, |B| = n) 각각 $|A \cup B| = m + n$이다.
Theorem 5 (Rule of Product)
만약 A와 B가 finite하고 (|A| = m, |B| = n)이라면 $|A \times B| = mn$이다.
Theorem 6 (Counting Functions)
만약 A와 B가 finite set이고 |A| = m, |B| = n이라면, $f : A \rightarrow B$인 함수 f는 $n^m$개 존재한다.
1-3. Permutation and Combination
Theorem 7
A가 n개의 원소로 구성된 finite set이라면, A의 구별되는 permutation은 총 n!개이다.
Theorem 8
The number of r-permutations of n objects는 P(n, r)로 쓰여지며
$$P(n, r) = \frac{n!}{(n-r)!}$$
Theorem 9
r, n은 자연수이고, $r \le n$이라면 The number of combinations of n objects taken r은 C(n,r) 또는 $\binom{n}{r}$으로 쓰여진다.
$$C(n ,r) = \frac{n!}{r!(n-r)!}$$
2. Recurrence Relations
2-1. Definition
재귀 관계란 sequence를 특정하는 하나의 방법이다. 각각의 term은 이전의 term들에 의해 정의되어진다.
- A recurrence relation은 sequence $a_0, a_1, a_2, ...$이 각각 자신 이전에 있는 term들로 규정되어 진다.
- $a_0, a_1, ...$ 정해진 숫자로 초기값이 주어진다.
Example 3(Fibonacci sequence)
- $a_0 = 0, a_1 = 1$(initial conditions)
- $a_n = a_{n-1} + a_{n-2}$ for $n \ge 2$(recurrence equation)
2-2. Solution to a recurrence relation
- recurrence relation의 solution은 recurrence equation과 boundary condition을 만족시키는 explicit formula이다.
- recurrence relation을 푸는 두가지 방법은 iteration과 linear homogeneous recurrence relation을 적용하는 방법이다.
2-3. Solving by Iterations
$a_n$으로부터 $a_{n-1}, ... , a_0$을 차례대로 순환하며 explicit equation을 구하는 방법이다.
$a_n = a_{n-1} + 3$과 $a_1 = 2$이다. iteration을 이용하면 $a_n = 2 + 3(n-1)$이다.
$$a_n = a_{n-1} + 3$$
$$ = a_{n-2} + 3 + 3$$
$$ = a_{n-3} + 3 + 3 + 3$$
$$ = a_{n-k} + 3k$$
$$ = a_{n - (n-1) + 3(n-1)}$$
$$= 2 + 3(n - 1)$$
2-4. Solving Linear Homogeneous Recurrence Relations
Definition 2
A linear homogeneous recurrence relation of order k with constant coefficients는 recurrence relation이 다음과 같은 형태를 가질 때를 말한다.
$$a_n = c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{k}a_{n-k}$$
$c_1, c_2, c_3, ... , c_k$는 모두 constant이며, $c_k \neq 0$이다.
다음과 같은 LHRR은 k개의 initial value를 가져야 한다. $a_0, a_1, ... , a_{k-1}$
Theorem 10
만약 $r_1과 r_2$가 $x^2 = c_1x + c_2$의 서로 다른 두 근이라면,
$$a_n = \alpha_1r_1^n + \alpha_2r_2^n$$
이 다음 LHRR의 해이다. $a_n = c_1a_{n-1} + c_2a_{n-2}(n \ge 2)$과 initial value $a_1, a_0$
$$\alpha_1 = \frac{a_1 - a_0r_2}{r_1 - r_2},\ \alpha_2 = \frac{a_0r_1 - a_1}{r_1 - r_2}$$
아래 관계를 만족한다.
$$a_0 = \alpha_1 + \alpha_2\ and\ a_1 = \alpha_1r_1 + \alpha_2r_2$$
Remark 1
Theorem 10은 아래와 같은 과정으로 얻어진다.
(1) $r_1, r_2$가 $x^2 = c_1x + c_2$의 서로 다른 두 근이고, $c_1 = r_1 + r_2$, $c_2 = -r_1r_2$이기 때문에 다음의 이차방정식은
$$x^2 - r_1x = r_2(x - r_1)$$
으로 바꾸어 써줄 수 있다.
(2) recurrence relation $a_n = c_1a_{n-1} + c_2a_{n-2}$은
$$a_n - r_1a_{n-1} = r_2(a_{n-1} - r_1a_{n-2})$$
으로 나타내줄 수 있다.
$b_n = a_n - r_1a_{n-1}$ $(n \ge 1)$으로 가정한다면, $b_n$의 closed form을 얻어낼 수 있고 그를 통해 답을 이끌어낼 수 있다.
$a_n = 3a_{n-1} - 2a_{n-2}$가 recurrence relation으로 주어질 때,
$r_1 = 2, r_2 = 1$이다.
(1) initial condition $a_1 = 1, a_0 = 1$일 때,
$\alpha_1 = 0, \alpha_2 = 1$이다. $a_n = r_2^n = 1^n$이다.
Theorem 11
만약 r이 $x^2 = c_1x + c_2$의 중근이라면,
$$a_n = \alpha_1r^n + \alpha_2nr^{n}$$
recurrence relation $a_n = c_1a_{n-1} + c_2a_{n-2}\ (n \ge 2)$의 solution이다.
만약 r이 중근이라면, $a_n - ra_{n-1} = r(a_{n-1} - ra_{n-2})$로 표시해줄 수 있다.
$b_n = a_n - ra_{n-1}$으로 두면 $b_n = r^{n-1}b_1$이며 $a_n = (a_0 + (\frac{a_1}{r} - a_0)n)r^n$이다.
따라서 $\alpha_1 = a_0$, $\alpha_2 = \frac{a_1}{r} - a_0$으로 나타내줄 수 있다.
ex)
$a_n = 4a_{n-1} - 4a_{n-2}$라고 하면 r은 2이다.
$$a_n = (\alpha_1 + \alpha_2n)2^n$$
initial condition $a_0 = 1, a_1 = 4$를 적용하면
$$a_0 = \alpha_1 = 1$$
$$a_1 = (\alpha_1 + \alpha_2)2 = 4$$
가 된다.
다음을 이용해서 방정식을 풀면
$$\therefore a_n = (\alpha_1 + \alpha_2n)2^n = (1+n)2^n$$
Remark 2
recurrence relation a_n = 3a_{n-1} - 2a_{n-2}에 대해,
해는 $a_n = \alpha_11^n + \alpha_22^n$이고 어떠한 정수 $\alpha_1, \alpha_2$에 대해서 성립한다.
$a_n = 4 \cdot 1^n + 5 \cdot 2^n$이 해인 것을 보이고 싶다면 $a_n = 1^n$과 $a_n = 2^n$이 만족하기 때문에
$$4 \cdot 1^{n} = 4 \cdot (3 \cdot 1^{n-1} - 2 \cdot 1^{n-2})$$
$$5 \cdot 2^{n} = 5 \cdot (3 \cdot 2^{n-1} - 2 \cdot 2^{n-2})$$
이 둘을 더하면
$$4 \cdot 1^{n} + 5 \cdot 2^{n} = 3 \cdot (4 \cdot 1^{n-1} + 5 \cdot 2^{n-1}) - 2 \cdot (4 \cdot 1^{n-2} + 5 \cdot 2^{n-2})$$
이 된다.
따라서 다음의 해도 recurrence relation을 만족시킨다.
2-5. Characteristic Equation
$a_n = r^n$이 다음 recurrence relation의 해라면, $a_n = c_1a_{n-1} + c_2a_{n-2} + c_3a_{n-3} + ... + c_ka_{n-k}(n \ge k)$,
$$\iff r^n = c_1r^{n-1} + c_2r^{n-2} + ... + c_kr^{n-k}$$
$r^{n-k}$로 나누면
$$r^k - c_1r^{k-1} - c_2r^{k-2} - ... - c_k = 0$$
이 된다.
다음을 the characteristic equation of the recurrence equation이라 부른다.
다음 식의 해를 the characteristics roots of the recurrence relation이라고 부른다.
위의 root를 이용해 모든 recurrence relation의 해를 구해줄 수 있다.
ex) $a_0 = 0, a_1 = a_2 = 1,$
$a_n = 2a_{n-1} + a{n-2} - 2a{n-3}$ for $n \gt 2$
$x^3 - 2x^2 - x + 2 = 0$는 세가지 근 -1, 1, 2를 가진다.
따라서
$$a_{n} = \alpha_1(-1)^n + \alpha_21^n + \alpha_32^n$$
가 된다.
initial condition을 각각 대입해주면
$a_0 = 0, a_1 = 1, a_2 = 1$
$$\therefore a_n = (-1/3)(-1)^n + (1/3)2^n = ((-1)^{n+1} + 2^n) / 3$$
2-6. Multiplicity of a root
Theorem 13
Suppose that the characteristic equation
$$r^k - c_1r^{k-1} - ... - c_k = 0$$
이 t개의 구분되는 root를 가질 때, multiplicity(각각의 근이 여러번 나오는 정도)는 $m_1, m_2, m_3, ... , m_k$로 표시된다.
$m_i \ge 1 (1 \le i \le t \le k)$이고 $\sum_{i = 1}^t m_i = k$이다.
$a_n$이 다음과 같은 LHRR을 가질 때,
$$a_n = c_1a_{n-1} + c_2a_{n-2} + ... + c_ka_{n-k}$$
는
$$\iff a_n = P_1(n)r_1^n + P_2(n)r_2^n + ... + P_t(n)r_t^n$$
$P_i(n)$은 polynomial of degree m_i - 1이다.(multiplicity보다 하나 낮은 차수의 다항식)
2-7. More Examples
ex)
A function that crows exponentially
$$a_0 = k, a_n = ca_{n-1} \ for\ n \gt 0$$
$$a_n = kc^n$$
ex)
f(h, k)가 maximum number of leaves of a tree of height h라면
f(0, k) = 1,
f(h,k) = kf(h-1, k) for $h \ge 1$
f(h,k) = $k^h$
ex)
Fibonacci sequence:
$$a_0 = 0, a_1 = 1$$
$$a_n = a_{n-1} + a_{n-2}\ for\ n \gt 1$$
characteristic function으로 풀면
$$\therefore a_n = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n$$
ex)
permutation
P(0) = 1
P(n) = nP(n-1) => this is not linear!!
P(n) = n!
3. Counting
3-1. Finite and Infinite Sets
Definition 3
A가 infinite하다는 것은 $f : A \rightarrow A$가 injection이 되고, f(A)가 A의 proper subset$(f(A) \ subsetneq A)$인 f가 존재한다는 것이다. A가 infinite하지 않으면 finite하다.
ex) $f : \mathbb{N} \rightarrow \mathbb{N}$이 f(x) = 2x로 규정되어진다면 이 함수는 injection이며, image는 $mathbb{N}$의 proper subset이다.
Theorem 15
A가 B의 superset일 때, B가 infinite할 때, A도 infinite하다.
Corollary 16
a finite set의 모든 부분 집합은 finite하다.
3-2. Countable and Uncountable Sets
Definition 4
set A가 cardinality $\aleph_0$일 때 |A| = $\aleph_0$이라고 적고, set $\mathbb{N}$와 A 사이에 bijection인 관계의 함수가 있을 때를 말한다.
Definition 5
set A가 countably infinite하려면 |A| = $\aleph_0$여야 한다. set A가 countable하거나 denumerable하다는 말은 A가 finite하거나 countably infinite한 상태를 말한다. set A가 uncountable하거나 uncountably infinite하려면 countable하지 않으면 된다.
ex) even positive number가 countably infinite한 것을 보여라.
f(x) = 2x 에서 $mathbb{N} \rightarrow$ {even positive numbers} 는 bijection한 관계를 가진다.
따라서 even positive number는 positive이다.
|even positive number| = $\aleph_0$
Theorem 17
The subset of real number, [0, 1]은 countably infinite하지 않다.
Proof by contradiction
f를 arbitrary function이고 $f : mathbb{N} \rightarrow [0, 1]$이라고 하자
f(x)는 아마
$$f(1) = 0.d_{1,1}d_{1,2}d_{1,3}...$$
$$f(2) = 0.d_{2,1}d_{2,2}d_{2,3}...$$
$$.$$
$$.$$
$$.$$
$$f(n) = 0.d_{n,1}d_{n,2}...$$
으로 나타내어줄 수 있다. $d_{n, i}$는 $f(n)$의 i번째 소숫점 자리의 숫자를 의미한다.
만약 어떠한 real number y를 다음과 같이 가정하면
$$ y_i = \begin{cases} 1 & \text{if $d_{i,i} \neq 1$}, \\ 2 & \text{if $d_{i,i} = 1$}, \end{cases}$$
$y \in [0,1]$이지만 y는 f(n)의 어떠한 숫자들과도 다르다.
$$y \text{ differs from } f(1) \text{ because } y_1 \neq d_{1,1}$$
$$y \text{ differs from } f(2) \text{ because } y_2 \neq d_{2,2}$$
$$y \text{ differs from } f(1) \text{ because } y_3 \neq d_{3,3}$$\
그러므로 $\exists y \in [0, 1] \land y \neq f(n)$이기 때문에 해당 함수는 surjection이 아니다.
the set [0,1]은 countable 하지 않다.