카탈루냐 번호는 어디에서 발생합니까?
-주어진 수의 대괄호 쌍이 있는 psp의 수
-주어진 잎 수를 가진 이진 트리의 수
-n * n 정사각형에서 대각선에 닿지 않는 왼쪽 하단 모서리에서 오른쪽 상단 모서리까지의 경로 수
<사업부>
-n각형을 삼각형으로 나눈 횟수
계산 방법
1) n번째 카탈루냐 수의 공식:
2)
•길이가 2n인 PSS를 가지자
•당연히 여는 중괄호로 시작합니다
•따라서 P = (A)B라고 하면 A와 B는 – 또한 psp(또한 A와 B는 비어 있을 수 있음)
•A의 길이 = 2k이면 시퀀스 A는 Ck 방식으로 구성될 수 있습니다.
•그러면 B의 길이 = 2(n - k - 1)이고 B는 Cn-k-1 방식으로 구성될 수 있습니다.
•우리는 dp에 대한 공식을 봅니다: Cn = sum(Ck * Cn-k-1) for all k <
사용된 재료: