제 1종, 2종 스털링 수

제 1종 스털링 수

모든 노드의 outdegree가 1이고 indegree도 1인 노드가 n개인 그래프에서 k개의 사이클이 생기는 경우의 수를 의미한다.

이 그래프는 일대일 대응이므로 간선은 전단사 함수라고 할 수 있다.

s(n,k) = s(n−1, k−1) + (n−1)s(n−1, k)

어떤 한 노드를 self loop라고 했을 때 n-1개에서 k-1개의 사이클이 생기는 경우의 수는 s(n-1, k-1) 이다.

어떤 한 노드를 제외하고 n-1개에서 k개의 사이클이 생기는 경우의 수는 s(n-1, k) 이고

어떤 한 노드를 이제 이미 만들어진 k개의 사이클로 넣어야 한다.

이 경우 어떤 한 노드의 친구를 정해고 그 친구와 함께 사이클에 들어간다고 하면

친구를 만드는 경우의 수는 n-1개이고 따라서 (n-1)s(n-1, k) 개 이다.

 

제 2종 스털링 수

n개의 원소를 갖는 집합에서 k개의 부분 집합으로 나누는 경우의 수

S(n, k) = S(n−1, k−1) + kS(n−1, k)

한 원소를 혼자 부분집합을 만들고 나머지 n-1 개에서 k-1개의 부분집합으로 나누는 경우의 수 S(n-1, k-1)

한 원소를 제외한 나머지 n-1 개에서 k개의 집합을 만드는 경우의 수 S(n-1, k)

한 원소가 이미 만들어진 k개의 집합중에서 선택하는 경우의 수 k

따라서 kS(n-1, k) 이다.