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

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 numberhttp://en.wikipedia.org../../../../articles/s/t/r/Strict_weak_ordering.html#The_number_of_weak_orders 13.

[edit] References

 This article does not cite any references or sources. (January 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.