Thoughts: Upper Bound
Imagine person 1 keeps a list of people they've sat with before. The list starts with 35 people on it, and each time they sit, they cross 3 names off. After 11 seatings, they will have crossed out 33 names, and so they can't sit down again without having to sit with someone they already crossed off.
In general, with (nk - 1) others, they will be able to sit \(\lfloor\dfrac{n \cdot k - 1}{k - 1}\rfloor\) times.
A different way at the upper bound is to consider all possible pairs of students who might sit together. There are 36 students, so there are \(\dbinom{36}{2} = 630\) possible pairs. If 4 students sit together at a table, that's the same as \(\dbinom{4}{2} = 6\) pairs of students who can't sit together again per table. With 9 tables, we have \(6\cdot9=54\) total pairs used up with each seating. Therefore, we can only create \(\lfloor\dfrac{630}{54}\rfloor=11\) seatings before we run out of pairs of students who haven't sat together.
In general, with n tables of k students each there are nk students total. This gives \(\dbinom{nk}{2} = \dfrac{nk\cdot(nk+1)}{2}\) pairs, and a total of \(\dbinom{k}{2} = \dfrac{k\cdot(k+1)}{2}\) pairs used per seating. This gives an upper bound of \(\lfloor\dfrac{n(nk+1)}{k+1}\rfloor\) seatings.
A Graph Theoretic Setting
Let |S| = nk, the total number of students. The complete graph on |S| nodes represents all possible pairs of students who could sit together. Define a seating as the disjoint union of n complete subgraphs on k nodes. We are looking for the maximum number of edge disjoint seatings.
In the diagram to the left you see a \(K_4\) subgraph of \(K_12\). This represents 4 students sitting at a table. Adding two more disconnected \(K_4\) subgraphs will yield one seating since we will have sat all 12 students in tables of 4.A Construction For All 1-factors
When k = 2, we are sitting students in pairs. In the graph setting, one seating is a complete matching (also called a 1-factor. As you can see to the right, there are 15 unique complete matchings for \(K_6\).
We came up with a simple enumeration of all the 1-factors for \(K_{2n}\). Label your nodes 1 to 2n. Every node must be matched once. There are (2n-1) other nodes that node 1 can match with. For each of these possibilities, proceed to the next highest unmached node, and match it with each of the (2n-3) unmatched nodes (2n-3 because there were 2n-1, and we just matched 2 nodes). For each of these possibilities, proceed to the next unmached node, and match it with each of the (2n-5) unmached nodes and so on until you have exhausted the nodes.
For n = 4 (that is, \(K_8\)), this process gives \(7 \cdot 5 \cdot 3 \cdot 1 = 105\) matchings. For n = 3 (\(K_6\)) it gives \(5 \cdot 3 \cdot 1 = 15\) matchings (as illustrated). In general, for \(K_{2n}\), the number of matchings is \(1 \cdot 3 \cdot 5 \cdot 7 ... \cdot (2n-1)\), which Erin noticed is equal to \(\dfrac{(2n+2)!}{(n+1)!\cdot 2^{n+1}}\)
A Simple Counting Argument For Unique Seatings
Given n tables of k students each, here is a simple counting argument for the number of unique seatings (where a student's placement within a group doesn't matter, and the tables are indistinguishable). Start with all (nk)! permutations of students. Divide by the k! equivalent permutations of students within each of the n tables. Divide by the n! equivalent permutations of tables. This gives the number of unique seatings as \(\dfrac{(nk)!}{{k!}^n \cdot n!}\).
For n = 3 and k = 2, this gives \(\dfrac{6!}{{2!}^3 \cdot 3!} = 15\) seatings, as expected. For the original problem of n = 9 and k = 4, this gives \(\dfrac{36!}{{4!}^9 \cdot 9!} = 388035036597427985390625\) or approximately \(3.88x10^{23}\).
No comments:
Post a Comment