카탈란 수 (Catalan numbers) - 편집 역사

2021년 2월 17일 (수) 13:01에 Pythagoras0님의 편집

2021-02-17T13:01:40Z

Pythagoras0: /* 메타데이터 */ 새 문단

2020-12-28T13:17:00Z

메타데이터: 새 문단

2020년 12월 28일 (월) 10:59에 Pythagoras0님의 편집

2020-12-28T10:59:55Z

2020년 11월 16일 (월) 14:43에 Pythagoras0님의 편집

2020-11-16T14:43:33Z

2020년 11월 12일 (목) 07:17에 Pythagoras0님의 편집

2020-11-12T07:17:34Z

2015년 3월 23일 (월) 06:54에 Pythagoras0님의 편집

2015-03-23T06:54:56Z

2014년 8월 30일 (토) 11:39에 Pythagoras0님의 편집

2014-08-30T11:39:05Z

Pythagoras0: Pythagoras0 사용자가 카탈란 수열(Catalan numbers) 문서를 카탈란 수 (Catalan numbers) 문서로 옮겼습니다.

2013-12-13T22:09:27Z

Pythagoras0 사용자가 카탈란 수열(Catalan numbers) 문서를 카탈란 수 (Catalan numbers) 문서로 옮겼습니다.

2013년 12월 12일 (목) 16:28에 Pythagoras0님의 편집

2013-12-12T16:28:01Z

2013년 12월 12일 (목) 15:57에 Pythagoras0님의 편집

2013-12-12T15:57:10Z

@@ 154번째 줄: / 154번째 줄: @@
 [[분류:수열]]
