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

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 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을 유도하는 듯하다.