조합론 수 계산기 (카탈랑·스털링·벨·분할수)

괄호 n쌍을 올바르게 짝짓는 방법의 수입니다. n=3이면 ((())), (()()), (())(), ()(()), ()()()로 5가지입니다. 같은 수가 n+2각형을 대각선으로 삼각형 n개로 쪼개는 방법, 잎이 n+1개인 이진트리 모양, 격자에서 대각선을 넘지 않는 최단경로도 셉니다. 값은 C(2n,n)/(n+1)이며 나눗셈이 언제나 딱 떨어집니다.

세는 대상이 다릅니다. 제2종 S(n,k)는 서로 다른 원소 n개를 이름 없는 묶음 k개로 빈 묶음 없이 나누는 방법의 수이고, 제1종 c(n,k)는 원소 n개의 순열 가운데 사이클이 정확히 k개인 것의 개수입니다. 제2종 한 행을 모두 더하면 벨 수가 되고, 제1종 한 행을 모두 더하면 n!이 됩니다.

벨 수는 «서로 다른» 원소를 나누고 분할수는 «같은» 것을 나눕니다. 예를 들어 n=3일 때 벨 수는 5인데 {abc}, {ab}{c}, {ac}{b}, {bc}{a}, {a}{b}{c}를 세고, 분할수는 3으로 3, 2+1, 1+1+1만 셉니다. 원소에 이름이 있으면 벨 수, 개수만 있으면 분할수입니다.

이 수들이 배정밀도 실수의 정확한 정수 범위(2의 53제곱, 약 9,007조)를 금방 넘기 때문입니다. 카탈랑 수는 C(31)에서 이미 넘고 벨 수는 그보다도 빠릅니다. 실수로 계산하면 그때부터 끝자리가 조용히 틀리는데 값이 그럴듯해 보여 알아채기 어렵습니다.

같은 것으로 셉니다. 분할수는 순서를 따지지 않아 4를 4, 3+1, 2+2, 2+1+1, 1+1+1+1로 5가지로 셉니다. 순서를 따지는 것은 구성(composition)이라 부르며 2의 (n−1)제곱가지로 훨씬 많습니다.

빈 집합을 나누는 방법이 「아무것도 하지 않기」 하나 있기 때문입니다. 묶음이 0개인 나눔 하나가 조건을 만족하며, 이 값을 1로 두어야 점화식과 벨 수 B(0)=1이 일관되게 맞습니다. n이 0보다 클 때 S(n,0)은 0인데, 빈 묶음이 허용되지 않아 원소를 놓을 곳이 없기 때문입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.