'Discrete Mathematics/Combinatorics'에 해당되는 글 8건

피보나치(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
조합 항등식의 조합론적 증명
이번 글에서는 몇 가지 조합 항등식(combination identity)들을 대수적인 방법이나 기타 다른 방법을 이용하지 않고 오직 조합론적 증명(combinatorial proof) 방법만을 이용하여 증명하려고 한다. 모든 증명은 기본적인 Double counting (한가지 대상을 두가지 다른 방법으로 셈하여 그 두개의 셈이 서로 같음을 보이는 방법)을 바탕으로 하고 있다. $\displaystyle{{n \choose r}= {n \choose n-r}}$증명. $n$명의 지원자 중에서 $r$명의 합격자를 선택하는 경우의 수 ${n \choose r}$은 $n$명의 지원자 중에서 $n-r$명의 불합격자를 선택하는 경우의 수 ${n \choose n-r}$와 같다. $\displaystyle{{n ..
Discrete Mathematics/Combinatorics  |  2015. 12. 2. 04:03

티스토리툴바