Числа Лаха

Числа Лаха, открытые математиком из Словении Иво Лахом в 1955 — это коэффициенты, выражающие возрастающие факториалы через убывающие факториалы.

Иллюстрация беззнаковых чисел Лаха для n и k между 1 и 4

Беззнаковые числа Лаха имеют интересное значение в комбинаторике — они отражают число способов, каким множество из n элементов может быть разбито на k непустых упорядоченных подмножеств. Числа Лаха связаны с числами Стирлинга.

Беззнаковые числа Лаха (последовательность A105278 в OEIS):

$L(n,k)=(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})\frac{n!}{k!}.$$L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}.$

Числа Лаха со знаками (последовательность A008297 в OEIS):

$L^{\prime }(n,k)=(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})\frac{n!}{k!}.$$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)} or {(3), (2, 1)}

L(n, n) всегда равно 1, поскольку, например, разбиение множества {1, 2, 3} на 3 непустых подмножества приводит к подмножествам длины 1.

{(1), (2), (3)}

При использовании обозначения Карамата — Кнута для чисел Стирлинга было предложено использовать следующее альтернативное обозначение чисел Лаха:

$L(n,k)=\lfloor \begin{array}{c}n\\ k\end{array}\rfloor .$$L(n,k)=\left\lfloor {\begin{matrix}n\\k\end{matrix}}\right\rfloor .$

Возрастающие и убывающие факториалыПравить

Пусть $x^{(n)}$$x^{(n)}$  обозначает возрастающий факториал $x(x+1)(x+2)\cdots <!--\; \cdots \; -->(x+n-<!--\; -\; -->1)$$x(x+1)(x+2)\cdots (x+n-1)$ , а $(x{)}_n$$(x)_{n}$  — убывающий факториал $x(x-<!--\; -\; -->1)(x-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->(x-<!--\; -\; -->n+1)$$x(x-1)(x-2)\cdots (x-n+1)$ .

Тогда $x^{(n)}=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}L(n,k)(x{)}_k$$x^{(n)}=\sum _{k=1}^{n}L(n,k)(x)_{k}$  and $(x{)}_n=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}L(n,k)x^{(k)}.$$(x)_{n}=\sum _{k=1}^{n}(-1)^{n-k}L(n,k)x^{(k)}.$ 

Например, $x(x+1)(x+2)=6x+6x(x-<!--\; -\; -->1)+1x(x-<!--\; -\; -->1)(x-<!--\; -\; -->2).$$x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2).$ 

Сравните с третьей строкой таблицы значений.

Тождества и связиПравить

$L(n,k)=(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})\frac{n!}{k!}=(\genfrac{}{}{0ex}{}{n}{k})\frac{(n-<!--\; -\; -->1)!}{(k-<!--\; -\; -->1)!}=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})(n-<!--\; -\; -->k)!$$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 <!--\; \cdot \; -->\frac{1}{(n-<!--\; -\; -->k)!}={\left(\frac{n!}{k!}\right)}^2\frac{k}{n(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,k+1)={\frac {n-k}{k(k+1)}}L(n,k).$ 

$L(n,k)=\underset{j}{\sum <!--\; \sum \; -->}\left[\genfrac{}{}{0ex}{}{n}{j}\right]\left\{\genfrac{}{}{0ex}{}{j}{k}\right\},$$L(n,k)=\sum _{j}\left[{n \atop j}\right]\left\{{j \atop k}\right\},$  где $\left[\genfrac{}{}{0ex}{}{n}{j}\right]$$\left[{n \atop j}\right]$  — числа Стирлинга первого рода, а $\left\{\genfrac{}{}{0ex}{}{j}{k}\right\}$$\left\{{j \atop k}\right\}$  — числа Стирлинга второго рода. Если принять, что $L(0,0)=1$$L(0,0)=1$  и $L(n,k)=0$$L(n,k)=0$  при $k>n$$k>n$ .

$L(n,1)=n!$$L(n,1)=n!$ 

$L(n,2)=(n-<!--\; -\; -->1)n!/2$$L(n,2)=(n-1)n!/2$ 

$L(n,3)=(n-<!--\; -\; -->2)(n-<!--\; -\; -->1)n!/12$$L(n,3)=(n-2)(n-1)n!/12$ 

$L(n,n-<!--\; -\; -->1)=n(n-<!--\; -\; -->1)$$L(n,n-1)=n(n-1)$ 

$L(n,n)=1$$L(n,n)=1$ 

$\underset{n\ge <!--\; \ge \; -->k}{\sum <!--\; \sum \; -->}L(n,k)\frac{x^n}{n!}=\frac{1}{k!}{\left(\frac{x}{1-<!--\; -\; -->x}\right)}^k$$\sum _{n\geq k}L(n,k){\frac {x^{n}}{n!}}={\frac {1}{k!}}\left({\frac {x}{1-x}}\right)^{k}$ 

Таблица значенийПравить

Таблица значений чисел Лаха:

${}_n\mathrm{╲<!--\; ╲\; -->}{}^k$$_{n}\!\!\diagdown \!\!^{k}$	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

Современное практическое применениеПравить

В последние годы числа Лаха используются в стеганография для сокрытия данных в изображениях. По сравнению с такими альтернативами, как DCT, DFT и DWT, они имеют меньшую сложность—$O(n\log <!--\; \; -->n)$$O(n\log n)$ —вычисления их целочисленных коэффициентов. Преобразования Лаха и Лагерра естественно возникают при пертурбативном описании хроматической дисперсии. В оптика Лаха-Лагерра такой подход значительно ускоряет решение задач оптимизации.

См. такжеПравить

• Числа Стирлинга
• Матрица Паскаля