1
$\begingroup$

A) if both objects and boxes and indistinguishable

B) if objects are indistinguishable and boxes are distinguishable

My attempt:

I know there are n! ways to but n objects into n boxes (both distinguishable).

A) I also know that to put n indistinguishable objects into n indistinguishable boxes we must count the number of partitions of n into n integers. I am unsure of how to calculate this and how to add the 1 box empty condition.

B) I know there are C(n + r − 1, n − 1) ways to place n indistinguishable objects into r distinguishable boxes. I can replace r with n. I am unsure of how to account for the 1 box empty condition here, as well.

$\endgroup$
  • 1
    $\begingroup$ What you tried? $\endgroup$ – Masacroso Nov 29 '15 at 22:30
  • 2
    $\begingroup$ There are $n^n$ ways to put $n$ objects into $n$ boxes if you allow multiple objects per box, which is the spirit of this question. $\endgroup$ – Ross Millikan Nov 29 '15 at 22:59
  • $\begingroup$ It is easier to work from the stronger condition "so no box remains empty" and then weaken it to "exactly one box remains empty", rather than what you are currently doing which is moving from "no restriction" to "exactly one box empty". $\endgroup$ – Morgan Rodgers Nov 29 '15 at 23:00
1
$\begingroup$

If both objects and boxes are distinguishable:
There are $n$ ways to select a box that'll be empty. Since rest of the boxes will have at least 1 object each, therefore there will one box out of the $n-1$ that will have two objects in it. There are $n-1$ ways to choose this box. Further, we have ${n\choose2}$ ways to put two objects in the selected box and $(n-2)!$ ways to arrange the rest of the objects in the remaining $n-2$ boxes such that each of those boxes gets exactly $1$ object. So the number of ways will be $n(n-1){n\choose2}(n-2)!=n!{n\choose2}$

A) If both objects and boxes are indistinguishable, there will be only $1$ way of placing the objects.

B) If the objects are indistinguishable, there will be only $1$ way of placing the objects after choosing the boxes. So there are $n(n-1)={n\choose2}$ ways.


Another method when both are distinguishable:
We first select $2$ objects that will be together in the box containing $2$ objects. There are $n\choose 2$ ways to do this. We now have $1$ "double object", $1$ "empty object" and $n-2$ normal objects. Since these are obviously distinguishable, we need to place $n$ objects in $n$ boxes. So there are $n!$ ways to do this. Therefore our answer will be $n! {n\choose 2}$. This can be done similarly for (B).

$\endgroup$
  • $\begingroup$ Would your answer for (A) also apply to a situation in which the boxes and the objects are distinguishable? $\endgroup$ – Ilia Labkovsky Nov 29 '15 at 22:43
  • 1
    $\begingroup$ @IliaLabkovsky I misread (A) as distinguishable. Let me edit it. $\endgroup$ – shaurya gupta Nov 29 '15 at 22:46
0
$\begingroup$

You dont need partitions of integers, just pigeon-hole principle.

If everything is indistinguishable there is only one way to place it, think that the empty box doesnt exist: n objects in n-1 boxes with no empty box (i.e. at least one object in every box). If you put one object in n-1 boxes you only have one free object more to put over one of these n-1 boxes.

For the second case they are only $(n)_2=n\cdot (n-1)$ variations because the only you change is the box that is empty (the only thing that is distinguishable, think it as colored boxes, so they are n colors) and the box with 2 balls.

$\endgroup$

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.