0
$\begingroup$

I have a question and a solution. However, I understand how to get to the solution but I'm struggling with how to interpret the solution:

Question:

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 $n_1!\cdot n_2!\cdot n_3!$ 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 𝑘𝑖 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 n_1!k_1!\cdot n_2!k_2!\cdot n_3!k_3!$

I don't understand the answer to the second part: $3!\cdot n_1!k_1!\cdot n_2!k_2!\cdot 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)!$

Solution:

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 $ri$ defined above as the "choose number" to get each term.

$n_i!/(k_i−(n_i-n_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 n_1!/k_1!\cdot n_2!/k_2!\cdot n_3!/k_3!$

How do I interpet this. I know it's not simply the number of permutations that I get after giving the CD's because that would be $(n-k)$. But I'm not sure how else to interpret it?

$\endgroup$
4
  • 1
    $\begingroup$ Your solution is correct if you assume that the $k_i$ CDs to be given away are determined in advance. The statement wants you to choose which $k_i$ CDs to give away as part of the problem. $\endgroup$ Jul 17 '20 at 14:42
  • $\begingroup$ I think I'm being terrible stupid here. I understand what you're saying, it just doesn't fit deeply for me yet. Would you be able to elucidate slightly more please? $\endgroup$
    – hello1994
    Jul 17 '20 at 15:27
  • $\begingroup$ The answer below explains it. First you have to choose which $k_i$ CDs you choose to give away, and then you arrange the remaining ones. $\endgroup$ Jul 17 '20 at 15:29
  • $\begingroup$ What should I do when someone answers my question? $\endgroup$
    – Jan
    Aug 6 '20 at 16:44
0
$\begingroup$

You have $n_i \choose k_i$ different ways to offer your friend for each type of CD and left with $n_i-k_i$ CDs of type $i$, which gives $${n_i \choose k_i}(n_i-k_i)!=\frac{n_i!}{k_i!}.$$

$\endgroup$
3
  • $\begingroup$ Would you be able to elaborate slightly? I'm confused why we're using combinations, when we do care about the position of the objects. I managed to get to the answer above as I posted ^^, through using a new variable r. However, I'm struggling with the intuition of the answer here. $\endgroup$
    – hello1994
    Jul 17 '20 at 15:59
  • $\begingroup$ When you choose $k_i$ type $i$ CDs to give to your friend, the order doesn't matter. For each type of CD, you have $\frac{n_i!}{k_i!}$ possible arrangements, where $\frac{n_i!}{k_i!}$ comes from ${n_i \choose k_i}(n_i-k_i)!$. $\endgroup$ Jul 17 '20 at 16:07
  • $\begingroup$ Toronto thanks! I think things finally struck! The question is asking us the total combinations for which we can give k CD's to our friend and then also the number of ways which we can organise our CD's. Thank you very much! That was 2/3 hours of frustration! $\endgroup$
    – hello1994
    Jul 17 '20 at 16:20

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.