모츠킨 수 문서 원본 보기

{{위키데이터 속성 추적}}
[[수학]]에서 '''모츠킨 수'''({{llang|en|Motzkin number}})는 [[원 (기하학)|원]] 위의 주어진 개수의 점들 사이에서 교차하지 않는 [[현 (기하학)|현]]들을 그리는 방법의 가짓수이다. [[기하학]]·[[조합론]]·[[수론]]에서 다양하게 응용된다.

== 정의 ==
[[파일:Motzkin4.svg|섬네일|(0, 0)부터 (4, 0)까지의 경로 가운데, ''y''축 밑으로 떨어지지 않으며 →·↗·↘와 같은 경로만으로 이루어진 경우는 총 9가지이다. 따라서 4번째 모츠킨 수는 9이다.]]
음이 아닌 정수 <math>n</math>에 대하여, <math>n</math>번째 '''모츠킨 수''' <math>M_n</math>은 다음과 같은 조합론 문제들의 답이다.
* <math>n</math>개의 [[공원점]]의 일부를 잇는 서로 교차하지 않는 [[현 (기하학)|현]]들을 그리는 방법의 수
* 시작점 <math>(0,0)</math>, 끝점 <math>(n,0)</math>, 보폭 <math>(1,-1),(1,0),(1,1)</math>의 <math>\mathbb Z\times\{0,1,2,\dots,\}</math> 속의 [[격자 경로]]의 수
* <math>n</math>개의 변을 갖는 [[이진 트리]]의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)
처음 몇 모츠킨 수는 다음과 같다.
: [[1]], 1, [[2]], [[4]], [[9]], [[21]], [[51]], [[127]], [[323]], [[835]], [[2188]], [[5798]], 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... {{OEIS|id=A001006}}
'''모츠킨 소수'''({{llang|en|prime Motzkin numbers}})의 열은 다음과 같다.
:2, 127, 15511, 953467954114363 {{OEIS|id=A092832}}

== 성질 ==
=== 점화식 ===
모츠킨 수에 대하여 다음과 같은 [[점화식]]이 성립한다.
:<math>M_n=M_{n-1}+\sum_{k=0}^{n-2}M_kM_{n-k-2}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}</math>

=== 항등식 ===
모츠킨 수는 [[바닥 함수]] 및 [[이항 계수]] 및 [[카탈랑 수]]를 사용하여 다음과 같이 나타낼 수 있다.
:<math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom n{2k}C_k</math>

=== 생성 함수 ===
모츠킨 수의 [[생성 함수]]는 다음과 같다.
:<math>\sum_{n=0}^nM_nx^n=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}=\frac1{1-x-\dfrac{x^2}{1-x-\dfrac{x^2}{1-x-\dfrac{x^2}\ddots}}}</math>

=== 수론적 성질 ===
[[소인수]] <math>p\ge5</math>를 갖는 모츠킨 수의 [[점근 밀도]]는 다음과 같은 [[상한과 하한|하계]]를 갖는다.<ref>{{웹 인용|성=Burns|이름=Rob|연도=2017|제목=Structure and asymptotics for Motzkin numbers modulo primes using automata|url=https://www.researchgate.net/publication/314182422_Structure_and_asymptotics_for_Motzkin_numbers_modulo_primes_using_automata|언어=en}}</ref>
:<math>\frac2{p(p-1)}</math>

== 예 ==
4개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 9가지가 있다. 따라서 <math>M_4=9</math>이다.
:[[파일:MotzkinChords4.svg|225픽셀]]
5개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 21가지가 있다. 따라서 <math>M_5=21</math>이다.
:[[파일:MotzkinChords5.svg|525픽셀]]

== 역사 ==
[[시어도어 모츠킨]]({{llang|en|Theodore Motzkin}})의 이름을 땄다.

== 같이 보기 ==
* [[격자 그래프]]

== 참고 문헌 ==
{{각주}}
* {{저널 인용 | last1 = Donaghey | first1 = R. | last2 = Shapiro | first2 = L. W. | title = Motzkin numbers | journal = Journal of Combinatorial Theory | series = Series A | volume = 23 | issue = 3 | year = 1977 | pages = 291–301 | mr = 0505544 | doi = 10.1016/0097-3165(77)90020-6}}

== 외부 링크 ==
* {{매스월드|id=MotzkinNumber|title=Motzkin number}}

[[분류:열거조합론]]
[[분류:정수열]]