Ordered partition of a set
|
|
In mathematics, an ordered partition O of a set S is a sequence
- A1, A2, A3, ..., An
of subsets of S, with union is S, which are non-empty, and pairwise disjoint. This definition differs from a partition of a set, in that the order of the Ai 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 Tn of { 1, 2, ..., n } can be found recursively by the formula:
- <math>T_n=\sum_{i=0}^{n-1} {n \choose i} T_i.<math>
Furthermore, the exponential generating function is
- <math>\sum_n {T_n \over n!} x^n = {1 \over 2-e^x}.<math>