'Discrete Mathematics'에 해당되는 글 11건

피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 2
이번 글에서는 저번 글 피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 1 에서 증명한 피보나치/루카스 수열과 삼각함수와의 관계를 다시 한 번 정리하면 다음과 같다: 임의의 음이 아닌 정수 $n \in \N$에 대하여 복소수 $z_n = \frac{n\pi}{2} - i \ln(\phi^n)$을 정의하면 \[ \cos(z_n) = \frac{i^n}{2} L_n, \quad \sin(z_n) = \frac{i^n \sqrt{5}}{2i} F_n \] 의 관계가 성립한다. 이를 이용하여 삼각함수 항등식이 하나 주어졌을 때, 그에 해당되는 피보나치/루카스 수열에 대한 항등식을 증명할 수 있다. 여기서 $z_n$은 $n$에 대하여 선형(linear)이므로 $z_n = n z_..
Discrete Mathematics/Combinatorics  |  2020. 3. 16. 20:24
피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 1
피보나치 수열(Fibonacci sequence)은 $F_{0} = 0$, $F_{1} = 1$, $F_{n+2} = F_{n+1} + F_{n}$으로 정의된 대중적으로 가장 잘 알려진 수열 중 하나이다. 이 수열에 대한 성질에 대하여 몇 개의 글을 작성한 적이 있다. 피보나치 수열(Fibonacci sequence)과 그래프(graph) 피보나치 수열(Fibonacci sequence)과 역코탄젠트(arccotangent) 함수 피보나치 수(Fibonacci number) 판별법 한 편 루카스 수열(Lucas sequence)은 피보나치 수열과 초기값은 다르지만 동일한 점화관계(recurrence relation)을 갖는 수열로서, $L_{0} = 2$, $L_{1} = 1$, $L_{n+2} = L_..
Discrete Mathematics/Combinatorics  |  2020. 3. 16. 20:22
특수한 형태의 무한급수와 벨수(Bell number), 감마함수(gamma function)와의 연관성
이전 글에서 특수한 형태의 무한급수 (다항함수를 지수함수 또는 계승함수로 나눈 꼴의 무한급수) 의 값을 계산하는 일반적인 방법에 대하여 알아보았다. 다항함수/지수함수 형태로 이루어진 무한급수의 값 다항함수/계승함수 형태로 이루어진 무한급수의 값 위 무한급수의 값을 조합론에서 등장하는 벨수(Bell number)와 푸비니수(Fubini number), 그리고 해석학에서의 감마함수(gamma function)와 연관지을 수 있는데 이를 하나씩 알아보도록 하자. 다항함수/계승함수 형태의 무한급수와 벨수(Bell number) 일반적으로 $d$차 다항함수 \[ p(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_d x^d \] 가 주어졌을 때, 무한급수의 선형성을 이용하면 \[ \sum_..
Discrete Mathematics/Combinatorics  |  2020. 1. 24. 12:39
이항계수(binomial coefficient)들의 조화평균과 이차평균
예전에 "이항계수(binomial coefficient)들의 산술평균과 기하평균"이라는 주제로 글을 올린 적이 있다. 이번에는 이 주제를 좀 더 확장하여 이항계수들의 조화평균(harmonic mean) $H_n$과 이차평균(quadratic mean) $Q_n$에 대해서 생각해 보자. 여기서 $H_n$과 $Q_n$은 다음과 같이 정의되는 값이다. \[ H_n = \frac{n+1}{\sum_{k=0}^{n} \tfrac{1}{\binom{n}{k}}}, \qquad Q_n = \sqrt{\frac{1}{n+1}\sum_{k=0}^{n} \binom{n}{k}^2} \] 이번에도 $\sqrt[n]{H_n}$과 $\sqrt[n]{Q_n}$의 극한값을 각각 계산해 보도록 하자. $ $ $\sqrt[n]{H_n..
Discrete Mathematics/Combinatorics  |  2019. 4. 19. 09:37
분할(partition)에 대한 오일러의 정리(Euler's theorem)
분할(partition)이란 주어진 양의 정수를 양의 정수들의 합으로 표현하는 방법을 연구하는 정수론 또는 조합론의 한 하위 분야이다. 양의 정수 $n$이 주어졌다고 하자. 그러면 $n$에 대한 분할수(partition number) $p(n)$은 $n$을 양의 정수들의 합으로 나타내는 서로 다른 방법의 개수를 말한다. 예를 들어 $n = 7$인 경우, \[ \begin{align*} &7, && 3+2+2, \\ &6+1, && 3+2+1+1, \\ &5+2, && 3+1+1+1+1, \\ &5+1+1, && 2+2+2+1, \\ &4+3, && 2+2+1+1+1, \\ &4+2+1, && 2+1+1+1+1+1, \\ &4+1+1+1, && 1+1+1+1+1+1+1+1 \\ &3+3+1, && \end..
Discrete Mathematics/Combinatorics  |  2018. 12. 6. 04:58
이항계수(binomial coefficient)들의 산술평균과 기하평균
식 $(x+y)^n$을 전개하여 각 항의 계수를 적으면 아래와 같이 이항계수(binomial coefficient)가 나타난다. \[ \binom{n}{0},\; \binom{n}{1},\; \cdots,\; \binom{n}{n}. \] 이제 위 이항계수들의 산술평균(arithmetic mean)과 기하평균(geometric mean)을 각각 $A_n$, $G_n$이라 하자. 다시 말해 $A_n$과 $G_n$은 아래와 같이 정의되는 수이다. \[ A_n := \frac{1}{n+1} \sum_{k=0}^{n} \binom{n}{k}, \quad G_n := \sqrt[n+1]{\prod_{k=0}^{n} \binom{n}{k}}. \] 이번 글에서 계산해볼 것은 $\sqrt[n]{A_n}$과 $\sqr..
Discrete Mathematics/Combinatorics  |  2017. 4. 22. 23:15
Problems and Solutions #022
Problem #022$m \times n$ (단, $m \leq n$) 크기의 격자가 있다고 하자. 이 격자에서 찾을 수 있는 '정사각형'은 모두 몇 개일까? 이 격자에서 찾을 수 있는 '직사각형'은 모두 몇 개일까? (1) 주어진 격자에서 찾을 수 있는 $1 \times 1$ 크기의 정사각형의 수는 모두 $mn$개이다. 또한 이 격자에서 찾을 수 있는 $2 \times 2$ 크기의 정사각형의 수는 모두 $(m-1)(n-1)$개이다. 일반적으로 $1 \leq k \leq m$에 대하여 $k \times k$ 크기의 정사각형의 수는\[ (m-k+1)(n-k+1) \]이 됨을 쉽게 확인할 수 있다. 따라서 이 격자에서 찾을 수 있는 모든 정사각형의 개수는\[ \sum_{k=1}^{m} (m-k+1)(n-k..
Discrete Mathematics/Combinatorics  |  2017. 3. 1. 13:45
디랙의 정리(Dirac's Theorem)
어떤 마을에 $n$개의 집이 있다고 하자. 이제 이 마을에 어떤 집에 문제가 생겼을 때 각 집에 이 사실을 알릴 수 있는 비상연락망을 만들고자 한다. 이 때, 비상연락망이란 ABCDEA와 같이 순환적인 연락망 (이 때, 연락망이란 A가 B의 연락처를 알고 B 또한 A의 연락처를 아는 것을 뜻한다.) 이 존재하여 만일 집 C에 문제가 생겨도 DEAB 순으로 서로 연락이 가능해야 함을 뜻한다. 이러한 비상연락망을 만들기 위해서 각 집마다 다른 집의 연락처를 모두 알고 있다면 제일 이상적이겠지만, (비용 또는 보안의 문제 때문에) 각 집에서 알아야 하는 연락처의 개수를 최소화 하고 싶다. 이러한 상황에서 각 집은 최소한 몇개의 다른 집의 연락처를 알아야 할까? 만일 $n=5$라 가정해 보자. 만일 모든 집이 ..
Discrete Mathematics/Graph Theory  |  2017. 2. 21. 12:59
Problems and Solutions #018
Problem #018 어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라의 모든 마을을 한번씩 거쳐갈 수 있는 길이 존재함을 증명하여라. 우선 문제를 수학적 용어로 다시 풀어 써 보자. $n$개의 마을을 $n$개의 점 $a_1,\, a_2,\, \ldots,\, a_n$이라 하고, 이 $n$개의 점으로 이루어진 완전유향그래프(complete digraph)를 생각하자. 이 때, $n$개의 점을 한번씩 모두 지나는 경로\[ a_{i_{1}} \rightarrow a_{i_{2}} \righ..
Discrete Mathematics/Graph Theory  |  2017. 2. 16. 11:52
Problems and Solutions #001
Problem #001 어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라에 어떤 마을이 존재하여, 이 마을로부터 다른 모든 마을을 갈 수 있음을 증명하여라. 각 마을을 $a_1,\, a_2,\, \ldots,\, a_n$와 같이 나타내자. 또한 임의의 $k = 1,\,2,\, \ldots,\, n$에 대하여, $\abs{a_k}$를 마을 $a_k$ 로부터 갈 수 있는 모든 마을의 개수라 하자. 따라서 이 문제는 $\abs{a_k}=n$인 $k$가 존재함을 증명하는 문제와 같다. 이제 $k..
Discrete Mathematics/Graph Theory  |  2016. 7. 29. 04:12

티스토리툴바