Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Let and . A function from one set to another sends every element of the first set to exactly one element of the second.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
(a) Each element of has 3 choices: .
(b) Functions that miss a given element of : ; that miss two given elements: . By inclusion and exclusion, onto functions number .
(c) From to , the three elements take different images: .
(d) Choose the two elements of the range in ways; the functions onto those two number . So . (Check: , with 3 constant functions.)
(e) Such a function is fixed once we know how many elements go to 1, to 2 and to 3: whole numbers . By stars and bars there are .
Check. Listing all functions (and all maps from to ) by computer gives the same five counts.
Watch out. In (b), do not stop at : the constant functions were taken away twice and must be added back.
Log in to join the discussion.
Loading…