4
$\begingroup$

The answer is, according to the book: $(m-1)!\cdot \binom{m+r-1}{r}$
I get why this is true. You arrange $m$ people in their seats in $(m-1)!$ ways and then you put $r$ empty spots inbetween them.

I was thinking - choose $m$ seats out of $m+r$ to put the people on => $\binom{m+r}{m}$
Arrange them once you've chosen the seats $\to (m-1)!$
So in total: $\binom{m+r}{m} \cdot (m-1)!$

This is obviously not true. What's wrong with the way I'm thinking?

$\endgroup$
  • 1
    $\begingroup$ What is $CC_m^r$? And why can one arrange $m$ people in their seats in $(m-1)!$ ways and not in $m!$ ways? Are arrangements that differ only by a rotation considered equal? $\endgroup$ – Daniel Fischer Feb 11 '17 at 20:58
  • $\begingroup$ @DanielFischer Uh I just googled CC and seems like no one is actually using this. $CC_{r}^{m}$ is the same as placing $r$ balls in $m$ boxes. Also can you explain the second part of your answer? $\endgroup$ – SomeoneWithAQuestion Feb 11 '17 at 21:03
  • 1
    $\begingroup$ When I have $m$ chairs and $m$ people, there are $m!$ ways to place one person on each chair. But when one places the chairs around a round table, it makes sense to not distinguish between two placings that can be transformed into each other by moving everybody $k$ chairs to the right (or, in the other direction, to the left). I'm asking whether that identification is made here. $\endgroup$ – Daniel Fischer Feb 11 '17 at 21:09
  • $\begingroup$ Yeah, arrangements that differ only by a rotation are considered equal, fromt he way I understand it. @DanielFischer $\endgroup$ – SomeoneWithAQuestion Feb 11 '17 at 21:52
  • $\begingroup$ Okay. So you always start with Elizabeth (makes sense, she's the queen after all). That means that effectively you have only $m-1$ people to place on $m+r-1$ chairs. Then choosing the $r$ chairs to be left empty gives you $\binom{m+r-1}{r}$ choices, and for each selection of empty chairs you have $(m-1)!$ ways to place Charles, Camilla, William, Kate etc. on the remaining chairs. $\endgroup$ – Daniel Fischer Feb 11 '17 at 21:56
1
$\begingroup$

Looks like seats are identical.

So, first place a person any seat. this will act as a reference point. This can be done only in one way. Then seat remaining $(m-1)$ persons in remaining $(m+r-1)$ seats and this can be done in $\dbinom{m+r-1}{m-1}$ ways. Considering arrangements, multiply with $(m-1)!$.

So,

$\dbinom{m+r-1}{m-1} \times (m-1)!$ ways

This is same as the answer given in the book because

$\dbinom{m+r-1}{m-1}(m-1)!=\dbinom{m+r-1}{r}(m-1)!$

$\endgroup$
  • $\begingroup$ So you're choosing the position for the first person, then arranging the others. The other answer stated that my solution over counts because you can rotate one solution and get another one. Why isn't it true for your solution as well? $\endgroup$ – SomeoneWithAQuestion Feb 11 '17 at 21:49
  • $\begingroup$ once we fix the reference point, then we can consider the rest in the same way we consider the arrangements in a row $\endgroup$ – Kiran Feb 11 '17 at 21:55
1
$\begingroup$

With your way, you over count. If one group of $m$ seats that you choose, on the table, is a rotated version of another group of $m$, then you can get the same order, by just rotating them.

$\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.