짧은 메모, 기록(카탈란 수, 팩토리얼 오버플로우)

간단한 메모, 기록용

카탈란 수

다음과 같은 점화식으로 표현할 수 있다.

$C_0 = 1$
$C_{n+1}= \frac{2(2n+1)}{(n+2)}C_n$
또는
$C_{n+1}= \sum\limits_{i=0}^n C_iC_{n-i}$

다음과 같이 일반항으로 나타낼 수 있다.

$C_n=_{2n}C_n-_{2n}C_{n-1} = \frac{1}{n+1}•_{2n}C_n$

*카탈란 수는 다음과 같은 여러 문제에서 답으로 나온다.

• 정(n+2)각형에 대각선을 그어 삼각형으로 분할하는 방법의 수
• (0, 0)에서 (n, n)까지 격자점을 따라 (1, 0) 또는 (0, 1)만큼 이동하는 경로 중 대각선 $x=y$ 좌상단으로 넘어가지 않는 경로의 개수
• (올바른) 괄호 나열 (뒤크 단어, Dyck word)) 시 경우의 수

팩토리얼

팩토리얼은 순열, 조합 등 수식에서 가끔 쓰이지만, 알고리즘 테스트에서 조심해서 사용해야 한다.
생각보다 빠르게 값이 커져서 오버플로우가 날 수 있기 때문.

(부호가 있는) Int32의 최댓값: 2,147,483,647
(부호가 있는) Int64의 최댓값: 9,223,372,036,854,775,807
20!: 2,432,902,008,176,640,000
21!: 51,090,942,171,709,440,000
21! 만 되어도 Int64의 최댓값 보다 커지기 때문.
그래서
Int64에서는 20!까지,
Int32에서는 12!까지 표현할 수 있다.