0
$\begingroup$

pg. 20 of The Art of Enumerative Combinatorics, George E. Martin.

How many ways are there to select 4 knights from 15 knights sitting at a round table if no adjacent knights can be chosen?

On the next page he generalizes the problem to the following:

Suppose there are k knights and that q are to be chosen for the quest with no adjacent knights chosen. If we calculate the number of quests that have Lancelot as a member and multiply this number by k, then this product equals q times the number that we are seeking.

I don't understand why this last statement is true. I understand how to get the number of quests with lucky Lancelot as a member ${k-q-1} \choose{q-1}$ but why should this number multiplied by k equal q times the total number of quests? I do not know how to visualize the second part of the problem.

$\endgroup$
  • $\begingroup$ You should be dividing by $q$ for the number of quests. $\endgroup$ – Ross Millikan Nov 12 '18 at 15:08
1
$\begingroup$

Once you know the number of combinations that include Lancelot, imagine sending each combination (both those including Lancelot and those that do not) out once. By symmetry, each knight is sent out the same number of times, so the total number of trips is $k{k-q-1 \choose q-1}$. On each quest there are $q$ knights, so there are $\frac kq{k-q-1 \choose q-1}$ quests.

$\endgroup$

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.