최근 수정 시각 : 2024-03-10 01:33:10

라흐 수

이산수학
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색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 정의3. 성질
3.1. 점화식3.2. 일반항
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})]
[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]

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(L(n,\,1))]은 [math(n)]개의 원소를 [math(1)]개의 순열로 나타내는 경우이므로 [math(L(n,\,1) = n!)]이다. 따라서
[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})]로 나타낸다.

분류