How to approach this counting problem?

Question

Let $n ≥ 1$ be an integer. A function $f : \{1, 2, \ldots , n\} \to \{1, 2, \ldots, n\}$ is considered "valid", if there is at least one integer $i$ in $\{1, 2, \ldots, n\}$ for which $f(i) = i$.

Determine the number of valid functions.

I'm having problems understanding what this question is asking. I'm not even sure how to approach this. Could someone point me to the right direction? What technique should I be using to approach it?

I guess what's confusing me the most is this line here. Since I don't understand it.

A function $f : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}$

Answer 1

Let $A_i$ denote the number of functions for which $f(i) = i$. We need $\left|\cup_{i=1}^n A_i\right|$. Note that $|A_i| = n^{n-1}$. Also $|A_i \cap A_j| = n^{n-2}$. Thus by inclusion exclusion principle, $$\left|\cup_{i=1}^n A_i\right| = \binom{n}{1}n^{n-1} - \binom{n}{2}n^{n-2} +\cdots =n^n - (n-1)^n$$

Answer 2

For each of the $n$ elements of the domain of the function $f$, we must choose one element of the range. There are $n$ possibilities to choose from in the range. This means that the total number of functions from $\{1,2,\,...\,,n\}$ to $\{1,2,\,...\,,n\}$ is $$n^n$$

However, we have a restriction that your function has at least one fixed point.

Let's count the number of functions with no fixed points and subtract this from the total number of functions.

For each element of the domain, one choice from the range is not allowed.

We have $n-1$ choices for each of the $n$ elements of the domain.

This means that the number of functions from $\{1,2,\,...\,,n\}$ to $\{1,2,\,...\,,n\}$ with no fixed points is

$$(n-1)^{n}\,$$

The number of functions from $\{1,2,\,...\,,n\}$ to $\{1,2,\,...\,,n\}$ with at least one fixed point is equal to the total number of functions from $\{1,2,\,...\,,n\}$ to $\{1,2,\,...\,,n\}$, minus the number of functions with no fixed points. This is our final answer:

$$n^n - (n-1)^n$$

Answer 3

There $n^n$ functions $\{1,\dots,n\}\to\{1,\dots,n\}$ in total, since for every argument $i\in\{1,\dots,n\}$ we have $n$ choices.

There are $(n-1)^n$ functions that are not valid, since for these functions for every argument $i\in\{1,\dots,n\}$ we have $n-1$ choices (the choice "$i$" falls out).

Consequently there are $n^n-(n-1)^n$ valid functions.