# find the number of injections/surjections

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.

• Number of injections is not so hard --- I suggest you try a few small examples like $p=2$, $q=3$ and see what patterns you find. Surjections is harder, usual answer uses inclusion-exclusion principle (which see) and leads to Stirling numbers (ditto). Bijections are permutations --- ever come across combinations and permutations? Now is the time to dust them off. – Gerry Myerson May 24 '13 at 23:50
• Have you looked at the links in the answer by @Walker? – Gerry Myerson May 25 '13 at 4:08
• Oohh. I did but I didn't understand how they applied until I just looked again just now. – Harry Tuttle May 25 '13 at 19:28

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.

Here we elaborate on the theory that allows us to count the number of permutations on a finite set $$A$$.

Definition: If $$A$$ is a finite set with $$n$$ elements we call any bijection $$\rho: A \to A$$ a permutation
and we denote the set of all permutations by $$S_A$$.

It is easy to argue that when two finite sets have the same cardinality, then the corresponding sets of permuatations are finite and have identical cardinalities.

Lemma: Let $$B$$ be a finite set with $$n$$ elements and let the cardinality of $$S_B$$ be $$\gamma$$.
If $$A = B \cup \{\hat a\}$$ where $$\hat a \notin B$$, then the set $$S_A$$ contains exactly $$\gamma (n+1)$$ permutaions.
Proof
Let $$\mathcal B = \{\rho \in S_A \; | \; \rho(\hat a) = \hat a\}$$. Let

$$\tag 1 C = \{\rho \in S_A \; | \; \rho \text{ is the identity map or a transposition }(\hat a \, b) \text{ with } b \in B\}$$

The set $$C$$ has exactly $$n+1$$ elements. It is easy to see that

$$\tag 1 (\beta, \rho) \mapsto \beta \circ \rho$$

defines a bijective correspondence between the Cartesian product $$\mathcal B \times C$$ and $$S_A$$.

It is also an easy matter to put $$\mathcal B$$ and $$S_B$$ into bijeective correspondence. $$\quad \blacksquare$$

The above will certainly motivate us to develop the Capital Pi notation so that we can examine the function

$$F(n) = \prod _{k=1}^{n} k$$

Since it is so important, we use the definition/abbreviation $$n!$$ for $$F(n)$$.