In mathematics, the Lah numbers, discovered by

Ivo Lah Ivo Lah (; 5 September 1896 – 23 March 1979) was a Slovenian mathematician and actuary, best known for his discovery of the Lah numbers in 1955 and for the Lah identity. In the 1930s, Lah made the first tables about mortality rates in Slov ...

in 1954, are

coefficient In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...

s expressing

rising factorial In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \ ...

s in terms of

falling factorial In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \ ...

s. They are also the coefficients of the

n

th derivatives of

e^

. Unsigned Lah numbers have an interesting meaning in

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

: they count the number of ways a set of ''n'' elements can be partitioned into ''k'' nonempty linearly ordered

subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...

s. Lah numbers are related to

Stirling number In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were redisc ...

s. Unsigned Lah numbers : :

L(n,k) =  \frac.

Signed Lah numbers : :

L'(n,k) = (-1)^n  \frac.

''L''(''n'', 1) is always ''n''!; in the interpretation above, the only partition of into 1 set can have its set ordered in 6 ways: :, , , , or ''L''(3, 2) corresponds to the 6 partitions with two ordered parts: :, , , , or ''L''(''n'', ''n'') is always 1 since, e.g., partitioning into 3 non-empty subsets results in subsets of length 1. : Adapting the Karamata– Knuth notation for

Stirling numbers In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were redisco ...

, it has been proposed to use the following alternative notation for Lah numbers:

\left\

Rising and falling factorials

Let

x^

represent the rising factorial

x(x+1)(x+2) \cdots (x+n-1)

and let

(x)_n

represent the falling factorial

x(x-1)(x-2) \cdots (x-n+1)

. Then

x^ = \sum_^n L(n,k) (x)_k

and

(x)_n = \sum_^n (-1)^ L(n,k)x^.

For example,

x(x+1)(x+2) = x + x(x-1) + x(x-1)(x-2).

Compare the third row of the table of values.

Identities and relations

L(n,k) =  \frac =  \frac =   (n-k)!

L(n,k) = \frac\cdot\frac = \left (\frac \right )^2\frac

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

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

where

L(n,0)=0

L(n,k)=0

for all

k > n

, and

L(1,1)=1.

L(n,k) = \sum_ \left

right Rights are legal, social, or ethical principles of freedom or entitlement; that is, rights are the fundamental normative rules about what is allowed of people or owed to people according to some legal system, social convention, or ethical th ...

\left\, where

\left

/math> are the

Stirling numbers of the first kind In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed poi ...

and

\left\

are the

Stirling numbers of the second kind In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \le ...

L(0,0)=1

, and

L(n, k)=0

for all

k>n

. :

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_ L(n,k)\frac = \frac\left( \frac \right)^k

Table of values

Below is a table of values for the Lah numbers:

Recent practical application

In recent years, Lah numbers have been used in

steganography Steganography ( ) is the practice of representing information within another message or physical object, in such a manner that the presence of the information is not evident to human inspection. In computing/electronic contexts, a computer file, ...

for hiding data in images. Compared to alternatives such as DCT, DFT and DWT, it has lower complexity—

O(n \log n)

—of calculation of their integer coefficients. The Lah and Laguerre transforms naturally arise in the perturbative description of the

chromatic dispersion In optics, and by analogy other branches of physics dealing with wave propagation, dispersion is the phenomenon in which the phase velocity of a wave depends on its frequency; sometimes the term chromatic dispersion is used for specificity t ...

. In Lah-Laguerre optics, such an approach tremendously speeds up optimization problems.

References

{{DEFAULTSORT:Lah Number Factorial and binomial topics Integer sequences Triangles of numbers

Rising and falling factorials

Identities and relations

Table of values

Recent practical application

See also

References