# Number of ways to put N + 1 balls into N bins with one bin empty

I will denote the two parts to my question a and b. I'm first trying to figure out first the number of ways to put $N + 1$ distinguishable balls into $N$ distinguishable bins, and then to find the same thing except with exactly one bin empty. The way I've currently approached part a is as follows:

Part a

There are $_{(N+1)}P_N$ ways to arrange the $N+1$ ball among the $N$ bins, which is $(N+1)!$ However, since there will always be one ball remaining after $N$ of them have been sorted, there are $_{N+1} C _{2}$, or $\frac{(N+1)!}{(N+1-2)!2!}$ ways of choosing two pairs of balls to "double up" in the same box. Thus I think the number of ways is $(N+1)_{N+1}C_2$. Is this correct?

Part b

Now in the case when exactly one bin is empty: firstly, there are $N$ ways to choose an empty box. Then there are $(N+1)N-1$ or $_{(N+1)!}P_{N-1}$ permutations of the $N+1$ balls. Finally, I need to some how choose which balls to double up. This is my main confusion.

• so you can have multiple balls in a bin? – jkabrg Jun 8 '15 at 17:23
• @user3491648 yes. – A user Jun 8 '15 at 17:25
• Just to make sure, for part a are we assuming that none of the bins can be empty? – CosmoVibe Jun 8 '15 at 17:40
• For part a, you're counting the number of functions from an $N+1$-set to an $N$-set, which is $N^{N+1}$. – jkabrg Jun 8 '15 at 17:41
• For part b, if you set aside one bin and then count the number of surjections from an $N+1$-set to an $N-1$-set, and then multiply by $N$ because of symmetry, you get the answer. – jkabrg Jun 8 '15 at 17:42

$$\left[ (n+1)! \right]^n$$