 Ordered partition of a set

In combinatorial mathematics, an ordered partition O of a set S is a sequence
 A_{1}, A_{2}, A_{3}, ..., A_{n}
of subsets of S, with union is S, which are nonempty, and pairwise disjoint. This differs from a partition of a set, in that the order of the A_{i} matters.
For example, one ordered partition of { 1, 2, 3, 4, 5 } is
 {1, 2} {3, 4} {5}
which is equivalent to
 {1, 2} {4, 3} {5}
but distinct from
 {3, 4} {1, 2} {5}.
The number of ordered partitions T_{n} of { 1, 2, ..., n } can be found recursively by the formula:
Furthermore, the exponential generating function is
An ordered partition of "type " is one in which the ith part has k_{i} members, for i = 1, ..., m. The number of such partitions is given by the multinomial coefficient
For example, for n = 3:
 type 1+1+1: 6
 type 2+1: 3
 type 1+2: 3
 type 3: 1
Together this is the ordered Bell number 13.
See also
 Partitions of a set
References
Categories:
Wikimedia Foundation. 2010.