Functions Between Sets

In combinatorics, we often count the number of functions between two finite sets satisfying specific properties (like injectivity or surjectivity).

Basic Counting

Let $A$ and $B$ be finite sets with $∣ A ∣ = k$ and $∣ B ∣ = n$ .

Theorem (Total Functions)

The total number of functions

f : A \to B

n^{k}

Proof. For each of the $k$ elements in $A$ , there are $n$ choices in $B$ . $n \times n \times \dots \times n = n^{k}$ . ∎

An injection requires that distinct inputs map to distinct outputs. This is only possible if

n \geq k

Theorem (Number of Injections)

The number of injective functions

f : A \to B

is:

P (n, k) = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)

Counting surjections is harder and typically requires the Principle of Inclusion-Exclusion or Stirling numbers of the second kind.

n = k

, a function is a bijection if and only if it is an injection (or surjection).

Theorem (Number of Bijections)

The number of bijections from a set of size

n

to itself is

n!

Exercise (Problem 1)

How many functions

f : {1, 2, 3} \to {a, b, c, d}

are there? How many are injective?

Exercise (Problem 2)

Let

A = {1, 2, 3, 4}

and

B = {1, 2, 3, 4, 5}

. What is the probability that a random function

f : A \to B

is strictly increasing?

Exercise (Problem 3)

Explain why there are no surjective functions from a set of size 3 to a set of size 4.