모츠킨 수 계산기

원점에서 시작해 오른쪽으로 n걸음을 걷되, 매 걸음 «위로 한 칸»·«아래로 한 칸»·«제자리(수평)» 중 하나를 골라, 한 번도 기준선(x축) 아래로 내려가지 않고 다시 기준선으로 돌아오는 경로의 수 M(n)입니다. M(0)=1, M(1)=1, M(2)=2, M(3)=4로 이어집니다.

카탈랑 수는 괄호 두 종류(여는 것·닫는 것)만으로 n쌍을 짝짓는 경우를 세고, 모츠킨 수는 거기에 «아무 표시 없음»(수평 걸음)까지 하나 더 넣어 길이 n인 걸음에서 짝이 맞는 경우를 셉니다. 걸음 수 기준 자체가 달라서(카탈랑은 2n걸음, 모츠킨은 n걸음) 나란히 비교하면 n=0,1,2에서는 같지만 n=3부터는 M(n)이 C(n)보다 작습니다(M(3)=4 < C(3)=5) — 자라는 속도도 모츠킨 수가 더 완만합니다(카탈랑은 대략 4ⁿ, 모츠킨은 대략 3ⁿ).

합성곱 점화식 M(n+1) = M(n) + Σ_{k=0}^{n-1} M(k)·M(n-1-k)을 씁니다. 경로가 기준선에 «처음 되돌아오는 지점»으로 나눠 셉니다 — 첫걸음이 수평이면 나머지 n걸음은 그대로 M(n)가지이고, 첫걸음이 위로면 어딘가에서 처음 기준선에 닿을 때까지의 안쪽 경로(M(k))와 그 뒤 나머지 경로(M(n-1-k))를 잇습니다.

네. 합성곱 점화식과는 완전히 다른 유도(생성함수가 만족하는 미분방정식)에서 나온 3항 점화식 (n+2)M(n)=(2n+1)M(n-1)+3(n-1)M(n-2)로도 계산해 넓은 구간에서 대조했습니다.

아니요. 모든 계산은 브라우저 안에서만 이뤄지며 서버로 전송되지 않습니다.