3
$\begingroup$

I've seen questions where it will have you arrange $N$ people at $2$ tables with $N\over 2$ people sitting at them. The answer is usually $$\binom{N} {\frac{N}{2}} \cdot \left(\frac{N}{2} - 1\right)! \cdot \left(\frac{N}{2} - 1\right)!$$ Because with two tables having half the total number of people at each, we know what people are at both tables just by knowing the people at $1$, then we just multiply by all possible arrangements at each.

In a situation where by knowing one tables people we still do not know the others ($3$ tables or more) do we have to multiply by another $\binom{N}{K}$?

For example with $15$ people at $3$ different tables each seating $5$ people, is the number of combinations of seating equal to:

$$\binom{15}{5} \binom{10}{5}(4!)^3$$

And could we take this answer and divide by 3! to eliminate all situations where all arrangements are the same but just at different tables?

$\endgroup$
1
  • $\begingroup$ Thank you for editing my question, I posted on mobile! $\endgroup$ Dec 21, 2015 at 20:08

3 Answers 3

3
$\begingroup$

I think your computation is correct.


Here is an alternate way to approach this problem that I think is a little simpler.


For the two-table case: If you number all the seats, then there are $N!$ ways to seat everyone. Then, we divide by $(N/2)^2$ to account for overcounting due to symmetry at each table (we do not consider rotations of an arrangement at a table to be different). Note that this is the same as your computation.

$$\binom{N}{N/2}(N/2-1)! (N/2-1)! = \frac{N!}{(N/2)! (N/2)!}(N/2-1)! (N/2-1)! = \frac{N!}{(N/2)^2}$$

Note that I assume that the two tables are distinguishable; if they are not, just divide everything by $2$.


For your three-table example, we can do the same thing: there are $15!$ ways to seat everyone if we label all the chairs, and then we need to divide by $5^3$ to account for the symmetry at each table. This gives the same number as your computation.

$$\binom{15}{5} \binom{10}{5} (4!)^3 = \frac{15!}{5! 10!} \frac{10!}{5!5!} (4!)^3 = \frac{15!}{(5!)^3}(4!)^3 = \frac{15!}{5^3}.$$

Again, this computation is if the tables are distinguishable; otherwise, divide everything by $3!$.

$\endgroup$
2
  • $\begingroup$ Did you mean we need to divide by $\color{red}{5}^3$ to account for the symmetry at each table? $\endgroup$ Dec 21, 2015 at 23:10
  • $\begingroup$ @N.F.Taussig Yes, thank you! $\endgroup$
    – angryavian
    Dec 22, 2015 at 1:21
3
$\begingroup$

Using the formula $\dfrac{n!}{n}$ here, rather than $(n-1)!$ for circular seating simplifies enormously.

Permute the $15$ people linearly in $15!$ ways with dividers after every $5$ people for $3$ tables.

Divide by $5^3$ to account for the tables being circular.

Assuming distinguishable tables, you directly arrive at $\dfrac{15!}{5^3}$

And if tables are indistinguishable, just divide the above answer by $3!$

$\endgroup$
1
$\begingroup$

There are two ways in which you can think of this problem.

Problem type 1 - Tables are not labelled table 1,2,3 and all you are worrying about are which people are sitting together on a table i.e. People P1,P2,P3,P4,P5 are together on table 1, People P6,P7,P8,P9,P10 are together on table 2 and P11,P12,P13,P14,P15 are on table 3 is considered as the SAME configuration if these groups of people were seated on tables 2,1,3 instead of tables 1,2,3.

In this case the answer is (15c5)(10c5)(4!)^3 -

  • Select 5 people out of 15 to be seated on a table - 15C5
  • Select 5 from remaining 10 - 10C5
  • Seat these groups of 5 Indpendently on the three circular tables - 4!

Second problem type - It matters what tables they are seated on. Then-

  • Select 5 people out of 15 to be seated on a table - 15C5
  • Select on table for these 5 people - 3C1
  • Select 5 from remaining 10 - 10C5
  • Select 1 table from the remaining 2 for these 5 people - 2C1
  • Seat these groups of 5 Indpendently on the three circular tables - 4! So the answer in this case is (15c5)(3C1)(10c5)(2C1)(4!)^3

There is no need to divide by the 3! in the end. Hope this break-up of the logic helps!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .