라흐 수

Lah number

1. 개요

---

라흐 수는 1954년에 슬로베니아의 수학자 이보 라흐(Ivo Lah)에 의해 정의된 수로서, $L(n,\,k)$로 표기된다. 표기가 표기이다보니 ‘라 수’로도 알려져 있다.[1]제1종 스털링 수, 제2종 스털링 수와 밀접한 관련이 있는 점으로부터 드물게 ‘제3종 스털링 수’라고도 불린다.[2] 제1종 스털링 수처럼, 부호 없는 라흐 수 $L(n,\,k)$와 부호 있는 라흐 수 $L'(n,\,k) = (-1)^{n-k} L(n,\,k)$로 나뉜다.[3] $0 \le k \le n \le 10$ 범위에서[4] $L(n,\,k)$ 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 $L'(n,\,k)$의 부호가 $(-)$임을 의미한다.

$n \Big\backslash k$	[math(0)]	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
[math(0)]	$1$	[math(0)]
$1$	[math(0)]	$1$	[math(0)]
$2$		$2$	$1$	[math(0)]
$3$		$6$	$6$	$1$	[math(0)]
$4$		$24$	$36$	$12$	$1$	[math(0)]
$5$		$120$	$240$	$120$	$20$	$1$	[math(0)]
$6$		$720$	$1800$	$1200$	$300$	$30$	$1$	[math(0)]
$7$		$5040$	$15120$	$12600$	$4200$	$630$	$42$	$1$	[math(0)]
$8$		$40320$	$141120$	$141120$	$58800$	$11760$	$1176$	$56$	$1$	[math(0)]
$9$		$362880$	$1451520$	$1693440$	$846720$	$211680$	$28224$	$2016$	$72$	$1$	[math(0)]
$10$		$3628800$	$16329600$	$21772800$	$12700800$	$3810240$	$635040$	$60480$	$3240$	$90$	$1$

2. 정의

---

라흐 수는 상승 계승 식을 하강 계승의 합으로 나타냈을 때 하강 계승에 곱해지는 계수로 정의된다.

$\displaystyle x^{\overline n} = \sum_{k=0}^n L(n,\,k) x^{\underline k}$

$k=1$부터 더하는 경우가 일반적인데, $x^{\overline 0} = x^{\underline 0} = 1$이고 $L(0,\,k) = \delta_{0,\,k}$ ($\delta_{0,\,k}$는 크로네커 델타)이므로 $n=0$일 때도 문제없이 위 식이 성립한다. $n \ge 1$이면 양변에 상수항이 없으므로 당연히 $L(n,\,0) = \delta_{n,\,0}$도 만족한다.
부호 없는 제1종 스털링 수 $\begin{bmatrix} n \\ r \end{bmatrix}$, 제2종 스털링 수 $\begin{Bmatrix} r \\ k \end{Bmatrix}$가 각각 $\displaystyle x^{\overline n} = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} x^r$, $\displaystyle x^r = \sum_{k=0}^r \begin{Bmatrix} r \\ k \end{Bmatrix} x^{\underline k}$를 만족하므로 위 식에 대입하면

$\displaystyle \begin{aligned} x^{\overline n} &= \sum_{k=0}^n L(n,\,k) x^{\underline k} = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} x^r = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \sum_{k=0}^r \begin{Bmatrix} r \\ k \end{Bmatrix} x^{\underline k} \\ &= \sum_{k=0}^n \left( \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \right) x^{\underline k} \end{aligned}$

즉 $\displaystyle L(n,\,k) = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix}$인데 $r<k$이면 $\begin{Bmatrix} r \\ k \end{Bmatrix} = 0$이므로 다음과 같이 간략하게 나타낼 수 있다. 라흐 수가 ‘제3종 스털링 수’라고도 불리는 이유를 극명하게 보여주는 성질이기도 하다.

$\displaystyle L(n,\,k) = \sum_{r=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix}$

스털링 수와 마찬가지로, 집합론을 이용해서 정의할 수도 있다. 라흐 수는 $n$개의 원소를 구분되지 않는 $k$개의 순열로 분할하는 경우의 수로 정의된다. 역시 각 정의에 입각해서 점화식을 써보면 똑같은 꼴이 유도된다.
라흐 수의 정의식에서 $x$에 $-x$를 대입하면 $(-x)^{\overline n} = (-1)^n x^{\underline n}$, $(-x)^{\underline k} = (-1)^k x^{\overline k}$이므로

$\displaystyle (-x)^{\overline n} = (-1)^n x^{\underline n} = \sum_{k=0}^n L(n,\,k) (-x)^{\underline k} = \sum_{k=0}^n L(n,\,k) (-1)^k x^{\overline k} \\ \begin{aligned} x^{\underline n} &= \sum_{k=0}^n (-1)^{k-n} L(n,\,k) x^{\overline k} \\ \therefore x^{\underline n} &= \sum_{k=0}^n (-1)^{n-k} L(n,\,k) x^{\overline k} \end{aligned}$

즉, 상승 계승과 하강 계승을 서로 맞바꿔주면 라흐 수에 $(-1)^{n-k}$ 이 곱해지는 꼴이 되는데 $(-1)^{n-k} L(n,\,k)$를 '''부호 있는(signed) 라흐 수'''라고도 하며 $L'(n,\,k)$등으로 나타낸다.[5]

3. 성질

---

3.1. 점화식

---

• || $L(n+1,\,k) = L(n,\,k-1) +(n+k) L(n,\,k)$ ||

스털링 수를 이용하여 나타낸 표기를 이용하면 간단하게 증명이 가능하다. 부호 없는 제1종 스털링 수, 제2종 스털링 수의 점화식이 각각 $\begin{bmatrix} n+1 \\ r \end{bmatrix} = \begin{bmatrix} n \\ r-1 \end{bmatrix} + n \begin{bmatrix} n \\ r \end{bmatrix}$, $\begin{Bmatrix} r \\ k \end{Bmatrix} = \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} r-1 \\ k \end{Bmatrix}$로 주어지므로 대입하면

$\displaystyle \begin{aligned} L(n+1,\,k) &= \sum_{r=k}^{n+1} \begin{bmatrix} n+1 \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} = \sum_{r=k}^{n+1} \left( \begin{bmatrix} n \\ r-1 \end{bmatrix} + n \begin{bmatrix} n \\ r \end{bmatrix} \right) \begin{Bmatrix} r \\ k \end{Bmatrix} = \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} + n \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \\ &= \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \left( \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} r-1 \\ k \end{Bmatrix} \right) + n \sum_{r=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \\ &= \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \sum_{r=k+1}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r-1 \\ k \end{Bmatrix} + n L(n,\,k) \\ &= L(n,\,k-1) + k L(n,\,k) + n L(n,\,k) \\ &= L(n,\,k-1) + (n+k) L(n,\,k) \end{aligned}$

집합론을 이용해서도 증명할 수 있다. $(n+1)$번째 원소를 추가하여 $k$개의 순열로 만들 때 크게 두 가지 경우로 나눌 수 있다. 첫 번째는 $(n+1)$번째 원소를 길이가 $1$인 순열로 추가하는 경우, 두 번째는 기존 $n$개 원소를 $k$개 순열로 분할한 것에 $(n+1)$번째 원소를 끼워넣는 경우이다. 전자는 $n$개 원소를 $(k-1)$개 순열로 분할한 경우의 수 $L(n,\,k-1)$가 그대로 쓰인다. 후자는 각 순열 집합에서 원소의 맨 앞, 사이사이, 맨 뒤를 모두 세어준 값을 $L(n,\,k)$에 곱하면 되는데, $k$개의 순열 집합을 일렬로 쭉 늘어놓고 세어보면 총 원소의 맨 앞, 사이사이, 맨 뒤의 수 $(n+1)$와 각 분할을 나누는 경계의 수 $(k-1)$를 한 번 더 세어준 값 $(n+1)+(k-1)=n+k$와 같다는 것을 알 수 있다. 정리하면 위 식이 얻어진다.

• || $L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k)$ ||

집합론을 이용해서 유도할 수 있다. 먼저 ‘공집합 없이 구분되지 않는 부분 집합 $k$개로 분할한다’를 $(k-1)$개의 칸막이를 끼워넣는 조작’으로 바꿔 해석하면, $k \to k+1$이란 곧 칸막이를 하나 늘리는 것으로 이해할 수 있다. $L(n,\,k)$에서 각 순열 집합을 일렬로 쭉 늘어놓고 공집합이 없이 새 칸막이를 끼워넣을 수 있는 자리의 수를 따져보면, 모든 원소의 사이인 $(n-1)$에서 칸막이의 개수 $(k-1)$개를 뺀 $(n-k)$이므로 $(k+1)$개로 분할한 경우의 수는 $(n-k) L(n,\,k)$가 된다. 그런데 다음과 같이 새 칸막이를 끼움으로써 중복이 생기는 경우가 있다. 예를 들어 3개 → 4개로 순열 분할을 늘릴 때

