문제: https://gall.dcinside.com/mgallery/board/view/?id=github&no=19247&search_head=50&page=1


이 문제는 '제 2종 스털링 수'를 가지고 조금 비틀어서 만들어 본 문제임.


제 2종 스털링 수는 'n개의 원소를 가진 집합을 k개의 공집합이 아닌 부분집합으로 나누는 경우의 수'로 정의되고, S(n, k)로 나타냄.


중고딩 때 경시수학 좀 해봤던 사람(나)이면 한 번쯤 봤을텐데, 보통 올림피아드 같은데서 'n명의 학생을 k개의 소그룹으로 나누는 경우'나 'n개의 서로 다른 공을 k개의 서로 같은 상자에 각 상자가 비어있지 않도록 넣는 경우' 정도로 변형시켜서 많이 나옴.


다들 처음 생각으로는 '전부 더해서 n이 되는 자연수 i_1 <= i_2 <= ... <= i_k 를 구한 다음에 각 i마다 조합을 돌리면 될 것 같다' 라고도 생각하겠지만... 풀다보면 이걸론 답이 안 나오겠다는 걸 느낄 거임.

맞음. 이걸로는 답이 안 나옴. 전부 더해서 n이 되는 k개의 자연수들의 모든 경우를 구하는 건 '자연수 분할' P(n, k)라고 해서 S(n, k)랑 똑같이 존나게 구하기 어려운 함수임.


그래서 구할 수 있는 방법은 재귀밖에 없음. 올림피아드에 나오는 문제들도 자연수 분할로는 못 풀게 숫자를 S(8, 4) 정도로 적당히 크게 만듬. 역시 내 풀이도 재귀를 쓸거임.



일단 {1, ..., n-1}을 부분집합들로 나누는 방법을 이미 알고 있다고 가정을 해보자. 그리고서 전체 집합 {1, ..., n-1}에 n을 추가한다고 생각을 해 보자.


그러면 이때 가능한 경우는


1. {1, ..., n-1}을 k개의 부분집합으로 미리 나누고 그 부분집합들 중 하나에 n이 들어감

2. {1, ..., n-1}을 k-1개의 부분집합으로 미리 나누고 n은 n 하나만 있는 새로운 부분집합에 들어감


이 두 가지 경우밖에 없을 거임


첫 번째 경우에는 미리 만들어진 k개의 부분집합들에 n이 들어갈 때마다 새로운 하나의 경우가 생기니까 새로 만들어지는 경우는 k * S(n-1, k)가 됨

두 번째 경우에 새로 만들어지는 경우는 S(n-1, k-1)이 됨


그러므로 S(n, k) = k * S(n-1, k) + S(n-1, k-1)이라는 점화식이 성립함


여기에다 S(n, 1) = 1, S(n, n) = 1 이라는 성질만 추가하면 모든 n, k에 대해 S(n, k)를 구할 수 있음. 증명 끝



S(n, k)를 구하는 방법은 대충 이런 식인데 이 아이디어만 가지고 그대로 코드로 옮기기만 하면 모든 경우의 수도 별로 어렵지 않게 구현할 수 있음. 아래는 러스트로 푼 거임.



viewimage.php?id=2ab4c42ef0d0&no=24b0d769e1d32ca73cec80fa11d028312e15c0eaac8534358234c142d2786488543b81b9ef1656b2efb5855767e59134b75bd59339b9f3b300900011f20918


더 자세히 보고 싶으면 여기: https://gist.github.com/adenosie/bd786bdd8de3f4ad622be1716b4cebcc


모든 원소가 원소 하나당 부분집합 하나에 속하게 되니까 인덱스(0..n): 부분집합 번호(0..k) 같은 식으로도 나타낼 수 있지 않을까 같은 생각도 들었지만 그냥 귀찮아서 접었음. 해보고 싶은 사람은 해 보셈