Ordered partition of a set
Encyclopedia : O : OR : ORD : Ordered partition of a set
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 is
-
which is equivalent to
-
but distinct from
- .
The number of ordered partitions
Tn of can be found recursively by the formula:
- [T_n=\sum_^ T_i.]
Furthermore, the exponential generating function is
- [\sum_n x^n = .]
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
- [ = .]
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.
