Counting functions

#functions#product rule#counting

Statement

How many functions from an $m$ -element set to an $n$ -element set are there?

Hint

Each of the $m$ elements has $n$ independent choices.

Show solutionHide solution

Product rule. $n$ choices for each of the $m$ elements: $n^m$ total.

Conclusion. There are $n^m$ functions.

Example. $m=3$ , $n=2$ : $2^3=8$ functions.