Trouble understanding the intuition behind permutation problem

Question

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?

Answer 1

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!}.$$

Answer 2

I was happy (and unsurprised) to come across this question on the internet, as it also occurred to me as I was reading this textbook last night.

While the answer provided by toronto is completely correct, I see two deficiencies:

1. arguably it doesn't really provide the "intuition" OP is seeking
2. the idea of combinations is introduced subsequent to this example in the text; the author's path to the answer did not involve combinations.

So what's my take on this?

The rigorous/more mechanical approach to reach the $n_i! / k_i!$ result is to do more or less what OP suggests and plug $(n_i - k_i)$ into the formula for what the author calls "$k$-permutations". Fair enough, but not very intuitive (or satisfying).

Another, more intuitive way to think about it by way of an example: suppose you have 3 CDs of a given genre and you opt to give 1 away. Let's further suppose that the CDs are labeled A, B, and C.

A simple tree diagram shows that there are 6 possible orderings of the remaining 2 CDs (i.e., AB, AC, BA, BC, CA, CB).

In words, you had 3 choices for which CD goes first and 2 choices for which CD came second. There is no third CD to place. A more complicated example, say with 10 CDs of which 3 are given away, works in the same way. Though you end up with 10 - 3 = 7 CDs, there are still 10 possibilities for which CD is placed first, 9 possibilities for which CD is placed second (etc) until you place the seventh CD (for which there will be 4 possibilities).

I hope that's helpful and a bit more "intuitive". Thank you for posting this question!