|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
Lah number
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(0 \le k \le n \le 10)] 범위에서[4] [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)] | |
2. 정의
라흐 수는 상승 계승 식을 하강 계승의 합으로 나타냈을 때 하강 계승에 곱해지는 계수로 정의된다.| [math(\displaystyle x^{\overline n} = \sum_{k=0}^n L(n,\,k) 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=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix})] |
라흐 수의 정의식에서 [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})] |
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(\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 {\color{red}\begin{pmatrix} a & b \end{pmatrix}},\,{\color{red}\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 {\color{red}\begin{pmatrix} c \end{pmatrix}},\,{\color{red}\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}},\,{\color{red}\begin{pmatrix} a & b \end{pmatrix}},\,{\begin{pmatrix} f & g & h \end{pmatrix}},\,{\color{red}\begin{pmatrix} c \end{pmatrix}} \\ &\vdots \\ &\vdots \end{aligned} \end{cases})]
와 같이, 분할 전의 경우의 수는 서로 다르지만 분할 후 중복되게 된다. 이 경우의 수는 분할 후의 순열 두 개를 결합시켜서 분할 전 상태를 만드는 경우의 수로 따져보면 되는데 [math((k+1))]개의 순열 집합에서 [math(2)]개를 골라내어 배열하는 경우의 수 [math({}_{k+1}{\rm 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) &= \frac{n-k}{k{\cdot}(k+1)} L(n,\,k) = \frac{(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 = \frac{\prod\limits_{i=1}^k(n-i)}{k!(k+1)!} L(n,\,1) \\ &= \frac{(n-1)!}{k!(k+1)!(n-k-1)!} L(n,\,1) \end{aligned})] |
| [math(\begin{aligned} L(n,\,k+1) &= \frac{(n-1)!n!}{k!(n-k-1)!(k+1)!} = \binom{n-1}k \frac{n!}{(k+1)!} = \binom n{k+1} \frac{(n-1)!}{k!} \\ L(n,\,k) &= \binom{n-1}{k-1} \frac{n!}{k!} = \binom nk \frac{(n+1)!}{(k+1)!}\,(1 \le k \le n) \\ \therefore L(n,\,k) &= \binom nk \frac{(n+1)!}{(k+1)!} = \binom{n+1}{k+1} \frac{n!}{k!}\,(0 \le k \le n) \end{aligned} )] |
참고로 스털링 수의 경우처럼 [math(n<k)]이면 이항계수가 정의되지 않으나 편의상 [math(L(n,\,k) = 0)]으로 정의한다.
4. 관련 문서
[1]
한국어판 위키피디아에는 ‘라 수’로 등재되어있는데
슬로베니아어에서 h는
무성 연구개 마찰음 /x/ 음가이기 때문에
바흐(Bach)의 ch처럼 ‘라흐’로 표기하는 게 맞다.
[2]
각 스털링 수의 정의를 이용해서 식을 세우다보면 튀어나온다. 후술
[3]
인지도가 낮아서인지 실례는 많지 않으나 부호 있는 라흐 수를 [math(L(n,\,k))]로 나타내고 부호 없는 라흐 수를 [math(|L(n,\,k)| = {\left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor})]로 표기하는 경우도 있다.
[4]
[math(n<k)]이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에 [math(0)]인 것으로 약속한다.
[5]
[math(L(n,\,k))] 표기에 대해선 정반대를 의미하는 경우도 있다.
프랑스어 버전 위키피디아의 라흐 수 페이지에서는
제1종 스털링 수처럼 부호 있는 라흐 수를 [math(L(n,\,k))]로, 부호 없는 라흐 수를[math(|L(n,\,k)| = {\left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor})]로 나타낸다.