2
$\begingroup$

Sorry for asking so much lately but you guys are the only way to assure me that I'm understanding this homework and not teaching myself the wrong stuff.

So my answers to the following question are the following, I would like to check if they're correct because this whole discrete mathematics makes me unsure about my answers especially that the rules don't always apply:

1- Once a placement of balls has been made, then, since the balls are identical, all we can say is which boxes have received a ball and which have not. In other words, placing the balls has the same effect as simply choosing k of the n boxes. Those boxes that receive a ball are the ones that are chosen, and those that do not receive a ball are not chosen. Hence, in this case we are making unordered selections, that is, forming combinations of size k, taken from the set of n boxes. ${r \choose s} $

2- since the balls are indistinguishable, we can only tell how many balls each box has received. This means making a choice of k of the n boxes, but with the possibility that a box may be chosen more than once. Thus, placing k balls into n boxes, in this case, corresponds to forming an unordered selection, or combination, of size k, taken from the set of n boxes, but with unrestricted repetitions.${s+r-1 \choose s-1}$

3- Putting k distinguishable balls into n boxes, with 1 at most in each bin, amounts to the same thing as making an ordered selection of k of the n boxes, where the balls do the selecting for us. The ball labeled 1 selects the first box, the ball labeled 2 selects the second box, and so on. In other words, distributing k distinguishable balls into n distinguishable boxes, with exclusion, is the same as forming a permutation of size k, taken from the set of n boxes $$\prod_{i=0}^{r-1} (s-i)$$

4- we can think in terms of selecting k of the n boxes. As before, the balls do the selecting for us but this time more than one ball may go into the same box, which means that the same box may be chosen more than once. Therefore, we are still dealing with ordered selections, or permutations, of the boxes, but now with unrestricted repetitions. $$r^s$$

que

$\endgroup$
2
$\begingroup$

In how many ways can $r$ indistinguishable balls be placed into $s$ distinguishable bins if at most one ball is placed into each bin?

If $r > s$, this is impossible. If $r \leq s$, we choose $r$ of the $s$ bins, then place a ball into each bin we have selected. This can be done in $$\binom{s}{r}$$ ways.

You reversed the roles of $r$ and $s$.

In how many ways can $r$ indistinguishable balls be placed into $s$ distinguishable bins if any number of balls can be placed in each bin?

Let $x_k$ be the number of balls placed in the $k$th bin. Then $$x_1 + x_2 + x_3 + \ldots + x_s = r \tag{1}$$ which is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of $s - 1$ addition signs in a row of $r$ ones. For instance, if $r = 12$ and $s = 5$, then $$1 1 1 + 1 1 + + 1 1 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 2$, $x_3 = 0$, $x_4 = 4$, and $x_5 = 3$. The number of solutions of equation 1 is $$\binom{r + s - 1}{s - 1}$$ since we must choose which $s - 1$ of the $r + s - 1$ positions required for $r$ ones and $s - 1$ addition signs will be filled with addition signs.

In how many ways can $r$ distinguishable balls be placed in $s$ distinguishable bins if at most one balls can be placed in each bin?

As above, this is impossible if $r > s$. If $r \leq s$, we can choose $r$ of the $s$ bins into which to place a ball. The $r$ balls can then be arranged in the selected bins in $r!$ orders. Hence, the number of such distributions is $$\binom{s}{r}r! = \frac{s!}{r!(r - s)!} = \frac{s!}{(r - s)!} = s(s - 1)(s - 2) \ldots (s - r + 1)$$ which agrees with your answer, which is sometimes denoted $P(s, r)$, where $P$ stands for permutation.

In how many ways can $r$ distinguishable balls be placed into $s$ distinguishable bins if any number of balls can be placed in each bin.

We have $s$ choices of bin in which to place each of the $r$ balls. Hence, the number of possible arrangements is $s^r$.

Once again, you reversed the roles of $r$ and $s$.

$\endgroup$
  • $\begingroup$ Thanks for pointing that out but in the second case, In how many ways can rr indistinguishable balls be placed into ss distinguishable bins if any number of balls can be placed in each bin? isn't ${r+s-1 \choose s-1}$ is the same as ${s+r-1 \choose s-1}$ $\endgroup$ – user481197 Dec 3 '17 at 17:57
  • 1
    $\begingroup$ My apologies. I missed that. $\endgroup$ – N. F. Taussig Dec 3 '17 at 18:03

Your Answer

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