모츠킨 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 조합론적 정의
- 2.2. 수열
3. 성질
4. 예시
- 4.1. 격자 경로
5. 역사
6. 추가 정보
- 6.1. 모츠킨 소수
- 6.2. 다양한 표현
참조

1. 개요

모츠킨 수는 조합론 문제의 해답으로 나타나는 수열로, 음이 아닌 정수 n에 대해 정의된다. 이 수는 n개의 점을 연결하는 교차하지 않는 현의 개수, 특정 격자 경로의 개수, 그리고 n개의 변을 가진 이진 트리의 수 등 다양한 조합론적 문제의 해답과 일치한다. 모츠킨 수는 점화식, 이항 계수, 카탈랑 수, 생성 함수 등을 통해 표현될 수 있으며, 모츠킨 소수는 소수인 모츠킨 수를 의미한다. 시어도어 모츠킨의 이름을 따서 명명되었으며, 수학의 여러 분야에서 다양한 방식으로 표현될 수 있다.

더 읽어볼만한 페이지

열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 $\{1,2,\ldots,n\}$ 의 순열에서 $a_i>a_{i+1}$ 인 $i$ 가 정확히 $m$ 개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
정수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
정수열 - 소수 (수론)
소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.
수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
수론 - 최소공배수
최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.

모츠킨 수

2. 정의

음이 아닌 정수 n에 대해, n번째 모츠킨 수는 다음과 같은 조합론 문제들의 답이다.

n개의 공원점의 일부를 잇는 서로 교차하지 않는 현들을 그리는 방법의 수
시작점 (0,0), 끝점 (n,0), 보폭 (1,-1),(1,0),(1,1)의 $\mathbb Z\times\{0,1,2,\dots,\}$ 속의 격자 경로의 수
n개의 변을 갖는 이진 트리의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)

(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, ...

'''모츠킨 소수'''(prime Motzkin numbers^영어)는 다음과 같다.

:2, 127, 15511, 953467954114363

n에 대한 모츠킨 수는 다음 조건을 만족하는 길이 n - 1인 정수열의 개수와 같다.

첫 항과 끝 항은 1 또는 2이며, 인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

또한, 다음 조건을 만족하는 길이 n + 1인 정수열의 개수와도 같다.

첫 항과 끝 항은 1이며, 인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

2차원 데카르트 좌표 평면에서 다음 조건을 만족하는 경로의 개수와도 같다.

(0, 0)에서 출발하여 (n, 0)까지 도달한다.
좌표가 모두 음이 아닌 정수인 점(격자점)만을 연결한 꺾은선이다.
어떤 격자점에서 그 다음 격자점으로 향하는 위치 벡터는 (1, -1), (1, 0), (1, 1) 중 하나이다.

Donaghey와 Shapiro (1977)의 조사에 따르면 수학의 여러 분야에서 모츠킨 수는 최소 14가지 다른 표현이 존재한다. Guibert, Pergola, Pinzani (2001)는 벡실러리 대합이 모츠킨 수에 의해 열거된다는 것을 보였다.

2. 1. 조합론적 정의

음이 아닌 정수

n

에 대하여,

n

번째 '''모츠킨 수'''

M_n

은 다음과 같은 조합론 문제들의 답이다.

$n$ 개의 공원점의 일부를 잇는 서로 교차하지 않는 현들을 그리는 방법의 수
시작점 $(0,0)$ , 끝점 $(n,0)$ , 보폭 $(1,-1),(1,0),(1,1)$ 의 $\mathbb Z\times\{0,1,2,\dots,\}$ 속의 격자 경로의 수
$n$ 개의 변을 갖는 이진 트리의 수 (단, 하나뿐인 자식 노드의 경우 왼쪽과 오른쪽을 구분하지 않아야 한다)

prime Motzkin numbers^영어인 모츠킨 소수의 열은 다음과 같다.

:2, 127, 15511, 953467954114363

n

에 대한 모츠킨 수는 격자의 오른쪽 위 사분면에서 좌표 (0, 0)에서 좌표 (

n

, 0)까지

n

단계로 가는 경로의 수로, 각 단계에서 오른쪽으로만(위, 아래 또는 직선) 이동할 수 있지만

y

= 0 축 아래로 내려갈 수 없다.

수학의 여러 분야에서 모츠킨 수의 최소 14가지 다른 표현이 존재한다. 벡실러리 대합이 모츠킨 수에 의해 열거된다는 연구 결과도 있다.

2. 2. 수열

처음 몇 모츠킨 수는 다음과 같다.

: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, ...

3. 성질

모츠킨 수는 여러 가지 수학적 성질을 갖는다. 모츠킨 수의 적분 표현은 다음과 같다.^[1]

: $M_{n}=\frac{2}{\pi}\int_0^\pi \sin(x)^2(2\cos(x)+1)^n dx$ .

소수인 모츠킨 수를 모츠킨 소수라고 한다. 현재까지 알려진 모츠킨 소수는 2, 127, 15511, 953467954114363 네 개이다.

3. 1. 점화식

모츠킨 수는 다음과 같은 점화식을 만족한다.^[1]

:

M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}

3. 2. 이항 계수 및 카탈랑 수와의 관계

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

\lfloor x\rfloor

는 바닥 함수)

:

M_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom n{2k}C_k

