대각선을 넘지 않고 위로 넷, 옆으로 넷. 70개 경로 중 14개

중앙 이항계수는 모든 경로를 세고 카탈란 공식은 허용되는 경로를 셉니다.

통계와 데이터 · 난이도: 고전적인 결과 · 업데이트 2026-11-10

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

계산기에서 풀어 보기

이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.

본 사이트는 독립적인 제3자 도구 사이트입니다. Casio, Texas Instruments 및 그 대리점과 제휴·후원·승인 관계가 없습니다. 모델명과 제품명은 각 권리자의 상표이며, 기기를 식별하기 위한 용도로만 표시됩니다.

이 매뉴얼의 키 조작 순서는 본 사이트가 온라인 계산기를 렌더링할 때 사용하는 것과 동일한 자체 레이아웃 데이터와 공개된 제품 정보를 바탕으로 작성했습니다. 사양과 지역별 구성은 실제 기기 및 제조사의 최신 자료로 확인합니다.