Lah number

From Wikipedia, the free encyclopedia

In mathematics, Lah numbers, discovered by Ivo Lah in 1955,[1] 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 subsets and in such a way that all elements of the same subset are linearly ordered. 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'(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 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 was proposed to use the following alternative notation for Lah numbers:

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

[edit] See also

[edit] References

  1. ^ Introduction to Combinatorial Analysis Princeton University Press (1958, reissue 1980) ISBN 978-0691023656 (reprinted again in 2002, by Courier Dover Publications).
Languages