1

This is a solved problem in "Introduction to Probability", 2nd Edition, by Bertsekas and Tsitsiklis, example 1.29, page 47. I'm having trouble understanding the answer to the second part.

You have $n_1$ classical music CDs, $n_2$ rock music CDs, and $n_3$ country music CDs. In how many different ways can you arrange them so that the CDs of the same type are contiguous?

We break down the problem in two stages, where we first select the order of the CD types, and then the order of the CDs of each type. There are $3!$ ordered sequences of the types of CDs (such as classical/rock/country, rock/country/classical, etc.), and there are $n_1!$ (or $n_2!$ or $n_3!$) permutations of the classical (or rock. or country, respectively) CDs. Thus for each of the $3!$ CD type sequences, there are $n1!\cdot n2!\cdot n3!$ arrangements of CDs. and the desired total number is $3!\cdot n_1!\cdot n_2!\cdot n_3!$

Suppose now that you offer to give $k_i$ out of the $n_i$ CDs of each type i to a friend, where $k_i < n_i, i=1,2,3$. What is the number of all possible arrangements of the CDs that you are left with? The solution is similar, except that the number of $(n_i−k_i)$ - permutations of CDs of type i replaces $n_i!$ in the estimate, so the number of possible arrangements is

$3! \cdot \frac{n_1!}{k_1!} \cdot \frac{n_2!}{k_2!} \cdot \frac{n_3!}{k_3!}$

I don't understand the answer to the second part: $3! \cdot \frac{n_1!}{k_1!} \cdot \frac{n_2!}{k_2!} \cdot \frac{n_3!}{k_3!}$, shouldn't it simply be:

$3! \cdot (n_1 - k_1)! \cdot (n_2 - k_2)! \cdot (n_3 - k_3)! $

Thanks in advance.

AnonymousUser
  • 29

1 Answers1

1

After considering the solution for quite a while, I believe I understand what is being done. I think the problem should have been worded differently, but the intent is as follows.

Introduce a new variable $r_i$ which is defined as $r_i = n_i - k_i$. This is the number of remaining CDs of each genre after you give some to your friend. Then use the formula for the number of permutations of n objects choose r.

$n! / (n - r)!$

Substitute in $r_i$ defined above as the "choose number" to get each term.

$n_i! / (n_i - (n_i - k_i))!$

which simplifies to $n_i! / k_i!$.

Repeat for all the genres and the 3 groups and you get the original answer.

$3! \cdot \frac{n_1!}{k_1!} \cdot \frac{n_2!}{k_2!} \cdot \frac{n_3!}{k_3!}$

AnonymousUser
  • 29