2
$\begingroup$

The problem given is in the title:

In how many ways can $20$ persons be seated round a table if there are $9$ chairs?

I tried solving it as follows:

I can fix one person to one of $9$ chairs. I can select any one of $20$ for this. Now I need to permute $8$ out of remaining $19$. So total count $=20\times {}^{19}P_8=609493224800$

But given solution was:

We can select $9$ out of $20$ person in ${}^{20}C_9$ ways. Those $9$ persons can seat around circular table in $8!$ ways. So total count ${}^{20}C_9\times 8!=6772147200$

So where did I made mistake in my approach?

$\endgroup$
  • $\begingroup$ Sorry, I dont quite understand your 'solution'. You can't 'fix' anyone to a chair due to the rotational equivalence: 123 is the same as 231 and 312 $\endgroup$ – Alex Sep 17 '19 at 5:53
  • $\begingroup$ Number of circular permutations for $n$ people is $(n-1)!$. We can interpret this as fixing "any" person to "any" chair and then permuting rest of $(n-1)!$. For example, if $n=5$, We fix 1st person. Then two (out of 4!) different permutations of remaining 4 will be: [1,2,3,4,5], [1,2,3,5,4]. First "any" means we still get [1,2,3,4,5] and [1,2,3,5,4] even if we fix 2nd person instead of 1st. Second "any" means [1,2,3,4,5] is same as [5,1,2,3,4]. (Thats how I interpret fix and tried same in above my solution) $\endgroup$ – anir Sep 18 '19 at 4:53
2
$\begingroup$

For each way:

One time you fix me (for example) and then sit other,

another time fix yourself and then sit other,

and so on for every of 9 person,

so you count every way 9 times!

Also after fixing first person,

sitting others from left of first person to his right isn't different from inverse direction,

so doesn't make new way,

but you count it!

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

In my solution to problem, I said:

I can fix one person to one of 9 chairs. I can select any one of 20 for this.

But this counts same arrangement multiple times. For simple example, consider we need to choose 3 people out 5 to sit around table. First I fix Person 1 at certain chair and then permute 2 out of remaining 4. This will take following form [1,2,3], [1,3,2], [1,3,4], [1,4,3] an so on. Now consider I fix Person 2 instead of person 1 and permute 2 out of remaining 4. This will give me [2,1,3], [2,3,1], [2,3,4], [2,4,3] and so on. Note that [1,2,3] and [2,3,1] are same on round table. If we would have fixed 3rd person, then [3,1,2] will be same as above two. Thats how my approach was counting certain arrangements more than once.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Since they sit round the table, they can be rotated without changing the order of seatings, the number of such rotations is equal to the number of people. Each such rotation corresponds to the same seating. Hence, $8!=\frac{9!}{9}$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ that's not the issue in his solution; he still "permuted" 8 $\endgroup$ – Saketh Malyala Sep 17 '19 at 5:50

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.