분류
1. 개요
라흐 수는 1954년에 슬로베니아의 수학자 이보 라흐(Ivo Lah)에 의해 정의된 수로서, [math(L(n,,k))]로 표기된다. 표기가 표기이다보니 ‘라 수’로도 알려져 있다.[1]제1종 스털링 수, 제2종 스털링 수와 밀접한 관련이 있는 점으로부터 드물게 ‘제3종 스털링 수’라고도 불린다.[2] 제1종 스털링 수처럼, 부호 없는 라흐 수 [math(L(n,,k))]와 부호 있는 라흐 수 [math(L'(n,,k) = (-1)^{n-k} L(n,,k))]로 나뉜다.[3]로 나타내고 부호 없는 라흐 수를 [math(|L(n,,k)| = leftlfloor begin{matrix} n \ k end{matrix} rightrfloor)]로 표기하는 경우도 있다.] [math(0 le k le n le 10)] 범위에서[4]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.] [math(L(n,,k))] 값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은 [math(L'(n,,k))]의 부호가 [math((-))]임을 의미한다.
[math(n Bigbackslash 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)]
| |
2. 정의
[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})]를 만족하므로 위 식에 대입하면
부호 없는 제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] 표기에 대해선 정반대를 의미하는 경우도 있다. 프랑스어 버전 위키피디아의 라흐 수 페이지에서는 제1종 스털링 수처럼 부호 있는 라흐 수를 [math(L(n,,k))]로, 부호 없는 라흐 수를[math(|L(n,,k)| = leftlfloor begin{matrix} n \ k end{matrix} rightrfloor)]로 나타낸다.]
3. 성질
3.1. 점화식
- [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))]
3.2. 일반항
- [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) = cdotscdots = 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<k)]이면 이항계수가 정의되지 않으나 편의상 [math(L(n,,k) = 0)]으로 정의한다.