How to Find the Number of Injections and Surjections

elementary-set-theoryfunctions

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:

  1. Number of Injections: $A \to B$
  2. Number of Surjections: $ A \to B$
  3. 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

  1. The number of bijections is given by $n!$, in which $n$ denotes the common cardinality of your sets. To see this, note that any bijection can be written as a permutation followed by a given bijection.
  2. An injection is a bijection onto its image. Thus you can find the number of bijections by counting the possible images and multiplying by the number of bijections to said image. In your notation, this number is $$\binom{q}{p} \cdot p!$$
  3. As others have mentioned, surjections are far harder to calculate. They satisfy certain recursions, e.g. given here. The number of surjections is also related to the Stirling numbers (of the second kind.
Related Question