Partitions

Definition: Index set

Let be a set, . Suppose for every we have a set . Then is called the index set for the family of sets .

Definition: Partition

A partition of a set is a family of nonempty sets such that is the disjoint union of all sets in . Each is called a part of the partition.

Definition: Stirling numbers

We define the Stirling numbers as the number of partitions of an -set into parts (where ).

Theorem: Formula for Stirling numbers

, and for every where , Proof:
Let . When , the only possible partition is , and when , the only possible partition is , since sets in the partition must be nonempty. Finally, when , we have two cases for a partition: is in its own set, or is not in its own set. If is in its own set, the remaining elements must be partitioned into sets, which there are ways of doing. If is not in its own set, it must belong to a set in a -partition of the remaining items, which there are ways of doing, and since for each such way there are sets to which can belong, we multiply this by and arive at the formula.

Theorem: Equivalence classes form a partition

Let be an Equivalence relation Equivalence relation on a set . Then the equivalence classes with respect to form a partition of .

Proof:
Follows directly from Theorem Theorem.

For any partition of , we can define a function by . We see that is surjective and well defined, by the definition of a partition. On the other hand, for any surjective map we can for every define which makes a partition of .

Theorem

Let be the set of surjections from an -set to a -set . Then Proof:
A surjection from to is uniquely determined by the sets for every . These are partitions, and there are to create such partitions, and since each partition corresponds to exactly one element in , there are surjections for each such partition of .

If we also restrict the size of each , we get the Multinomial numbers Multinomial numbers.