Ordered partition of a set

From Wikipedia, the free encyclopedia

In combinatorial 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 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:

T_n=\sum_{i=0}^{n-1} {n \choose i} T_i.

Furthermore, the exponential generating function is

\sum_n {T_n \over n!} x^n = {1 \over 2-e^x}.

An ordered partition of "type k_1+\cdots+k_m is one in which the ith part has ki members, for i = 1, ..., m. The number of such partitions is given by the multinomial coefficient

{n \choose k_1, \dots, k_m} = {n! \over k_1!\cdots k_m!}.
Retrieved from "http://en.wikipedia.org../../../o/r/d/Ordered_partition_of_a_set.html"