I've been banging my head on this problem for some time now, and could really use help. Bear in mind I'm not very good at this sort of thing and am struggling to get by in class.
Problem:
Given $ \alpha : A \to B \;\;\;\;\; |A|=p \;\;\;\;|B|=q $
Find:
- Number of Injections: $A \to B$
- Number of Surjections: $ A \to B$
- Prove that ∃ a bijection $A \to B$
- $\Rightarrow$ p = q
- find number of bijections: $A \to B$
I apologize for dropping such a big problem on you all, but I just can't get anywhere with this. Help?
EDIT:
These answers are really helpful and I believe I've got down the number of Injections, but we haven't gone through permutations or combinatorics in class so my understanding of it is really hamstrung. I'm unclear on the Stirling theorem as discussed here: http://www.ma.utexas.edu/users/kbi/COURSES/TERM/11S/325K/L17.pdf, specifically the part where inclusion-exclusion comes into play. I'm not sure how to apply that, since right now I'm letting p = 4 and q = 3, so I don't know where inclusion-exclusion would be used (if at all!) since I don't know how elements would be missing.
Best Answer