모츠킨 수
수학에서 모츠킨 수(영어: 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가지가 있다. 따라서 이다.
역사[편집]
시어도어 모츠킨(영어: Theodore Motzkin)의 이름을 땄다.
같이 보기[편집]
각주[편집]
- ↑ 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.