Lah number

In mathematics, Lah numbers, discovered by Ivo Lah in 1955, [http://books.google.com/books?id=zWgIPlds29UC "Introduction to Combinatorial Analysis"] Princeton University Press (1958, reissue 1980) ISBN 978-0691023656 (reprinted again in 2002, by Courier Dover Publications). are coefficients expressing rising factorials in terms of falling factorials.

Unsigned Lah numbers have an interesting meaning in combinatorics: they count the number of ways a set of "n" elements can be partitioned into "k" nonempty linearly ordered subsets. Lah numbers are related to Stirling numbers.

Unsigned Lah numbers:

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

Signed Lah numbers:

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

"L"("n", 1) is always "n"!; using the interpretation above, the only partition of {1, 2, 3} into 1 set can be ordered 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 the 6 partitions with two ordered parts:

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

"L"("n", "n") is always 1: partitioning {1, 2, 3} into 3 non-empty subsets results in subsets of length 1.

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

Paraphrasing Karamata-Knuth notation for Stirling numbers, it wasproposed to use the following alternative notation for Lah numbers:

:

See also

* Stirling numbers

References