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:
“Walls have cracks and partitions ears.”
—Chinese proverb.
“To the extent to which genius can be conjoined with a merely good human being, Haydn possessed genius. He never exceeds the limits that morality sets for the intellect; he only composes music which has “no past.””
—Friedrich Nietzsche (1844–1900)
“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)