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

피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 2
이번 글에서는 저번 글 피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 1 에서 증명한 피보나치/루카스 수열과 삼각함수와의 관계를 다시 한 번 정리하면 다음과 같다: 임의의 음이 아닌 정수 n∈N에 대하여 복소수 zn=nπ2−iln⁡(ϕn)을 정의하면 cos⁡(zn)=in2Ln,sin⁡(zn)=in52iFn 의 관계가 성립한다. 이를 이용하여 삼각함수 항등식이 하나 주어졌을 때, 그에 해당되는 피보나치/루카스 수열에 대한 항등식을 증명할 수 있다. 여기서 zn은 n에 대하여 선형(linear)이므로 $z_n = n z_..
Discrete Mathematics/Combinatorics  |  2020. 3. 16. 20:24
피보나치(Fibonacci) 수열, 루카스(Lucas) 수열, 그리고 삼각함수 - 1
피보나치 수열(Fibonacci sequence)은 F0=0, F1=1, Fn+2=Fn+1+Fn으로 정의된 대중적으로 가장 잘 알려진 수열 중 하나이다. 이 수열에 대한 성질에 대하여 몇 개의 글을 작성한 적이 있다. 피보나치 수열(Fibonacci sequence)과 그래프(graph) 피보나치 수열(Fibonacci sequence)과 역코탄젠트(arccotangent) 함수 피보나치 수(Fibonacci number) 판별법 한 편 루카스 수열(Lucas sequence)은 피보나치 수열과 초기값은 다르지만 동일한 점화관계(recurrence relation)을 갖는 수열로서, L0=2, L1=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)=a0+a1x+a2x2+⋯+adxd 가 주어졌을 때, 무한급수의 선형성을 이용하면 \[ \sum_..
Discrete Mathematics/Combinatorics  |  2020. 1. 24. 12:39
이항계수(binomial coefficient)들의 조화평균과 이차평균
예전에 "이항계수(binomial coefficient)들의 산술평균과 기하평균"이라는 주제로 글을 올린 적이 있다. 이번에는 이 주제를 좀 더 확장하여 이항계수들의 조화평균(harmonic mean) Hn과 이차평균(quadratic mean) Qn에 대해서 생각해 보자. 여기서 Hn과 Qn은 다음과 같이 정의되는 값이다. Hn=n+1∑k=0n1(nk),Qn=1n+1∑k=0n(nk)2 이번에도 Hnn과 Qnn의 극한값을 각각 계산해 보도록 하자. $\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)가 나타난다. (n0),(n1),⋯,(nn). 이제 위 이항계수들의 산술평균(arithmetic mean)과 기하평균(geometric mean)을 각각 An, Gn이라 하자. 다시 말해 An과 Gn은 아래와 같이 정의되는 수이다. An:=1n+1∑k=0n(nk),Gn:=∏k=0n(nk)n+1. 이번 글에서 계산해볼 것은 Ann과 $\sqr..
Discrete Mathematics/Combinatorics  |  2017. 4. 22. 23:15
Problems and Solutions #022
Problem #022m×n (단, m≤n) 크기의 격자가 있다고 하자. 이 격자에서 찾을 수 있는 '정사각형'은 모두 몇 개일까? 이 격자에서 찾을 수 있는 '직사각형'은 모두 몇 개일까? (1) 주어진 격자에서 찾을 수 있는 1×1 크기의 정사각형의 수는 모두 mn개이다. 또한 이 격자에서 찾을 수 있는 2×2 크기의 정사각형의 수는 모두 (m−1)(n−1)개이다. 일반적으로 1≤k≤m에 대하여 k×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 (한가지 대상을 두가지 다른 방법으로 셈하여 그 두개의 셈이 서로 같음을 보이는 방법)을 바탕으로 하고 있다. (nr)=(nn−r)증명. n명의 지원자 중에서 r명의 합격자를 선택하는 경우의 수 (nr)은 n명의 지원자 중에서 n−r명의 불합격자를 선택하는 경우의 수 (nn−r)와 같다. $\displaystyle{{n ..
Discrete Mathematics/Combinatorics  |  2015. 12. 2. 04:03

티스토리툴바