Number of functions on finite set If $A$ has $n$ elements, how many functions are there from $A \rightarrow A$? How many bijective functions are there from $A$ to $A$?
My thinking was that there are $n$ possibilities for $f(a_1)$, $n$ possibilities for $f(a_2)$, etc., so there should be $n^n$ functions from $A$ to $A$.
For bijective, there should be $n$ possibilities for $f(a_1)$, $(n-1)$ possibilities for $f(a_2)$, $(n-2)$ possibilities for $f(a_3)$, etc. Not sure how to express it correctly.
 A: Total functions from A -> A are
$$n^n$$
as there are n choices with which one element of 1st set can be assigned to n elements of the same set of n elements.
Number of bijective functions are
$$n! = n.(n-1).(n-2)...1$$
as the number of elements of both sets = n, so 1 bijection can be arranged in n! ways to get other bijective funtions.
A: There is a neat notational convention that goes along with this idea.  For instance if you have a set $B$ with $n$ elements and a set $A$ with $m$ elements, then the number of functions from $A$ to $B$ is $n^m$.
(And there are $n\cdot(n-1)\cdots (n-m-1) = \frac{n!}{m!}=\ _nP_m$ injective functions.)
Here we see that the cardinality of the set of functions from $A$ to $B$ is $|B|^{|A|}$.  This set can be denoted by $B^A$.  Which makes sense independently, since you can think of each function as a vector in $B^m$.
Extending this idea, we can label the set of sequences of elements of $B$ as $B^{\mathbb{N}}$.  Here we can think of this as a collection of functions from the natural numbers to $B$.  Similarly we label the set of functions from $\mathbb{R}$ to $B$ as $B^\mathbb{R}$.
Finally we can talk about subsets of the real numbers as $2^{\mathbb{R}}$.  This is the set of functions from $\mathbb{R}$ to the set $\{0,1\}$.  We have a correspondence with subsets of $\mathbb{R}$ by taking a function $f \in 2^{\mathbb{R}}$ and making a set $A_f = \{ x \in \mathbb{R} : f(x) = 1\}$.  This is a bijective correspondence between these functions and subsets.  Of course this is not only restricted to $\mathbb{R}$.
The cool thing here is that if you take two functions $f, g \in 2^{\mathbb{R}}$ then $A_{f\cdot g} = A_f \cap A_g$.  And taking $f + g$ to be the function $(f+g)(x) = max\{f(x), g(x)\}$ then we have $A_{f+g} = A_f \cup A_g$.
I know this is a bit of a tangent, but I always thought this was a neat idea.