-== 메타데이터 ==
+==메타데이터==
 ===위키데이터===
 * ID :  [https://www.wikidata.org/wiki/Q270513 Q270513]

← 이전 판		2020년 12월 28일 (월) 13:17 판
153번째 줄:		153번째 줄:
	[[분류:조합수학]]		[[분류:조합수학]]
	[[분류:수열]]		[[분류:수열]]
		+
		+	== 메타데이터 ==
		+
		+	===위키데이터===
		+	* ID : [https://www.wikidata.org/wiki/Q270513 Q270513]

@@ 7번째 줄: / 7번째 줄: @@
 [[파일:카탈란 수열(Catalan numbers)1.png]]
-−
-−
 ==점화식==
@@ 18번째 줄: / 18번째 줄: @@
 (n+2)c_{n+1}+(-4 n-2)c_{n}=0
 </math>
-−
-−
 ==생성함수==
-* 기본적인 내용에 대해서는  [[생성함수]] 항목을 참조
+* 기본적인 내용에 대해서는  [[생성함수]] 항목을 참조
 * 카탈란 수열의 생성함수는 다음과 같이 주어짐
 :<math>G(x)= c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots=\frac{1-\sqrt{1-4x}}{2x}</math>
@@ 37번째 줄: / 37번째 줄: @@
 :<math>G(x)= \frac{1-\sqrt{1-4x}}{2x}</math>■
-−
-−
 ==점근 급수==
@@ 54번째 줄: / 54번째 줄: @@
 * [[점근 급수(asymptotic series)]]
-−
 ==격자경로와 카탈란 수==
@@ 64번째 줄: / 64번째 줄: @@
 * (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구한 다음, 그 중에서 y=x를 넘어서 가는 방법의 수를 빼면 된다. 이 방법의 수가 얼마가 되겠느냐를 구하는 과정에서 일대일대응이 등장한다.
-−
 ===일단계===
 (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자. 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.  각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 <math>{2n \choose n}</math>이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 <math>{2n \choose n}</math>이다.
-−
 ===이단계===
@@ 86번째 줄: / 86번째 줄: @@
 그 결과는 <math>(0,0)</math>에서 출발하여 <math>(n+1,n-1)</math>에 도착하는 경로일 것이다.
 [[파일:카탈란 수열(Catalan numbers)result.jpg]]
 위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 이 대응은 일대일 대응이다. 일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.
@@ 95번째 줄: / 95번째 줄: @@
 :<math>{2n \choose n}-{2n \choose n+1}=\frac{1}{n+1}{2n \choose n}</math> ■
-−
-−
-−
 ==적분표현==
@@ 111번째 줄: / 111번째 줄: @@
 * [[수학사 연표]]
-−
-−
 ==메모==
 * [http://bomber0.byus.net/index.php/2008/05/10/643 일대일대응 그리고 카탈란의 수(Catalan Numbers)]
-−
 ==관련된 항목들==
@@ 133번째 줄: / 133번째 줄: @@
 ** https://oeis.org/A000108
-−
-==사전 형태의 자료==
+==사전 형태의 자료==
 * http://ko.wikipedia.org/wiki/
@@ 141번째 줄: / 141번째 줄: @@
-−
 ==리뷰, 에세이, 강의노트==
 * Pak, Igor. “History of Catalan Numbers.” arXiv:1408.5711 [math], August 25, 2014. http://arxiv.org/abs/1408.5711.
-−
 ==관련도서==
-* Thomas Koshy [http://www.amazon.com/exec/obidos/ASIN/019533454X/ref=nosim/addallbooksearch Catalan Numbers with Applications], Oxford University Press, USA, 2008
+* Thomas Koshy [http://www.amazon.com/exec/obidos/ASIN/019533454X/ref=nosim/addallbooksearch Catalan Numbers with Applications], Oxford University Press, USA, 2008
 [[분류:조합수학]]
 [[분류:수열]]

@@ 67번째 줄: / 67번째 줄: @@
 ===일단계===
-(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.<br> 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.  각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 <math>{2n \choose n}</math>이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 <math>{2n \choose n}</math>이다.
+(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자. 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.  각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 <math>{2n \choose n}</math>이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 <math>{2n \choose n}</math>이다.
@@ 103번째 줄: / 103번째 줄: @@
 ==적분표현==
-* <math>c_n=\int_{0}^{1} 2^{2n+1}{\cos^{2n} \pi x}\, {\sin^2 \pi x}\,dx</math><br>
+* <math>c_n=\int_{0}^{1} 2^{2n+1}{\cos^{2n} \pi x}\, {\sin^2 \pi x}\,dx</math>
@@ 130번째 줄: / 130번째 줄: @@
 ==매스매티카 파일 및 계산 리소스==
-* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]<br>
+* [http://www.research.att.com/%7Enjas/sequences/index.html The On-Line Encyclopedia of Integer Sequences]
 ** https://oeis.org/A000108

@@ 15번째 줄: / 15번째 줄: @@
 <math>c_{n+1}=c_0c_n+c_1c_{n-1}+\cdots+c_nc_0 \label{rec}</math>
 * [[홀로노믹 수열]]
-$$
+:<math>
 (n+2)c_{n+1}+(-4 n-2)c_{n}=0
-$$
+</math>
@@ 29번째 줄: / 29번째 줄: @@
 ===증명===
 생성함수를 다음과 같이 두자
-$$G(x)= c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots$$
+:<math>G(x)= c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots</math>
 다음을 얻을 수 있다
 :<math>x G(x)^2= (c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n + \cdots)^2=c_0^2x+(c_0c_1+c_1c_0)x^2+(c_0c_2+c_1c_1+c_2c_0)x^3+\cdots=G(x)-1</math>
@@ 42번째 줄: / 42번째 줄: @@
 ==점근 급수==
-* 멱급수 $(1-x)^{-1/2}=\sum_{n=0}^{\infty} a_n x^n$의 계수는 다음과 같은 점근 급수를 갖는다
+* 멱급수 <math>(1-x)^{-1/2}=\sum_{n=0}^{\infty} a_n x^n</math>의 계수는 다음과 같은 점근 급수를 갖는다
-$$
+:<math>
 a_n \sim \frac{1}{\sqrt{\pi n}}\left(1-\frac{1}{8 n}+\frac{1}{128 n^2}+\frac{5}{1024 n^3}+O(\frac{1}{n^4})\right)
-$$
+</math>
 * 카탈란 상수는 다음을 만족한다
-$$
+:<math>
 c_n=\frac{4^n}{n+1}a_n \sim \frac{4^n}{(n+1)\sqrt{\pi n}}\left(1-\frac{1}{8 n}+\frac{1}{128 n^2}+\frac{5}{1024 n^3}+O(\frac{1}{n^4})\right)
-$$
+</math>
 * [[스털링 공식]] 을 이용하여 다음을 증명할 수 있다
 :<math>c_{n}\sim \frac{4^{n}}{\sqrt{\pi n}(n+1)}(1-\frac{1}{8n})</math>
@@ 61번째 줄: / 61번째 줄: @@
 :<math>{2n \choose n}</math>
 *  (0,0)에서 (n,n)까지 격자점을 지나는 최단거리의 경로 중에서 직선 <math>y=x</math>를 넘지 않는 경우의 수 (카탈란 수)
-$$\frac{1}{n+1}{2n \choose n}$$
+:<math>\frac{1}{n+1}{2n \choose n}</math>
 * (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구한 다음, 그 중에서 y=x를 넘어서 가는 방법의 수를 빼면 된다. 이 방법의 수가 얼마가 되겠느냐를 구하는 과정에서 일대일대응이 등장한다.
@@ 67번째 줄: / 67번째 줄: @@
 ===일단계===
-(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.<br> 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.  각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 ${2n \choose n}$이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 ${2n \choose n}$이다.
+(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.<br> 이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.  각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다. 따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 <math>{2n \choose n}</math>이다. 즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 <math>{2n \choose n}</math>이다.
 ===이단계===
-이제 직선 $y=x$를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 $y=x+1$과 만나게 될 것이다.
+이제 직선 <math>y=x</math>를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 <math>y=x+1</math>과 만나게 될 것이다.
 [[파일:카탈란 수열(Catalan numbers)meeting.jpg]]
-이 때, 이 경로의 $(0,0)$에서부터 $y=x+1$과 처음으로 만나는 점까지를 잘라서, $y=x$에 대칭시키자.
+이 때, 이 경로의 <math>(0,0)</math>에서부터 <math>y=x+1</math>과 처음으로 만나는 점까지를 잘라서, <math>y=x</math>에 대칭시키자.
 [[파일:카탈란 수열(Catalan numbers)Symmetrization.jpg]]
@@ 84번째 줄: / 84번째 줄: @@
 [[파일:카탈란 수열(Catalan numbers)translation.jpg]]
-그 결과는 $(0,0)$에서 출발하여 $(n+1,n-1)$에 도착하는 경로일 것이다.
+그 결과는 <math>(0,0)</math>에서 출발하여 <math>(n+1,n-1)</math>에 도착하는 경로일 것이다.
 [[파일:카탈란 수열(Catalan numbers)result.jpg]]
@@ 90번째 줄: / 90번째 줄: @@
 위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 이 대응은 일대일 대응이다. 일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.
-$y=x$를 넘어서서 가는 경로는 $(0,0)$에서 $(n+1,n-1)$까지 가는 경로와 일대일 대응되므로 그 개수는 <math>{2n \choose n+1}</math>이다.
+<math>y=x</math>를 넘어서서 가는 경로는 <math>(0,0)</math>에서 <math>(n+1,n-1)</math>까지 가는 경로와 일대일 대응되므로 그 개수는 <math>{2n \choose n+1}</math>이다.
 따라서 처음에 제기했던 문제의 답은 다음과 같다

@@ 125번째 줄: / 125번째 줄: @@
 * [[Associahedron]]
 * [[모츠킨 수 (Motzkin number)]]
+* [[격자 경로]]

← 이전 판	2014년 8월 30일 (토) 11:39 판
142번째 줄:	142번째 줄:


	+	==리뷰, 에세이, 강의노트==
	+	* Pak, Igor. “History of Catalan Numbers.” arXiv:1408.5711 [math], August 25, 2014. http://arxiv.org/abs/1408.5711.

← 이전 판	2013년 12월 13일 (금) 22:09 판
(차이 없음)

← 이전 판		2013년 12월 12일 (목) 16:28 판
124번째 줄:		124번째 줄:
	* [[Dyck 경로]]		* [[Dyck 경로]]
	* [[Associahedron]]		* [[Associahedron]]
		+	* [[모츠킨 수 (Motzkin number)]]
		+
		+