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.
“Until, accustomed to disappointments, you can let yourself rule and be ruled by these strings or emanations that connect everything together, you haven’t fully exorcised the demon of doubt that sets you in motion like a rocking horse that cannot stop rocking.”
—John Ashbery (b. 1927)
“All ye poets of the age,
All ye witlings of the stage,
Learn your jingles to reform,
Crop your numbers to conform.
Let your little verses flow
Gently, sweetly, row by row;
Let the verse the subject fit,
Little subject, little wit.
Namby-Pamby is your guide,
Albion’s joy, Hibernia’s pride.”
—Henry Carey (1693?–1743)