Ordered partition of a set

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:

$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 k_i 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!}.$

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