2
$\begingroup$

Consider this equation:

$x_1 + x_2 + \cdots + x_k = n$

with these following constraints:

$x_i ≥ 0;\; i = 1,2,\ldots, k$

How would I go about formulating each of the following problems as a variation of the above problem? I have the answer key, but it's one of those useless keys that just give an answer with no explanation or steps shown so I am completely stuck.

  1. Determine the number of ways to select k objects with replacements from a set of n objects.

Answer: $x_1 + x_2 + \cdots + x_n = k;$ $\;x_i ≥ 0; i = 1; 2; \ldots; n$.

(b) Determine the number of ways to place $n$ nondistinguisable balls in $k$ boxes.

Answer: $x_1 + x_2 + \cdots + x_k = n;$ $\;x_i ≥ 0; i = 1; 2; \ldots; k$.

Can anyone explain to me how to get those answers?

$\endgroup$

1 Answer 1

1
$\begingroup$

For $1$:
$x_i$ is the number of times you selected object $i$.
For an example: Let's say we have $4$ objects, and we want to select $3$ (with replacement). We can:

  • Select object $1$ three times, and all other objects $0$ times. ($x_1=3,\; x_2=x_3=x_4=0$)
  • Select object $1$ two times, object 2 once, and all others $0$ times. ($x_1=2,\; x_2=1,\;x_3=x_4=0$)
  • Etc.

For $2$:
$x_i$ is the number of balls in the $i$-th box. Let's say we have 2 boxes, and 2 balls. Then, we can:

  • Place both balls in box $1$ ($x_1 = 2,\;x_2 = 0$)
  • Place one ball in each box ($x_1=x_2 = 1$)
  • Place both balls in box $2$ ($x_1 = 0,\;x_2=0$)
$\endgroup$
4
  • $\begingroup$ Can you go into more detail here? $\endgroup$
    – Ash
    May 25, 2014 at 19:04
  • $\begingroup$ @Jack It's hard to enumerate all possibilities, because the number quickly gets large. But, does this help explain where the numbers are coming from? (edited post) $\endgroup$
    – apnorton
    May 25, 2014 at 19:10
  • $\begingroup$ Thanks, and one last question, how do we know to set 1) for example to = k and not = n? For answer one, why isn't it x1+x2+⋯+xk=n? $\endgroup$
    – Ash
    May 25, 2014 at 19:16
  • $\begingroup$ @Jack I don't know exactly why I know that (practice has replaced conscious thought with intuition, for better or for worse), but I think it is probably because $k$ in problem $1$ represents the number of things we're selecting and not the total number of things. $\endgroup$
    – apnorton
    May 25, 2014 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .