수학(mathematics)에서, 라 숫자는, 이보 라(Ivo Lah)에 의해 1954년에 발견되었으며, 떨어지는 팩토리얼(falling factorial)의 관점에서 올라가는 팩토리얼(rising factorial)을 표현하는 계수(coefficient)입니다. 그것들은 역시 \(e^{1 / x}\)의 \(n\)번째 도함수의 계수입니다.
부호없는 라 숫자(Unsigned Lah numbers)는 조합론(combinatorics)에서 흥미로운 의미를 가집니다: 그것들은 n 원소의 집합(set)이 k 비-빈 선형적으로 순서화된 부분집합(subset)으로 분할(partition)될 수 있는 방법의 숫자를 셉니다. 라 숫자는 스털링 숫자(Stirling number)와 관련이 있습니다.
부호없는 라 숫자 (OEIS에서 수열 A105278):
\(\quad\displaystyle L(n,k) = {n-1 \choose k-1} \frac{n!}{k!}.\)
부호화된 라 숫자 (OEIS에서 수열 A008297):
\(\quad\displaystyle L'(n,k) = (-1)^n {n-1 \choose k-1} \frac{n!}{k!}.\)
L(n, 1)은 항상 n!입니다; 위의 해석에서, {1, 2, 3}에서 1 집합으로의 유일한 분할은 6 방법에서 순서화된 그것의 집합을 가질 수 있습니다:
{(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)} 또는 {(3, 2, 1)}
L(3, 2)는 둘의 순서화된 부분을 갖는 6 분할에 해당합니다:
{(1), (2, 3)}, {(1), (3, 2)}, {(2), (1, 3)}, {(2), (3, 1)}, {(3), (1, 2)} 또는 {(3), (2, 1)}
L(n, n)은 항상 1인데 왜냐하면, 예를 들어, {1, 2, 3}을 3 비-빈 부분집합으로 분할하는 것은 길이 1의 부분집합을 초래합니다:
{(1), (2), (3)}
스털링 숫자(Stirling numbers)에 대해 카르마타(Karamata)–커누스(Knuth) 표기법을 적용하여, 라 숫자에 대해 다음 대안적인 표기법을 사용하는 것이 제안되어 왔습니다"
\(\quad\displaystyle L(n,k) = \sum_{j=0}^n \left[\begin{matrix} n \\ j \end{matrix}\right] \left\{\begin{matrix} j \\ k \end{matrix}\right\}\)
Rising and falling factorials
\(x^{(n)}\)가 올라가는 팩토리얼 \(x(x+1)(x+2) \cdots (x+n-1)\)를 나타내는 것으로 놓고 \((x)_n\)가 떨어지는 팩토리얼 \(x(x-1)(x-2) \cdots (x-n+1)\)을 나타내는 것으로 놓습니다.
그런-다음 \(x^{(n)} = \sum_{k=1}^n L(n,k) (x)_k\)이고 \((x)_n = \sum_{k=1}^n (-1)^{n-k} L(n,k)x^{(k)}\)입니다.
예를 들어,
\(\quad\displaystyle x(x+1)(x+2) = {\color{red}6}x + {\color{red}6}x(x-1) + {\color{red}1}x(x-1)(x-2).\)
값 테이블의 세 번째 행을 비교하십시오.
Identities and relations
- \( L(n,k) = {n-1 \choose k-1} \frac{n!}{k!} = {n \choose k} \frac{(n-1)!}{(k-1)!} = {n \choose k} {n-1 \choose k-1} (n-k)!\)
- \( L(n,k) = \frac{n!(n-1)!}{k!(k-1)!}\cdot\frac{1}{(n-k)!} = \left (\frac{n!}{k!} \right )^2\frac{k}{n(n-k)!}\)
- \( L(n,k+1) = \frac{n-k}{k(k+1)} L(n,k).\)
- \( L(n+1,k) = (n+k) L(n,k) + L(n,k-1)\) 여기서 \(L(n,0)=0\), 모든 \(k > n\)에 대해 \(L(n,k)=0\)이고, \(L(1,1)=1\)입니다.
- \( L(n,k) = \sum_{j} \left[{n\atop j}\right] \left\{{j\atop k}\right\},\) 여기서 \(\left[{n\atop j}\right]\)는 첫 번째 종류의 스털링 숫자이고 \(\left\{{j\atop k}\right\}\)는 두 번째 종류의 스털링 숫자이고, \(L(0,0)=1\)와 모든 \(k>n\)에 대해 \(L(n, k)=0\)입니다.
- \( L(n,1) = n!\)
- \( L(n,2) = (n-1)n!/2\)
- \( L(n,3) = (n-2)(n-1)n!/12\)
- \( L(n,n-1) = n(n-1)\)
- \( L(n,n) = 1\)
- \(\sum_{n\geq k} L(n,k)\frac{x^n}{n!} = \frac{1}{k!}\left( \frac{x}{1-x} \right)^k\)
Recent practical application
최근 몇 년 동안, 라 숫자는 이미지에서 데이터를 숨기기 위한 스테가노그래피(steganography)에서 사용되어 왔습니다. Sudipta Kumar Ghosal과 같은 몇몇 연구원은 복잡성이 낮기 때문에 DCT, DFT, 및 DWT의 대안으로 이 영역에서 그것들을 활용해 왔는데, 왜냐하면 정수 계수의 계산의 낮은 복잡도-\(O(n \log n)\)-때문입니다.
See also