Where the Stirling partition numbers *S*(*n*, *k*)
describe the number of ways a set with *n* elements can be partitioned into
*k* disjoint, non-empty unordered subsets, the Lah numbers *L _{n, k}*
describe the same situation where the contents of the subsets are ordered.

For example, *L*_{3, 2} corresponds to partitions of the three elements {A, B, C}
into two ordered subsets (the order of the subsets themselves doesn’t matter, though) in these ways:

- {{A, B}, {C}}
- {{B, A}, {C}}
- {{A, C}, {B}}
- {{C, A}, {B}}
- {{B, C}, {A}}
- {{C, B}, {A}}

So *L*_{3, 2} = 6. (With the Stirling partition numbers, on the other hand,
{A, B} is the same as {B, A}, so removing these “duplicates” gives us *S*(3, 2) = 3.)

Jumping right in, *L*_{2, 1} = 2! = 2. In other words, the set of two items
can be “divided” into one ordered subset in these two ways:

*L*_{2, 2} = 1:

*L*_{3, 1} = 3! = 6.
(In fact, *L*_{n, 1} is always *n*!, since the one subset of
*n* items can be ordered in *n*! ways.)

*L*_{3, 2} = 6:

*L*_{3, 3} = 1. (*L*_{n, n} is always 1,
since the *n* items can be divided into *n* subsets in only the one way.)

*L*_{4, 1} = 4! = 24, about which see
permutations.

*L*_{4, 2} = 36. Of those 36, 24 look like this:

And 12 of them look like this:

*L*_{4, 3} = 12:

*L*_{4, 4} = 1:

Sums of Stirling partition numbers are the Bell numbers, sums of Narayana numbers are the Catalan numbers, but sums of Lah numbers don’t seem to have a common name.

See Riordan, Introduction to Combinatorial Analysis, New York: Dover Publications, 2002, pp. 43–44.

Designed and rendered using *Mathematica* 7.0.

Copyright © 2011–2018 by Robert Dickau.

[ home ] || [ 2013-09-22 ]

www.robertdickau.com/lah.html