n+1 balls put into n bins. Double count?

Question

Question: n+1 balls are put into n bins. What is the probability that all of the bins are not empty (contain 1 ball at least)?

What I did:

Choose n balls from the n+1 ${n+1 \choose n}$, order them in the bins (n!), choose one bin to put the remaining ball in (n). That sums up to: ${n+1 \choose n}n!n$. I think there's a double count somewhere, but it all seems logical to me... Anyone can please explain me what I have counted twice? ($|\Omega|$ - is the number of ways to put the balls in the bins) $|\Omega| = n^{n+1}$ of course. So the probability is ${{n+1 \choose n}n!n} \over {n^{n+1}}$

Answer 1

How many ways ate there to put $n+1$ balls into $n$ bins? How many ways are there such that every bin has at least one ball?

Answer 2

Let us make a probability model of the situation. We have $n+1$ labelled balls, and $n$ bins. We toss the balls one at a time towards the bins. Assume that a ball is rqually likely to land in any of the bins, and that the results of the $n+1$ tosses are independent.

The experiment has $n^{n+1}$ equally likely outcomes.

We now count the "favourable" outcomes, the ones in which no bin is empty.

The two balls that will end up t0gether can be chosen in $\dbinom{n+1}{2}$ ways. Glue these two balls together. We now have $n$ "balls". They can be arranged among the $n$ bins, one "ball" to each bin, in $n!$ ways.

Thus the number of favourables is $\dbinom{n+1}{2}n!$.

Remark: You have almost the same answer, just off by a factor of $2$. At a certain stage, you chose $n$ balls to be arranged in the bins, so implicitly you chose $1$ ball to be temporarily left behind. Then you chose where to place that ball.

Imagine two balls, A and B. Included in your count is A being left behind, and the remaining balls being arranged in alphabetical order, so with B in the first bin. And then A being placed also in the first bin.

You have also counted B being left behind, the others arranged in order, and then B being placed to join A in the first bin.

But these give the same function from the set of balls to the set of bins.

Answer 3

Your double count was here: choose $n$ balls from $n+1$ and than place the remaining one. What difference is when:

I choose balls 1..5 and place them in order and ball 6 give to the same basket as ball 5.

I choose balls 1..4 and 6, place them in order and ball 5 place to the same basket as ball 6.