라흐 수

 


1. 개요
2. 정의
3. 성질
3.1. 점화식
3.2. 일반항
4. 관련 문서

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] 한국어판 위키피디아에는 ‘라 수’로 등재되어있는데 슬로베니아어에서 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$$로 나타낸다.

분류