3
$\begingroup$

In how many ways can we seat 100 people around 20 different circular tables in such a way that there are five people per table?

Am I right in assuming that we're only considering unique situations?

For example, if we take 2 people at 2 tables with 1 per table. Then we'd have [A][B] and [B][A] which is actually only 1 arrangement. $\frac{C(2,1)}{2} = \frac{2}{2} = 1$

Or 4 people, 2 tables, 2 per {[AB] [CD]} {[AC] [BD]} {[AD] [BC]} which is three arrangements since we don't count [B,A], [C,A], [D,A], [D,C], [D,B] or [B,C] $\frac{C(4,2)}{2} = \frac{6}{2} = 3$

Therefore, the formula I got was $\frac{C(totalPeople,peoplePerTable)}{numberOfTables}$

For 100 people at 20 tables with 5 per table.

We have $\frac{C(100,5)}{20} = 3,764,376$ possibilities

$\endgroup$
5
$\begingroup$

There are $100!$ ways to line up the people. Take the first $5$ and seat them around the first table in order. Do the same for the second $5$ and the second table. Continue until you’ve seated all $100$. If the tables are individually identified, and each of the $20$ tables has a designated head seat, each of these $100!$ seatings counts as a different arrangement. If the tables are individually identified, but seatings that are equivalent under a rotation of the table are not considered distinct, then each seating at each table has been counted $5$ times, once for each possible location of a head seat, and there are therefore only $\dfrac{100!}{5^{20}}$ distinct arrangements.

You appear to be assuming, however, that the tables are not individually identified and that rotationally equivalent arrangements at a table are not distinguished. In that case each distinct arrangement has been counted $20!$ times in the figure $\dfrac{100!}{5^{20}}$, once for each of the $20!$ permutations of the tables, so there are only $\dfrac{100!}{5^{20}20!}$ distinct arrangements. This is a bit over $4\times10^{125}$.

$\endgroup$
0
$\begingroup$

This is actually an instance of a type of problem that can be solved by symbolic combinatorics for labelled counting. Let $\mathcal{Z}$ be the singleton class and $\mathcal{T}$ the set of all seating arrangements as required. This gives the combinatorial class specification $$ \mathcal{T}= \mathfrak{P}_{20}(\mathfrak{C}_5(\mathcal{Z}))$$ where $\mathfrak{C}$ is the cycle operator and $\mathfrak{P}$ the set operator.

Translating to exponential generating functions, this gives $$ T(z) = \frac{(z^5/5)^{20}}{20!}.$$

The result is now given by (remember that we are using an EGF) $$100! [z^{100}] T(z) = 100! [z^{100}] \frac{z^{100}}{5^{20} 20!} = \frac{100!}{5^{20} 20!},$$ as obtained in the first answer.

I do believe it is useful to employ the symbolic method even in a simple case like this in order to pick up the mechanics and be able to apply it to more complex problems in the future.

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