제1종 스털링 수

이 문서는 토막글입니다.

이 문서는 토막글로 분류되는 800바이트 이하의 문서입니다. 토막글을 채우는 것은 기여자의 따뜻한 손길입니다. 이 틀을 적용할 시 틀의 매개변수로 분류:토막글의 하위 분류 중 적절한 분류를 지정해 주시기 바랍니다.

Stirling numbers of the first kind

1 개요

원소의 개수가 n인 집합을 구분되지 않는 k개의 원순열로 분할하는 방법의 수이다. [math] s \left(n,k\right) [/math] 로 나타낸다.
참고로 제2종 스털링 수의 기호는 s를 대문자로 쓴 것이다.

예를 들어, 어느 평범한 원탁의 기사들이 구분되지 않는 원탁들에 모여서 밥을 먹는다고 하자.
이때 기사들이 n명, 원탁이 k개 일 때 앉는 방법의 수이다.

[math] s\left(n,k\right)=s\left(n-1,k-1\right)+\left(n-1\right)s\left(n-1,k\right) [/math]

위의 원탁의 기사를 예시로 들면 어느 기사 1명이 있다고 하자. 이 1명이 혼자 앉을지, 아니면 다른 기사가 있는 방에 앉을지 선택 하게 하자. 만약 1명이 혼자 앉으면 원탁은 구분되지 않으므로 그냥 [math]s\left(n-1,k-1\right)[/math]다. 하지만 다른 사람이 있는 원탁에 앉는다고 하면 우선 1번을 넘어간뒤 2번을 고르게 하자. 이런 식으로 우선 모든 사람이 방을 고르게 한 뒤 1번에게 남은 식탁중 1개를 고르라고 하자. 그러면 [math] s\left(n-1,k\right)\times \left(n-1\right)[/math]이다.
따라서 [math] s\left(n,k\right)=s\left(n-1,k-1\right)+\left(n-1\right)s\left(n-1,k\right) [/math]