# Yet another combinatoric problem

we have the following question for homework:

N of the knights of the round table are having dinner.
In how many ways can they sit around the table?
What if Jack won't sit next to John and the queen -
how many possible ways exist now?


The first question for quite easy - (n-1)!. I'm struggling with the second one: If Jack refuses to sit next to one of them I can count them as one, calculate and then subtract it from the total number of permutations. Its a little harder when he refuses to sit next to two people, because they CAN sit next to each other.

Also, how can I think of it in term of equivalence classes? I am trying to adopt this way of thinking so a hint in that direction would be nice. Thanks in advance!

• @Angela Richardson: With small typo fix, the solution under first condition (neither next to Jack) is efficient, correct. It solves the problem under the standard interpretation that being the Queen's right-hand man is not the same as being her left-hand man. For second interpretation (want to avoid sitting between) answer is fine if reversal of order means "the same", otherwise need $(N-1)!-2(N-3)!$. – André Nicolas Nov 29 '11 at 18:01

Have you done inclusion-exclusion? You count the total number of ways to seat the $N$ people (I guess the Queen counts as a knight for this problem), subtract the one(s) where Jack sits next to John, subtract the ones where Jack sits next to the Queen, and then add back in the ones where Jack sits next to both John and the Queen. (edited typo)

In the first part of the problem, it says N of the knights are having dinner. Given there are M total knights, and K = M+1 chairs at the table (one extra for the queen). This problem becomes, how many ways can you select N+1 seats from K total seats (combination) X how many ways you can arrange N knights and 1 queen (permutation).

This is C(K,N+1) x (N+1)! => (K!/((N+1)!x(K-N-1)!)) x (N+1)! The (N+1)! term cancels out, giving: K! / (K-N-1)!

The second part's result is a subset of the first, so let J = K! / (K-N-1)! The number of ways 3 people can be arranged (permutation) is 3!. The number of ways to pick 3 contiguous seats from K chairs is K. Therefore, the number of ways to seat 3 people contiguously in K chairs is K x 3!

Therefore: J-(K x 3!) = (K! / (K-N-1)!) - (K x 3!)

• So under your interpretation, we first have to choose which $N$ knights are dining, out of an unspecified total of $M$ knights, and then for some reason we assume the number of chairs at the table is one more than the total number of knights, and a-b-empty-c counts as different from a-empty-b-c. I doubt that the person posing the problem had any of that in mind. – Gerry Myerson Nov 29 '11 at 23:15
• Well it is combinatorics yes? – Roger Johnson Nov 29 '11 at 23:30
• It is combinatorics, to which you have added a fair bit of mind-reading. – Gerry Myerson Nov 30 '11 at 0:40
• OK - I'm sorry if I offended you somehow. I was just trying to apply a bit of rigor to the problem. It's been a long time since my college Combinatorics class. I stated K chairs = M + 1 (for the queen). You did cause me to reconsider the queen and catch an error, thank you for that. I wish you would consider moving the solution forward by demonstrating via proof how your solution is correct, where mine is not. Also, I guess it is possible, that stating M total knights could add noise and yield a less than elegant solution. A default interpretation could certainly be the case M=N. – Roger Johnson Nov 30 '11 at 6:08
• Not offended, just mystified. Our solutions differ because our interpretations differ, and there is no way to prove that my interpretation is correct and yours is not, other than to get OP (or OP's teacher) to tell us what was intended. yotamoo, you still there? – Gerry Myerson Nov 30 '11 at 12:13