$\begin{cases} \begin{aligned} \begin{pmatrix} a & b & c \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix} &\to \begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix} \\ \begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b & f & g & h \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix} &\to \begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix}, \begin{pmatrix} f & g & h \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix} \\ \begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} f & g & h & c \end{pmatrix} &\to \begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix}, \begin{pmatrix} c \end{pmatrix} \\ &\vdots \\ &\vdots \end{aligned} \end{cases}$

와 같이, 분할 전의 경우의 수는 서로 다르지만 분할 후 중복되게 된다. 이 경우의 수는 분할 후의 순열 두 개를 결합시켜서 분할 전 상태를 만드는 경우의 수로 따져보면 되는데 $(k+1)$개의 순열 집합에서 $2$개를 골라내어 배열하는 경우의 수 ${}_{k+1}\mathrm P_2 = k(k+1)$와 같으므로 이 값으로 나누어주면 된다. 따라서 $L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k)$

3.2. 일반항

---

• || $L(n,\,k) = \dbinom nk \dfrac{(n+1)!}{(k+1)!} = \dbinom{n+1}{k+1} \dfrac{n!}{k!}$ ||

점화식 항목의 두 번째 식을 이용하면 된다.

$\begin{aligned} L(n,\,k+1) &= \dfrac{n-k}{k \cdot (k+1)} L(n,\,k) = \dfrac{(n-k)(n-k+1) }{ k(k-1) \cdot (k+1) k} L(n,\,k-1) \\ &= \frac{(n-k)(n-k+1)(n-k+2) }{ k(k-1)(k-2) \cdot (k+1) k(k-1)} L(n,\,k-2) = \cdots\cdots = \dfrac{\displaystyle \prod_{i=1}^k(n-i)}{ k!(k+1)! } L(n,\,1) \\ &= \dfrac{(n-1)!}{k!(k+1)!(n-k-1)!} L(n,\,1) \end{aligned}$

$L(n,\,1)$은 $n$개의 원소를 $1$개의 순열로 나타내는 경우이므로 $L(n,\,1) = n!$이다. 따라서

$\begin{aligned} L(n,\,k+1) &= \dfrac{(n-1)!n!}{k!(n-k-1)!(k+1)!} = \dbinom{n-1}k \dfrac{n!}{(k+1)!} = \dbinom n{k+1} \dfrac{(n-1)!}{k!} \\ L(n,\,k) &= \dbinom{n-1}{k-1} \dfrac{n!}{k!} = \dbinom nk \dfrac{(n+1)!}{(k+1)!}\,(1 \le k \le n) \\ \therefore L(n,\,k) &= \dbinom nk \dfrac{(n+1)!}{(k+1)!} = \dbinom{n+1}{k+1} \dfrac{n!}{k!}\,(0 \le k \le n) \end{aligned}$

참고로 스털링 수의 경우처럼 $$n

4. 관련 문서

---

• 제1종 스털링 수
• 제2종 스털링 수
• 순열

[1] 한국어판 위키피디아에는 ‘라 수’로 등재되어있는데 슬로베니아어에서 h는 무성 연구개 마찰음 /x/ 음가이기 때문에 바흐(Bach)의 ch처럼 ‘라흐’로 표기하는 게 맞는다.

[2] 각 스털링 수의 정의를 이용해서 식을 세우다보면 튀어나온다. 후술

[3] 인지도가 낮아서인지 실례는 많지 않으나 부호 있는 라흐 수를 $L(n,\,k)$로 나타내고 부호 없는 라흐 수를 $|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor$로 표기하는 경우도 있다.

[4] $n<k$이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.

[5] $L(n,\,k)$ 표기에 대해선 정반대를 의미하는 경우도 있다. 프랑스어 버전 위키피디아의 라흐 수 페이지에서는 제1종 스털링 수처럼 부호 있는 라흐 수를 $L(n,\,k)$로, 부호 없는 라흐 수를$|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor$로 나타낸다.