Subsetcomposities

Subsetcomposities are a concept in combinatorics describing ordered partitions of a finite set into nonempty, pairwise disjoint subsets whose union is the original set. They are also known in the literature as set compositions or ordered partitions. Formally, if X is a finite set, a subsetcompositie of X is an ordered k-tuple (B1, B2, ..., Bk) where each Bi is a nonempty subset of X, the Bi are pairwise disjoint, and the union of all Bi equals X. The order of the blocks matters, so (B1, B2) and (B2, B1) are different subsetcomposities.

Counting and characteristics: For a set of size n, the number of subsetcomposities is the nth ordered Bell number, often denoted a(n). It equals sum_{k=1}^n k! S(n, k), where S(n, k) are the Stirling numbers of the second kind. Equivalently, for a fixed k, the number of subsetcomposities with k blocks equals the number of surjections from an n-element set onto a k-element set, which is k! S(n, k). The sequence begins 1, 3, 13, 71, 461, 3447, ... for n = 1, 2, 3, 4, 5, 6, respectively.

Example: Let X = {a,b,c}. There are 13 subsetcomposities. Examples include ({a},{b},{c}), ({a,b},{c}), ({a},{b,c}), and ({a,b,c}) as the single-block composition, among others.

Relation to other concepts: Subsetcomposities correspond to surjections from X onto an ordered set {1,...,k} for some k, and hence to weak orderings when blocks are considered with their order. Variants may allow empty blocks, yielding weak subsetcomposities. Subsetcomposities have applications in data organization, hierarchical clustering, and the study of ordered classifications.