Partitions of Sets and Numbers
When viewing ƒ as a grouping of the elements of N (which assumes one identifies under permutations of X), requiring ƒ to be surjective means the number of groups must be exactly x. Without this requirement the number of groups can be at most x. The requirement of injective ƒ means each element of N must be a group in itself, which leaves at most one valid grouping and therefore gives a rather uninteresting counting problem.
When in addition one identifies under permutations of N, this amounts to forgetting the groups themselves but retaining only their sizes. These sizes moreover do not come in any definite order, while the same size may occur more than once; one may choose to arrange them into a weakly decreasing list of numbers, whose sum is the number n. This gives the combinatorial notion of a partition of the number n, into exactly x (for surjective ƒ) or at most x (for arbitrary ƒ) parts.
Read more about this topic: Twelvefold Way
Famous quotes containing the words partitions, sets and/or numbers:
“Great wits are sure to madness near allied,
And thin partitions do their bounds divide.”
—John Dryden (1631–1700)
“It is time to be old,
To take in sail:—
The god of bounds,
Who sets to seas a shore,
Came to me in his fatal rounds,
And said: ‘No more!’”
—Ralph Waldo Emerson (1803–1882)
“The only phenomenon with which writing has always been concomitant is the creation of cities and empires, that is the integration of large numbers of individuals into a political system, and their grading into castes or classes.... It seems to have favored the exploitation of human beings rather than their enlightenment.”
—Claude Lévi-Strauss (b. 1908)