Category Archives: Discrete Mathematics

Notorious bound for Ramsey number for two coloring

Lemma. If , then . Proof. 꼭짓점이 인 완전그래프 을 생각해보자. 그러면 에는 blue로 칠해진 edge가 적어도 한 개가 있거나() 모두 red인 경우거나 둘 중 하나다. 그러므로 이다. 모두 red로 칠해진 완전그래프 를 생각해보면 induced subgraph로서 blue로 된 는 없고, red로 된 또한 없다. 그러므로 이므로 이다.   Theorem. If and , then (1)  … Read More »

Bernoulli number and Zeta function

이 글에서는 Bernoulli number와 zeta function과의 관계를 드러내는 식을 증명한다. Definition 1 Define the Bernoulli numbers by the formula 이 Bernoulli number는 계수 비교를 이용해서 , , , , , 이 성립한다. Bernoulli number를 generating function을 이용해서 정의를 했는데, Bernoulli number간의 점화식은 다음과 같다. Proposition 2 For , we have Proof: 계산의 편의를 위해 양변에… Read More »

Catalan number and its closed formula

이 글에서는 카탈란 수의 closed formula를 증명한다. 우선 이 글에서 카탈란 수의 정의는 다음과 같다. Definition 1 The Catalan numbers are a sequence defined by the following recurrence relation: 카탈란 수를 정의했으니, 다음 질문은 이 카탈란 수를 표현할 수 있는 일반식이 무엇인지다. 일반항을 구하는 방법은 여러가지가 있지만, Generating function을 이용해서 찾고자 한다. 잠시 Cauchy product… Read More »