Ordered partition of a set

From Free net encyclopedia

In combinatorial mathematics, an ordered partition O of a set S is a sequence

A₁, A₂, A₃, ..., A_n

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

<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>

An ordered partition of "type <math>k_1+\cdots+k_m</math> 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

<math>{n \choose k_1, \dots, k_m} = {n! \over k_1!\cdots k_m!}.</math>