스털링 수와 다항식 기저 변환

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 Stirling number \(S(n,k)\)에는 항상 제 2종 이라는 수식어가 붙는다. 교과서에서 보이지도 않는 제 1종 스털링 수가 뭐기에 더 쓸모가 많은 \(S(n,k)\)를 "제 2종"이라고 이름붙인 걸까?

 

Notations & Preliminaries

 

- \([n]\)은 양의 정수 집합 \(\{1,2,\cdots,n\}\)을 의미한다.

- Falling factorial \(\displaystyle (x)_{k} := x(x-1)\cdots(x-k+1) = k! \cdot \begin{pmatrix}x\\k\end{pmatrix}\).

- 제 2종 스털링 수의 조합적 의미를 깊게 다루지는 않는다.

- 서술을 엄밀하게 하지 않는다.

---

제 2종 스털링 수

가볍게 정의를 Recall해보자.

 

Definition 1. (제 2종 스털링 수) \(n\)개의 label이 붙은 물체를 \(k\)개의 구분되지 않는 집합으로 나누는 경우의 수를 제 2종 스털링 수라고 하고, \(S(n,k)\)로 표기한다.

 

즉, \([3]\)을 \(\{1,2\},\{3\}\)으로 분할한 것과 \(\{3\},\{1,2\}\)로 분할한 것은 서로 같은 경우이다.

 

Remark 2. \([n]\)에서 \([k]\)로 가는 전사함수(surjection)의 개수는 \(k! \cdot S(n,k)\)개이다.

 

Remark 3. (Recursion for \(S(n,k)\))

$$ S(n,k) = S(n-1,k-1) + kS(n-1, k) $$

 

pf) \(n\)이 들어가는 곳이 singleton인 경우와 그렇지 않은 경우로 나누면 된다. \(\blacksquare\)

 

Theorem 4. 

$$ x^{n} = \sum_{k=0}^{n} S(n, k) (x)_{k} $$

 

pf) \((x)_{k}\)의 정의에 따라 보이고자 하는 식을 아래와 같이 변형할 수 있다.

$$ x^{n} = \sum_{k=0}^{n} k! \cdot S(n,k) \begin{pmatrix} x\\k\end{pmatrix} $$

\(x\)에 임의의 자연수 \(m\)을 대입했을 때 등식이 성립한다면 둘은 다항식으로써 같다.

좌변은 \([m]\)에서 \([n]\)으로 가는 함수의 개수이고,

우변은 모든 \(I \subset [n]\)에 대해 \([m]\)에서 \(I\)로 가는 surjection의 개수를 센 것이다. bijective proof가 성립. \(\blacksquare\)

 

Proposition 4.1.

 

\(\mathfrak{B} := \{1,x,x^2,\cdots\}\)는 다항식 벡터공간 \(\mathcal{P}[x]\)의 (standard) basis이다. 그런데 \(\mathfrak{B}_{!} := \{1, x, x(x-1), \cdots, (x)_{k}, \cdots \}\)도 \(\mathcal{P}[x]\)의 basis를 이룬다는 것을 알 수 있다. 따라서, (infinite-dimensional?) matrix \(\left( S_{nk} := S(n,k)\right)\) 는 \(\mathfrak{B}_{!}\)를 \(\mathfrak{B}\)로 변환해주는 일종의 transition matrix가 된다.

 

 

---

제 1종 스털링 수

 

(meaningless) Proposition 5. \([n]\)의 permutation 중에서, 크기 \(i\)짜리 cycle이 \(a_i\)개인 permutation의 개수는 아래와 같다. (단, \(\sum_{i} ia_{i} = n\))

$$ \frac{n!}{a_{1}!a_{2}!\cdots a_{n}! \cdot 1^{a_1}2^{a_2}\cdots n^{a_n}}$$

 

pf) 임의의 permutation의 \(1\)번째, \(2\)번째, \(\cdots\) \(a_1\)번째, \(a_1 + 1 \cdots a_1 + 2\)번째, \(a_1 + 3 \cdots a_1 + 4\)번째, \(\cdots\) \(a_1 + 2a_2 + \cdots + ka_k + 1 \ldots a_1 + 2a_2 + \cdots + ka_k + k\)번째, \(\cdots\) 원소들을 하나의 cycle로 묶으면 조건을 만족하는 순열 하나를 만들 수 있다. 다만, 동일한 크기의 cycle을 다른 위치에서 묶는 경우 (\(a_{i}!\)), 한 cycle 내에서의 cyclic shift (\(i^{a_i}\))에 대한 중복 factor를 나눠주어야 원하는 답을 얻는다.

 

Definition 6. \([n]\)의 순열 중 cycle이 정확히 \(k\)개인 것의 개수를 \(c(n,k)\)로 정의한다.

 

즉, \(\sum_{i} a_{i} = k, \sum_{i} ia_i = n\)을 만족하는 모든 \(a\)에 대해서 Proposition 5의 식을 더한 것이다. 역시 제 2종 스털링 수와 같이 explicit한 표현이 없지만, 깔끔한 recursion을 갖는다.

 

Lemma 7. (Recursion of \(c(n,k)\))

$$ c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) $$

 

pf) 마찬가지로, \(n\)이 self loop를 이루는 경우를 따로 세어 주자. 그렇지 않은 경우는 \(1,\ldots,n-1\)중 하나를 골라 \(n\)과 '묶어' 주면 된다. \(\blacksquare\)

 

Definition 8. (제 1종 스털링 수)

$$ s(n,k) := (-1)^{n+k}c(n,k) $$

 

제 1종 스털링 수는 무려 '부호'가 있는 수다! 따라서 조합적인 의미를 부여하기 어렵다.

하지만 Proposition 4.1에서 \((S_{nk} = S(n,k))\)와 같은 행렬을 정의한 것을 보면, 왜 굳이 부호가 \((-1)^{n+k}\)의 형태로 붙어야만 했는지 짐작해볼 수 있다.

 

Theorem 9.  

$$ (x)_{n} = \sum_{k=0}^{n} s(n,k) x^{k} $$

즉, \((s_{nk} := s(n,k))\)는 \(S\)의 inverse matrix가 된다.

 

pf) By induction.

Base case는 자명하니 생략한다. 우변을 변형하면

$$ \sum_{k=0}^{n} (-1)^{n+k}c(n,k)x^{k} = (n-1) \sum_{k=0}^{n-1} (-1)^{n+k}c(n-1,k)x^{k} + \sum_{k=0}^{n-1}(-1)^{n+k+1}c(n-1,k)x^{k+1} \\ = -(n-1)\sum_{k=0}^{n-1} s(n-1,k)x^{k} + x\sum_{k=0}^{n-1}s(n-1,k)x^{k}=(x-n+1)(x)_{n-1} = (x)_{n} \blacksquare$$

 

Corollary 9.1. \(sS = Ss = I\).

 

---

Conclusion

 

따라서 두 가지 스털링 수는 \(\mathcal{P}[x]\)의 두 기저 간의 transition matrix 역할을 한다. \(s\)가 \(\mathfrak{B} \to \mathfrak{B}_{!}\)으로, \(S\)가 반대로 기저를 바꿔주는 행렬이니 정방향(?)을 1종, 역방향을 2종으로 칭한 것은 아닌가 짐작해본다. 사실 Wikipedia에서는 Theorem 4, 9로 스털링 수를 정의하고, 조합적 의미와 recursion을 유도하는 듯하다.