모츠킨 수

수학에서 모츠킨 수()는 원 위의 주어진 개수의 점들 사이에서 교차하지 않는 현들을 그리는 방법의 가짓수이다. 기하학·조합론·수론에서 다양하게 응용된다.

 정의 
섬네일|(0, 0)부터 (4, 0)까지의 경로 가운데, y축 밑으로 떨어지지 않으며 →·↗·↘와 같은 경로만으로 이루어진 경우는 총 9가지이다. 따라서 4번째 모츠킨 수는 9이다.
음이 아닌 정수 에 대하여, 번째 모츠킨 수 은 다음과 같은 조합론 문제들의 답이다.
 개의 공원점의 일부를 잇는 서로 교차하지 않는 현들을 그리는 방법의 수
 시작점 , 끝점 , 보폭 의  속의 격자 경로의 수
 개의 변을 갖는 이진 트리의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)
처음 몇 모츠킨 수는 다음과 같다.
 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, ... 
모츠킨 소수()의 열은 다음과 같다.
2, 127, 15511, 953467954114363 

 성질 
 점화식 
모츠킨 수에 대하여 다음과 같은 점화식이 성립한다.

 항등식 
모츠킨 수는 바닥 함수 및 이항 계수 및 카탈랑 수를 사용하여 다음과 같이 나타낼 수 있다.

 생성 함수 
모츠킨 수의 생성 함수는 다음과 같다.

 수론적 성질 
소인수 를 갖는 모츠킨 수의 점근 밀도는 다음과 같은 하계를 갖는다.

 예 
4개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 9가지가 있다. 따라서 이다.
225픽셀
5개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 21가지가 있다. 따라서 이다.
525픽셀

 역사 
시어도어 모츠킨()의 이름을 땄다.

 같이 보기 
 격자 그래프

 참고 문헌 



 외부 링크 


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