1
$\begingroup$

How to distribute $r$ different objects in $n$ different bins? Each bin can hold one object.

The book says that the the answer is:

$$n(n-1)(n-2)(n-3)...(n-r+1)$$

I guess this is being done looking at the choices of each object.

Why can't we look at the problem bin by bin instead like this $$r(r-1)(r-2)....(r-n+1)$$ I know I am missing a trivial point.

In general how do you select the thing whose point of view is to be taken in account?

$\endgroup$
1
$\begingroup$

It helps to look at extreme cases.

Suppose we have $n$ bins and one object. There are $n$ ways we can match an object with a bin since we have $n$ choices of bin in which we can place the object. The alternative formula you considered would match all $n$ bins with one object, which would be impractical.

We wish to match objects with bins. Since only one object can be placed in each bin, we should get zero if there are more objects than bins. However, if we choose objects rather than bins we will get $0$ whenever there are more bins than objects, which is clearly false for the case of one object and two bins. Hence, we must choose the bins in which we place the objects.

The formula $$P(n, k) = n(n - 1)(n - 2) \ldots (n - k + 1) = \frac{n(n - 1)(n - 2) \ldots (n - k + 1)(n - k)!}{k!} = \frac{n!}{(n - k)!}$$ comes from the observation that we have $n$ bins in which we can place the first object, $n - 1$ remaining bins in which we can place the second object, and so forth until we have $n - (k - 1) = n - k + 1$ remaining bins in which we can place the $k$th object. Notice that when $k \geq n + 1$, the product reduces to zero, as expected.

$\endgroup$
  • $\begingroup$ I understand your point. But where was i going wrong??? $\endgroup$ – Harshit Joshi Apr 27 '18 at 14:12
  • $\begingroup$ Your formula gives zero whenever there are more bins than objects, but we should only get zero when there are more objects than bins. $\endgroup$ – N. F. Taussig Apr 27 '18 at 14:17
  • $\begingroup$ I understand that the formula is wrong. $\endgroup$ – Harshit Joshi Apr 27 '18 at 14:18
  • $\begingroup$ I have revised my answer. Let me know if I have addressed your question. $\endgroup$ – N. F. Taussig Apr 27 '18 at 14:30
  • $\begingroup$ Yes this addresses my question. Actually i am struggling with this chapter as I always make a trivial mistake. Do you have any general suggestions about solving any combinatorics problem? $\endgroup$ – Harshit Joshi Apr 27 '18 at 14:32
0
$\begingroup$

If we look at the problem bin by bin then the question is something similar like this:

  • Given $n$ boxes, how many ways are there to put $n$ boxes on $r$ objects if each box can only be placed on one object?

  • Otherwise, this question is similar to: Given $n$ different boxes, how many ways are there to put $r$ objects on each box if each object can only be placed on one box?

We can generalize it like this:

If we need to distribute $r$ objects into $n$ groups, each group hold exactly one object (not each object must be in exactly one group, which is not possible because there may be some leftover objects) then the answer is $n(n-1)(n-2)(n-3)...(n-r+1)$.

$\endgroup$
0
$\begingroup$

You can think of two steps: first select $r$ objects in $r!$ ways, then put them into $n$ boxes in ${n\choose r}$ ways. Hence: $$r!\cdot {n\choose r}=r!\cdot \frac{n!}{r!(n-r)!}=(n-r+1)(n-r+2)\cdots (n-1)n.$$

$\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.