Lah number
라흐 수는 1954년에
슬로베니아의 수학자
이보 라흐(Ivo Lah)에 의해 정의된 수로서, [math(L(n,\,k))]로 표기된다. 표기가 표기이다보니 ‘라 수’로도 알려져 있다.
[1] 한국어판 위키피디아에는 ‘라 수’로 등재되어있는데 슬로베니아어에서 h는 무성 연구개 마찰음 /x/ 음가이기 때문에 바흐(Bach)의 ch처럼 ‘라흐’로 표기하는 게 맞는다.
,
제2종 스털링 수와 밀접한 관련이 있는 점으로부터 드물게 ‘제3종 스털링 수’라고도 불린다.
[2] 각 스털링 수의 정의를 이용해서 식을 세우다보면 튀어나온다. 후술
제1종 스털링 수처럼, 부호 없는 라흐 수 [math(L(n,\,k))]와 부호 있는 라흐 수 [math(L'(n,\,k) = (-1)^{n-k} L(n,\,k))]로 나뉜다.
[3] 인지도가 낮아서인지 실례는 많지 않으나 부호 있는 라흐 수를 [math(L(n,\,k))]로 나타내고 부호 없는 라흐 수를 [math(|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor)]로 표기하는 경우도 있다.
[math(0 \le k \le n \le 10)] 범위에서
[4] [math(n<k)]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.
[math(L(n,\,k))] 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 [math(L'(n,\,k))]의 부호가 [math((-))]임을 의미한다.
[math(n \Big\backslash k )]
| [math(0)]
| [math(1)]
| [math(2)]
| [math(3)]
| [math(4)]
| [math(5)]
| [math(6)]
| [math(7)]
| [math(8)]
| [math(9)]
| [math(10)]
|
[math(0)]
| [math(1)]
| [math(0)]
|
[math(1)]
| [math(0)]
| [math(1)]
| [math(0)]
|
[math(2)]
| [math(2)]
| [math(1)]
| [math(0)]
|
[math(3)]
| [math(6)]
| [math(6)]
| [math(1)]
| [math(0)]
|
[math(4)]
| [math(24)]
| [math(36)]
| [math(12)]
| [math(1)]
| [math(0)]
|
[math(5)]
| [math(120)]
| [math(240)]
| [math(120)]
| [math(20)]
| [math(1)]
| [math(0)]
|
[math(6)]
| [math(720)]
| [math(1800)]
| [math(1200)]
| [math(300)]
| [math(30)]
| [math(1)]
| [math(0)]
|
[math(7)]
| [math(5040)]
| [math(15120)]
| [math(12600)]
| [math(4200)]
| [math(630)]
| [math(42)]
| [math(1)]
| [math(0)]
|
[math(8)]
| [math(40320)]
| [math(141120)]
| [math(141120)]
| [math(58800)]
| [math(11760)]
| [math(1176)]
| [math(56)]
| [math(1)]
| [math(0)]
|
[math(9)]
| [math(362880)]
| [math(1451520)]
| [math(1693440)]
| [math(846720)]
| [math(211680)]
| [math(28224)]
| [math(2016)]
| [math(72)]
| [math(1)]
| [math(0)]
|
[math(10)]
| [math(3628800)]
| [math(16329600)]
| [math(21772800)]
| [math(12700800)]
| [math(3810240)]
| [math(635040)]
| [math(60480)]
| [math(3240)]
| [math(90)]
| [math(1)]
|
라흐 수는
상승 계승 식을
하강 계승의 합으로 나타냈을 때 하강 계승에 곱해지는 계수로 정의된다.
[math(\displaystyle x^{\overline n} = \sum_{k=0}^n L(n,\,k) x^{\underline k})]
|
[math(k=1)]부터 더하는 경우가 일반적인데, [math(x^{\overline 0} = x^{\underline 0} = 1)]이고 [math(L(0,\,k) = \delta_{0,\,k})] ([math(\delta_{0,\,k})]는
크로네커 델타)이므로 [math(n=0)]일 때도 문제없이 위 식이 성립한다. [math(n \ge 1)]이면 양변에 상수항이 없으므로 당연히 [math(L(n,\,0) = \delta_{n,\,0})]도 만족한다.
부호 없는
제1종 스털링 수 [math(\begin{bmatrix} n \\ r \end{bmatrix})],
제2종 스털링 수 [math(\begin{Bmatrix} r \\ k \end{Bmatrix})]가 각각 [math(\displaystyle x^{\overline n} = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} x^r)], [math(\displaystyle x^r = \sum_{k=0}^r \begin{Bmatrix} r \\ k \end{Bmatrix} x^{\underline k})]를 만족하므로 위 식에 대입하면
[math(\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})]
|
즉 [math(\displaystyle L(n,\,k) = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix})]인데 [math(r<k)]이면 [math(\begin{Bmatrix} r \\ k \end{Bmatrix} = 0)]이므로 다음과 같이 간략하게 나타낼 수 있다. 라흐 수가 ‘제3종 스털링 수’라고도 불리는 이유를 극명하게 보여주는 성질이기도 하다.
[math(\displaystyle L(n,\,k) = \sum_{r=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix})]
|
스털링 수와 마찬가지로, 집합론을 이용해서 정의할 수도 있다. 라흐 수는 [math(n)]개의 원소를 구분되지 않는 [math(k)]개의
순열로 분할하는 경우의 수로 정의된다. 역시 각 정의에 입각해서 점화식을 써보면 똑같은 꼴이 유도된다.
라흐 수의 정의식에서 [math(x)]에 [math(-x)]를 대입하면 [math((-x)^{\overline n} = (-1)^n x^{\underline n})], [math((-x)^{\underline k} = (-1)^k x^{\overline k})]이므로
[math(\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})]
|
즉, 상승 계승과 하강 계승을 서로 맞바꿔주면 라흐 수에 [math((-1)^{n-k} )] 이 곱해지는 꼴이 되는데 [math((-1)^{n-k} L(n,\,k))]를
부호 있는(signed) 라흐 수라고도 하며 [math(L'(n,\,k))]등으로 나타낸다.
[5] [math(L(n,\,k))] 표기에 대해선 정반대를 의미하는 경우도 있다. 프랑스어 버전 위키피디아의 라흐 수 페이지에서는 제1종 스털링 수처럼 부호 있는 라흐 수를 [math(L(n,\,k))]로, 부호 없는 라흐 수를[math(|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor)]로 나타낸다.
- || [math(L(n+1,\,k) = L(n,\,k-1) +(n+k) L(n,\,k))] ||
스털링 수를 이용하여 나타낸 표기를 이용하면 간단하게 증명이 가능하다. 부호 없는
제1종 스털링 수,
제2종 스털링 수의 점화식이 각각 [math(\begin{bmatrix} n+1 \\ r \end{bmatrix} = \begin{bmatrix} n \\ r-1 \end{bmatrix} + n \begin{bmatrix} n \\ r \end{bmatrix})], [math(\begin{Bmatrix} r \\ k \end{Bmatrix} = \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} r-1 \\ k \end{Bmatrix})]로 주어지므로 대입하면
[math(\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})]
|
집합론을 이용해서도 증명할 수 있다. [math((n+1))]번째 원소를 추가하여 [math(k)]개의 순열로 만들 때 크게 두 가지 경우로 나눌 수 있다. 첫 번째는 [math((n+1))]번째 원소를 길이가 [math(1)]인 순열로 추가하는 경우, 두 번째는 기존 [math(n)]개 원소를 [math(k)]개 순열로 분할한 것에 [math((n+1))]번째 원소를 끼워넣는 경우이다. 전자는 [math(n)]개 원소를 [math((k-1))]개 순열로 분할한 경우의 수 [math(L(n,\,k-1))]가 그대로 쓰인다. 후자는 각 순열 집합에서 원소의 맨 앞, 사이사이, 맨 뒤를 모두 세어준 값을 [math(L(n,\,k))]에 곱하면 되는데, [math(k)]개의 순열 집합을 일렬로 쭉 늘어놓고 세어보면 총 원소의 맨 앞, 사이사이, 맨 뒤의 수 [math((n+1))]와 각 분할을 나누는 경계의 수 [math((k-1))]를 한 번 더 세어준 값 [math((n+1)+(k-1)=n+k)]와 같다는 것을 알 수 있다. 정리하면 위 식이 얻어진다.
- || [math(L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k))] ||
집합론을 이용해서 유도할 수 있다. 먼저 ‘공집합 없이 구분되지 않는 부분 집합 [math(k)]개로 분할한다’를 [math((k-1))]개의 칸막이를 끼워넣는 조작’으로 바꿔 해석하면, [math(k \to k+1)]이란 곧 칸막이를 하나 늘리는 것으로 이해할 수 있다. [math(L(n,\,k))]에서 각 순열 집합을 일렬로 쭉 늘어놓고 공집합이 없이 새 칸막이를 끼워넣을 수 있는 자리의 수를 따져보면, 모든 원소의 사이인 [math((n-1))]에서 칸막이의 개수 [math((k-1))]개를 뺀 [math((n-k))]이므로 [math((k+1))]개로 분할한 경우의 수는 [math((n-k) L(n,\,k))]가 된다. 그런데 다음과 같이 새 칸막이를 끼움으로써 중복이 생기는 경우가 있다. 예를 들어 3개 → 4개로 순열 분할을 늘릴 때
[math(\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})]
|
와 같이, 분할 전의 경우의 수는 서로 다르지만 분할 후 중복되게 된다. 이 경우의 수는 분할 후의 순열 두 개를 결합시켜서 분할 전 상태를 만드는 경우의 수로 따져보면 되는데 [math((k+1))]개의 순열 집합에서 [math(2)]개를 골라내어 배열하는 경우의 수 [math({}_{k+1}\mathrm P_2 = k(k+1))]와 같으므로 이 값으로 나누어주면 된다. 따라서 [math(L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k))]
- || [math(L(n,\,k) = \dbinom nk \dfrac{(n+1)!}{(k+1)!} = \dbinom{n+1}{k+1} \dfrac{n!}{k!})] ||
점화식 항목의 두 번째 식을 이용하면 된다.
[math(\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} )]
|
[math(L(n,\,1))]은 [math(n)]개의 원소를 [math(1)]개의 순열로 나타내는 경우이므로 [math(L(n,\,1) = n!)]이다. 따라서
[math(\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} )]
|
참고로 스털링 수의 경우처럼 [math(n
이 문서의 내용 중 전체 또는 일부는 2023-11-25 03:53:04에 나무위키
라흐 수 문서에서 가져왔습니다.
이 문서의 내용 중 전체 또는 일부는 2023-11-25 03:53:04에 나무위키 라흐 수 문서에서 가져왔습니다.