Technique
Number of onto functions onto a two-element set:
Algebra • Relations and Functions
Formula
If and , there are functions from to , and exactly of them are not onto (the two constant functions). So there are onto functions.
How to use it
- 1Each element of has 2 choices of image, so there are functions in all.
- 2A function into a 2-element set fails to be onto only when every element goes to the same image: there are 2 such functions.
- 3Subtract: onto functions .
Worked example
How many onto functions are there from to ?
Step-by-step
- 1All functions:
Why: Each of the 3 elements picks its image in 2 ways.
- 2Not onto: all to , or all to : functions
Why: Missing means everything goes to , and the other way round.
- 3
Answer
Watch out
counts all functions, not only onto ones. Do not use , which counts pairs, not functions.
Builds on
Also known as
surjective functions count, onto functions to two elements, number of onto maps