In how many ways can $k$ distinct objects be placed in $n$ distinct boxes?

Question

In how many ways can $k$ distinct objects be placed in $n$ distinct boxes? Allegedly the correct answer is $n^k$ times, I just don't know how to arrive to this answer. In the first box I believe I have $\sum_{i=0}^{k}\binom{k}{i}$ options no? Then for the subsequent one I can't think of an expression. How should I go about this?

Answer 1

Consider functions from set $A=\{1,2,3, \ldots , k\}$ to set $B=\{1,2,3, \ldots, n\}$. Think of your objects as members of set $A$ and your bins as members of set $B$. Number of ways to do this assignment will be simply the number of function from $A$ to $B$.

To count the latter, the first element $1$ has $n$ choices, the second element $2$ also has $n$ choices and so on. Thus the number of functions is $n \cdot n \cdot \dotsb n=n^k$.

Answer 2

The problem with thinking about the number of choices for the first bin, then the second bin, and so on, is that each of these depends on the previous ones. You are right that there are $\sum_{i=0}^k\binom ki$ choices for the first box - this is the binomial expansion of $(1+1)^k$, so equals $2^k$, but then the number of choices for the second box depends on how many objects are left.

The right way to think of it is instead to consider the number of choices for the first object, then the second object and so on. For each object there are $n$ choices, and these are independent, so you can just multiply them together to get $n\times n\times...\times n=n^k$.