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.

  • $\begingroup$ so you can have multiple balls in a bin? $\endgroup$ – jkabrg Jun 8 '15 at 17:23
  • $\begingroup$ @user3491648 yes. $\endgroup$ – A user Jun 8 '15 at 17:25
  • 1
    $\begingroup$ Just to make sure, for part a are we assuming that none of the bins can be empty? $\endgroup$ – CosmoVibe Jun 8 '15 at 17:40
  • $\begingroup$ For part a, you're counting the number of functions from an $N+1$-set to an $N$-set, which is $N^{N+1}$. $\endgroup$ – jkabrg Jun 8 '15 at 17:41
  • $\begingroup$ 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. $\endgroup$ – jkabrg Jun 8 '15 at 17:42

ok. so all balls are distinguishable, so order matters.

for part a), i guess all bins should be non empty. so I get N+1_N permutations and then i multiply this by N for the different hypotheses for the extra ball in each of the permutations. that arranges to

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

in part b, if exactly one bin is empty then you can either have two bins with two balls or one bin with three balls (all other N-1 bins have one ball), and you just add all those permutations up...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.