Lach numbers

Illustration of unsigned lach numbers for n and k between 1 and 4

Lach numbers , discovered by a mathematician from Slovenia, Ivo Lah in 1955 ^[1] , are coefficients expressing increasing factorials in terms of decreasing factorials .

Unsigned Lach numbers have interesting meanings in combinatorics - they reflect the number of ways in which a set of n elements can be divided into k nonempty ordered subsets. Lach numbers are related to Stirling numbers .

Unsigned Lach numbers (sequence A105278 in OEIS ):

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

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

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

Signed Laha numbers (sequence A008297 in OEIS ):

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

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

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

L ( n , 1) is always n ! In the above interpretation of partitioning the set {1, 2, 3} into 1, the set can be implemented in 6 ways:

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

L (3, 2) corresponds to 6 partitions into two ordered sets:

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

L ( n , n ) is always equal to 1, because, for example, splitting the set {1, 2, 3} into 3 nonempty subsets leads to subsets of length 1.

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

When using the Karamat-Knuth notation for Stirling numbers, it was proposed to use the following alternative notation for Lach numbers:

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

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

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

Content

1 Rising and decreasing factorials
2 Identities and Relationships
3 table of values
4 See also
5 notes
6 Literature

Rising and decreasing factorials

Let be $x^{(n)}$ ${\ displaystyle x ^ {(n)}}$ denotes an increasing factorial $x(x+1)(x+2)\cdots (x+n-1)$ ${\ displaystyle x (x + 1) (x + 2) \ cdots (x + n-1)}$ , but $(x)_{n}$ ${\ displaystyle (x) _ {n}}$ - decreasing factorial $x(x-1)(x-2)\cdots (x-n+1)$ ${\ displaystyle x (x-1) (x-2) \ cdots (x-n + 1)}$ .

Then $x^{(n)}=\sum _{k=1}^{n}L(n,k)(x)_{k}$ ${\ displaystyle x ^ {(n)} = \ sum _ {k = 1} ^ {n} L (n, k) (x) _ {k}}$ and $(x)_{n}=\sum _{k=1}^{n}(-1)^{n-k}L(n,k)x^{(k)}.$ ${\ displaystyle (x) _ {n} = \ sum _ {k = 1} ^ {n} (- 1) ^ {nk} L (n, k) x ^ {(k)}.}$

For example, $x(x+1)(x+2)={\color {red}6}x+{\color {red}6}x(x-1)+{\color {red}1}x(x-1)(x-2).$ ${\ displaystyle x (x + 1) (x + 2) = {\ color {red} 6} x + {\ color {red} 6} x (x-1) + {\ color {red} 1} x (x -1) (x-2).}$

Compare with the third row of the value table.

Identities and Relationships

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)!

{\ displaystyle 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} (nk)!}

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)!}}

{\ displaystyle L (n, k) = {\ frac {n! (n-1)!} {k! (k-1)!}} \ cdot {\ frac {1} {(nk)!}} = \ left ({\ frac {n!} {k!}} \ right) ^ {2} {\ frac {k} {n (nk)!}}}

L(n,k+1)={\frac {n-k}{k(k+1)}}L(n,k).

{\ displaystyle L (n, k + 1) = {\ frac {nk} {k (k + 1)}} L (n, k).}

L(n,k)=\sum _{j}\left[{n \atop j}\right]\left\{{j \atop k}\right\},

{\ displaystyle L (n, k) = \ sum _ {j} \ left [{n \ atop j} \ right] \ left \ {{j \ atop k} \ right \},}

Where

\left[{n \atop j}\right]

{\ displaystyle \ left [{n \ atop j} \ right]}

- Stirling numbers of the first kind , and

\left\{{j \atop k}\right\}

{\ displaystyle \ left \ {{j \ atop k} \ right \}}

- Stirling numbers of the second kind . If you accept that

L(0,0)=1

{\ displaystyle L (0,0) = 1}

and

L(n,k)=0

{\ displaystyle L (n, k) = 0}

at

k>n

{\ displaystyle k> n}

.

L(n,1)=n!

{\ displaystyle L (n, 1) = n!}

L(n,2)=(n-1)n!/2

{\ displaystyle L (n, 2) = (n-1) n! / 2}

L(n,3)=(n-2)(n-1)n!/12

{\ displaystyle L (n, 3) = (n-2) (n-1) n! / 12}

L(n,n-1)=n(n-1)

{\ displaystyle L (n, n-1) = n (n-1)}

L(n,n)=1

{\ displaystyle 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}

{\ displaystyle \ sum _ {n \ geq k} L (n, k) {\ frac {x ^ {n}} {n!}} = {\ frac {1} {k!}} \ left ({\ frac {x} {1-x}} \ right) ^ {k}}

Value Table

Lach value table:

$_{n}\!\!\diagdown \!\!^{k}$ ${\ displaystyle _ {n} \! \! \ diagdown \! \! ^ {k}}$	one	2	3	four	5	6	7	8	9	10	eleven	12
one	one
2	2	one
3	6	6	one
four	24	36	12	one
5	120	240	120	twenty	one
6	720	1800	1200	300	thirty	one
7	5040	15120	12600	4200	630	42	one
8	40320	141120	141120	58800	11760	1176	56	one
9	362880	1451520	1693440	846720	211680	28224	2016	72	one
10	3628800	16329600	21772800	12700800	3810240	635040	60480	3240	90	one
eleven	39916800	199584000	299376000	199584000	69854400	13970880	1663200	11880	4950	110	one
12	479001600	2634508800	4390848000	3293136000	1317254400	307359360	43908480	3920400	217800	7260	132	one

Notes

↑ Riordan, 1958 .

Literature

John Riordan. Introduction to Combinatorial Analysis . - Princeton University Press, 1958. - ISBN 978-0-691-02365-6 . The article was reprinted in 1980, and one more time in 2002 (Dover Publications)

[_95f236f86202249d-1] Riordan, 1958 .