모츠킨 수
수학에서 모츠킨 수(영어: Motzkin number)는 원 위의 주어진 개수의 점들 사이에서 교차하지 않는 현들을 그리는 방법의 가짓수이다. 기하학·조합론·수론에서 다양하게 응용된다.
정의
편집음이 아닌 정수 에 대하여, 번째 모츠킨 수 은 다음과 같은 조합론 문제들의 답이다.
- 개의 공원점의 일부를 잇는 서로 교차하지 않는 현들을 그리는 방법의 수
- 시작점 , 끝점 , 보폭 의 속의 격자 경로의 수
- 개의 변을 갖는 이진 트리의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)
처음 몇 모츠킨 수는 다음과 같다.
- 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의 수열 A001006)
모츠킨 소수(영어: prime Motzkin numbers)의 열은 다음과 같다.
성질
편집점화식
편집모츠킨 수에 대하여 다음과 같은 점화식이 성립한다.
항등식
편집모츠킨 수는 바닥 함수 및 이항 계수 및 카탈랑 수를 사용하여 다음과 같이 나타낼 수 있다.
생성 함수
편집모츠킨 수의 생성 함수는 다음과 같다.
수론적 성질
편집소인수 를 갖는 모츠킨 수의 점근 밀도는 다음과 같은 하계를 갖는다.[1]
예
편집4개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 9가지가 있다. 따라서 이다.
5개의 공원점을 잇는 교차하지 않는 현을 그리는 방법에는 다음과 같은 21가지가 있다. 따라서 이다.
역사
편집같이 보기
편집각주
편집- ↑ Burns, Rob (2017). “Structure and asymptotics for Motzkin numbers modulo primes using automata” (영어).
참고 문헌
편집- Donaghey, R.; Shapiro, L. W. (1977). “Motzkin numbers”. 《Journal of Combinatorial Theory》. Series A 23 (3): 291–301. doi:10.1016/0097-3165(77)90020-6. MR 0505544.
외부 링크
편집- Weisstein, Eric Wolfgang. “Motzkin number”. 《Wolfram MathWorld》 (영어). Wolfram Research.