Let $A$ and $B$ be non-empty finite sets, $|A|=k, |B|=n$. The number of all possible partial functions from $A$ to $B$ is $(1+n)^k$. What is the combinatorial explanation for this?
I know that we can think of this problem as choosing $i$ elements of $A$ and then mapping them to $B$. This is: $$ \sum_{i=0}^k {k\choose i}n^i=(1+n)^k $$
But the sigma just happens to be equal to the binomial expansion. But why does the binomial expansion really represent the problem of counting partial functions?
For each element of $A$, there are $n+1$ options. It can not be part of the mapping, or it can be mapped to one of the $n$ elements of $B$. Since repetition is allowed, this gives a factor of $(1+n)$ for each element of $A$.