역으로, 카탈랑 수는 모츠킨 수를 사용하여 다음과 같이 표현할 수 있다.^[1]

:

C_{n+1}=\sum_{k=0}^{n} \binom{n}{k} M_k

3. 3. 생성 함수

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

:

\sum_{n=0}^nM_nx^n=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}=\frac{1}{1-x-\dfrac{x^2}{1-x-\dfrac{x^2}{1-x-\dfrac{x^2}\ddots}}}

3. 4. 점근적 거동

모츠킨 수는 다음과 같은 점근적 거동을 보인다.^[1]

:

M_{n}\sim \frac{1}{2 \sqrt{\pi}}\left(\frac{3}{n}\right)^{3/2} 3^n, \quad n \to \infty

.

4. 예시

원 위에 4개의 점이 있을 때, 각 점을 서로 교차하지 않게 잇는 방법은 9가지이다. 따라서 4번째 모츠킨 수 M₄는 9이다.

원 위에 5개의 점이 있을 때, 각 점을 서로 교차하지 않게 잇는 방법은 21가지이다. 따라서 5번째 모츠킨 수 M₅는 21이다.

4. 1. 격자 경로

음이 아닌 정수

n

에 대하여,

n

번째 모츠킨 수는 시작점

(0,0)

, 끝점

(n,0)

, 보폭

(1,-1),(1,0),(1,1)

의

\mathbb Z\times\{0,1,2,\dots,\}

속의 격자 경로의 수이다.

n

에 대한 모츠킨 수는 각 단계에서 오른쪽으로만(위, 아래 또는 직선) 이동할 수 있지만

y

= 0 축 아래로 내려갈 수 없는 경우, 격자의 오른쪽 위 사분면에서 좌표 (0, 0)에서 좌표 (

n

, 0)까지

n

단계로 가는 경로의 수를 제공한다.

또한, 2차원 데카르트 좌표 평면에서 다음 조건을 만족하는 경로의 개수와도 같다.

(0, 0)에서 출발하여 ( $n$ , 0)까지 도달한다.
경로는 좌표가 모두 음이 아닌 정수인 점(격자점)만을 연결한 꺾은선이다.
어떤 격자점에서 그 다음 격자점으로 향하는 위치 벡터는 (0,1), (1,1), (1, -1) 중 하나이다.

5. 역사

Theodore Motzkin|시어도어 모츠킨^영어의 이름을 따서 명명되었다.

6. 추가 정보

모츠킨 수는 수학의 여러 분야에서 최소 14가지의 서로 다른 방식으로 표현될 수 있으며,^[1] 벡실러리 인볼루션의 개수를 계산하는 데 사용될 수 있다.^[2]

모츠킨 수는 다음 조건을 만족하는 길이 n-1의 정수열의 개수와 같다.

첫 항과 끝 항은 1 또는 2이다.
인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

또한, 다음 조건을 만족하는 길이 n+1의 정수열의 개수와도 같다.

첫 항과 끝 항은 1이다.
인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

2차원 데카르트 좌표 평면에서, (0, 0)에서 출발하여 (n, 0)에 도달하는 경로 중 다음 조건을 만족하는 경로의 개수는 모츠킨 수와 같다.

경로는 좌표가 모두 음이 아닌 정수인 점(격자점)만을 연결한 꺾은선이다.
각 격자점에서 다음 격자점으로 이동하는 위치 벡터는 (0,1), (1,1), (1, -1) 중 하나이다.

6. 1. 모츠킨 소수

소수인 모츠킨 수이다. 현재까지 알려진 모츠킨 소수는 다음과 같다.

모츠킨 소수
2
127
15511
953467954114363

6. 2. 다양한 표현

도너기(Donaghey)와 샤피로(Shapiro)가 1977년에 조사한 바에 따르면, 수학의 여러 분야에서 모츠킨 수는 최소 14가지의 서로 다른 방식으로 표현될 수 있다.^[1] 귀베르(Guibert), 페르골라(Pergola), 핀자니(Pinzani)는 2001년에 벡실러리 인볼루션의 개수가 모츠킨 수로 계산될 수 있음을 보였다.^[2]

n*에 대한 모츠킨 수는 다음 조건을 만족하는 길이 *n* - 1의 정수열의 개수와 같다.

첫 항과 끝 항은 1 또는 2이며, 인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

또한, 다음 조건을 만족하는 길이 *n* + 1의 정수열의 개수와도 같다.

첫 항과 끝 항은 1이며, 인접한 두 항 간의 차이는 -1, 0, 1 중 하나이다.

게다가, 2차원 데카르트 좌표 평면에서 다음 조건을 만족하는 경로의 개수와도 같다.

(0, 0)에서 출발하여 (*n*, 0)까지 도달한다.
경로는 좌표가 모두 음이 아닌 정수인 점(격자점)만을 연결한 꺾은선이다.
어떤 격자점에서 그 다음 격자점으로 향하는 위치 벡터는 (0,1), (1,1), (1, -1) 중 하나이다.

예를 들어, 다음 그림은 (0, 0)에서 (4, 0)까지 도달하는 9가지 모츠킨 경로를 보여준다.

참조

_[1] 논문 Combinatorics of Generalized Motzkin Numbers https://cs.uwaterloo[...] 2015
_[2] 웹인용 Structure and asymptotics for Motzkin numbers modulo primes using automata https://www.research[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com