From Harvard Stat 110
A hash table is being used to store the phone numbers of k people, storing each person's phone number in a uniformly random location, represented by an integer between 1 and n (see Exercise 25 from Chapter 1 for a description of hash tables). Find the expected number of locations with no phone numbers stored, the expected number with exactly one phone number, and the expected number with more than one phone number (should these quantities add up to n?).
Would someone, please, give me a reasoned solution for the expected number with exactly one phone number?
My argument is: Let $I_j$ be an i.r.v. for the $j^{th}$ location having exactly $1$ phone number. If we treat the $k$ phone numbers as a vector, each entry in the vector will have $n$ choices of locations. Now we choose one of the $k$ entries and send it into the $j^{th}$ location. Each one of the other $k-1$ entries have $n-1$ locations to choose from. Then, $P(I_j=1)=k((n-1)/n)^{k-1}$. Then we multiply by $n$ to get the expected value. But this is different from the book's answer.
Your argument is basically correct. By linearity of expectation, the expected number of slots with one item is $\sum{P(X_j=1)}$ where $X_j$ is the number of entries in slot $j$.
I think you have computed the probability wrong though. You neglected to multiply by the probability that the selected item is in slot $j$. There are $k$ ways to choose the item that will go in slot $j$. For each such item, the probability that it is slot $j$ is $1/n$ and the probability that the remaining $n-1$ items are in slots other than n is $\left(\frac{n-1}{n}\right)^{k-1}$ as you said. Thus $$P(X_j=1)=\frac{k}{n}\left(\frac{n-1}{n}\right)^{k-1}$$
Now we have to sum over all the slots, so we multiply by $n$ and the final answer is $$k\left(\frac{n-1}{n}\right)^{k-1}$$
Is this what the book gets?