스털링 수

스털링 수는 위키 피디아 에서 아래와 같이 정의 되어 있다.

조합론에서 스털링 수(Stirling, Stirling number)는 조합론에서 자주 등장하는 두종의 정수열이다.

제 1종 스털링 수와 2종 스털링 수가 존재하는데,
부호 없는 제 1종 스털링 수는 n개의 원소의 순열 가운데, 정확히 m개의 순환(cycle)들로 구성된 순열들의 수이다. (고정점은 길이 1의 순환으로 간주)

부호 없는 제 1종 스털링 수를 재귀적으로 나타내면 다음과 같다.

위의 재귀적 표현의 의미는 다음과 같다.

n개의 점을 m개의 순환사이클로 구성된 순열로 나타내는 것은 1개의 점을 독립 사이클로 만들어 두는 것과 나머지 n-1개의 특정 점에 사이클을 포함되게 하는 것과 같다.

2종 스털링 수는 n개의 원소의 집합을 m개의 공집합이 아닌 부분집합들로 나누는 방법의 수이다.

제 2종 스털링 수를 재귀적으로 나타내면 다음과 같다.

위의 재귀적 표현의 의미는 다음과 같다.

n개의 점을 m개의 공집합 없는 부분집합으로 표현하는 것은 n-1개의 점에서 m-1개의 부분집합에 1개짜리 부분집합을 만드는 것과 n-1개로 m개의 부분집합을 만드는 m개 중에 하나에 포함되게 하는 것과 같다.

이는 알고리즘에서 활용될 (특히 DP) 수 있으니 숙지하는 것이 좋다.