Ordered partition of a set
Encyclopedia
In combinatorial
mathematics
, an ordered partition O of a set S is a sequence
of subset
s 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
which is equivalent to
but distinct from
The number of ordered partitions Tn of { 1, 2, ..., n } can be found recursively by the formula:
Furthermore, the exponential generating function is
An ordered partition of "type
" 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
For example, for n = 3:
Together this is the ordered Bell number 13.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an ordered partition O of a set S is a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
- A1, A2, A3, ..., An
of subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of S, with union is S, which are non-empty, and pairwise disjoint. This differs from a partition of a set
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
, 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:
Furthermore, the exponential generating function is
An ordered partition of "type
" is one in which the ith part has ki members, for i = 1, ..., m. The number of such partitions is given by the multinomial coefficientFor 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.