Lah number

Original article: w:Lah number

Illustration of the unsigned Lah numbers for n and k between 1 and 4

수학(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):

$L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}.$

부호화된 라 숫자 (OEIS에서 수열 A008297):

$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) 표기법을 적용하여, 라 숫자에 대해 다음 대안적인 표기법을 사용하는 것이 제안되어 왔습니다"

$$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)}$입니다.

예를 들어, $$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}$

Table of values

아래는 랄 숫자에 대해 값의 테이블입니다:

k n	1	2	3	4	5	6	7	8	9	10	11	12
1	1
2	2	1
3	6	6	1
4	24	36	12	1
5	120	240	120	20	1
6	720	1800	1200	300	30	1
7	5040	15120	12600	4200	630	42	1
8	40320	141120	141120	58800	11760	1176	56	1
9	362880	1451520	1693440	846720	211680	28224	2016	72	1
10	3628800	16329600	21772800	12700800	3810240	635040	60480	3240	90	1
11	39916800	199584000	299376000	199584000	69854400	13970880	1663200	11880	4950	110	1
12	479001600	2634508800	4390848000	3293136000	1317254400	307359360	43908480	3920400	217800	7260	132	1

Recent practical application

최근 몇 년 동안, 라 숫자는 이미지에서 데이터를 숨기기 위한 스테가노그래피(steganography)에서 사용되어 왔습니다. Sudipta Kumar Ghosal과 같은 몇몇 연구원은 복잡성이 낮기 때문에 DCT, DFT, 및 DWT의 대안으로 이 영역에서 그것들을 활용해 왔는데, 왜냐하면 정수 계수의 계산의 낮은 복잡도—$O(n\log n)$—때문입니다.

See also

• Stirling numbers
• Pascal matrix