Partitions

In mathematics, a partition of a set X is a collection of nonempty, pairwise disjoint subsets whose union is X. Each element of X belongs to exactly one subset, called a block or part.

Partitions are closely linked to equivalence relations: two elements are in the same block if and only if they are equivalent. Conversely, the blocks of an equivalence relation form a partition of the set.

Counting partitions of a finite set: The number of partitions of an n-element set is the Bell number B_n. The number of partitions into k blocks is the Stirling number of the second kind, S(n,k).

Integer partitions: A partition of a positive integer n is a way of writing n as a sum of positive integers without regard to order. Examples for n = 4 are 4; 3 + 1; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1. The function p(n) counts such partitions, and the partitions can be visualized with Ferrers diagrams or Young tableaux.

Applications and related ideas: Partitions appear throughout combinatorics and number theory, in the study of symmetry, and in the organization of data. In computing, a disk partition divides a storage device into independent regions with separate file systems. In statistics and machine learning, data are often partitioned into training and testing sets or into cross-validation folds. In topology, partitions induced by equivalence relations lead to quotient spaces, and the partition into connected components is a fundamental example.