4 × 4 격자에서 왼쪽 아래에서 오른쪽 위로, 위로와 오른쪽으로만 가는 경로는 8!/(4!·4!) = 70가지입니다. 작업대는 이를 두 번째 링크에서 보여 줍니다. 대부분은 대각선 위로 올라가지 않는다는 규칙을 더하며, 그러면 수는 8!/(4!·5!) = 14가 됩니다. 두 공식은 분모의 n + 1 배만큼 다르며, 그것이 카탈란 보정 전부입니다.
금지된 56개 경로는 흩어져 있지 않습니다. 반사 논증에 따르면 대각선을 넘는 것은 이동된 끝점으로 가는 경로와 일대일로 대응하며, 그 수는 8!/(3!·5!) = 56입니다. 따라서 70 − 56 = 14이고 두 화면이 일치합니다. 같은 수열 1, 2, 5, 14, 42는 곱셈 사슬에 괄호를 넣는 방법, 볼록 다각형의 삼각분할, 허용되는 괄호식을 셉니다. 세 번째 링크는 다음 값인 C₅ = 10!/(5!·6!) = 42, 칠각형의 삼각분할 수입니다.
답
14
읽는 방법
작업대의 8!/(4!·5!)로 쓴 C₄입니다. 두 번째 링크는 제한 없는 세기 8!/(4!·4!) = 70이고, 세 번째는 다음 카탈란 수 42입니다.
출처
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.