Wikipedia:Reference desk/Archives/Mathematics/2023 February 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 19

permutations (table seating)

Hi,

I am looking for the name of the branch of mathematics that will allow me to solve the following "problem."

I want the guests at my dinner party to all have a chance to meet each other. There are g guests sitting at t tables eating c courses. After each course, some will switch to a different table. I want to do this in a way that the maximum number of people will get to meet each other in small groups. More precisely, for given g, t and c I want the permutations that leave the fewest pairs of guests NOT having spoken to each other.

I have some grounding in mathematics, but in a rather applied approach - during my physics education. There is probably a whole field of study devoted to this sort of thing and it would help me a lot to know the name, so that I can tune my Google search a bit better.

Thanks,

GilHamiltonTheArm (talk) 17:05, 19 February 2023 (UTC)

The general topic is combinatorics. AndrewWTaylor (talk) 19:47, 19 February 2023 (UTC)

In statistics when testing out for instance different plants against different treatmnts this sort of thing happens in block design. Steiner system is possibly more what you want and Kirkman's schoolgirl problem is a simple variant which forms a nice puzzle. NadVolum (talk) 20:28, 19 February 2023 (UTC)

GilHamiltonTheArm: There are ${\frac {g(g-1)}{2}}$ pairs of guests. Each guest will meet the ${\frac {g}{t}}-1$ other guests at their table for each course. So based on first glance the fewest pairs of guests $p$ that have not met each other would be something like $p\geq {\frac {g(g-1)-({\frac {g}{t}}-1)c}{2}}$. Note that if $c$ is high enough such that each guest really does have the opportunity to meet every other guest, then many pairings of guests would meet again, and $p$ would be larger than the other side of the inequality. Sungodtemple (talk • contribs) 20:55, 19 February 2023 (UTC)

With four guests (Alice, Bob, Charlie, Debbie), and two tables, each seating two guests, each of the six pairs can meet in three rounds: (1) Alice+Bob, Charlie+Debbie; (2) Alice+Charlie, Bob+Debbie; (3) Alice+Debbie, Bob+Charlie. Using $g=4,t=2,c=3,$ we should find $p=0,$ but the above formula results in

$p\geq {\frac {4(4-1)-({\frac {4}{2}}-1)3}{2}}=4.5\,.$

 --Lambiam 14:05, 20 February 2023 (UTC)

A parameter missing from the question is the seating capacity of the tables. (If there is no capacity constraint, just seat all guests at the same table.) Do the tables all have the same capacity? Also, is this question out of theoretical interest, or do you need these permutations with an eye to actual application? (In the latter case a near-optimal solution is better than none.)  --Lambiam 09:58, 20 February 2023 (UTC)

Since, for the purpose of getting pairs of guests sitting at the same table, neither the identity of the tables matters, nor the arrangement around a given table, the seating at each course corresponds to a partition of the set of guests, constrained by the number of tables and their seating capacities. The term partition may be helpful in refining the search. If similar problems have been studied, it is more likely to have been the problem of determining the least number of partitions such that all pairs co-occur at least once in a cell of one of the partitions.  --Lambiam 14:44, 20 February 2023 (UTC)

Considering the problem of finding the smallest set of partitions such that all guests will meet, and restricting one's attention to the situation that the number of guests is an integral multiple of the seating capacity of the tables, one can look at two special cases:

1. The tables all seat two guests. I found $g=2\mapsto c=1;g=4\mapsto c=3;g=6\mapsto c=5.$ One might be tempted to guess that in general $c=g-1.$
2. There are just two tables. For this case I found $g=4\mapsto c=3;g=6\mapsto c=4;g=8\mapsto c=3.$ This surprised me. I had expected $c$ to increase with $g.$

 --Lambiam 22:10, 20 February 2023 (UTC)

I would not be surprised to learn that graph theory has terminology applicable to exactly this problem. —Tamfang (talk) 04:58, 22 February 2023 (UTC)

This is the closest I can come. Assuming $g$ is an integral multiple of $t$ and denoting each table's seating capacity by $s=g/t,$ a seating is a vertex cover of the complete graph $K_{g}$ by the disjoint union of $t$ cliques, each being a copy of $K_{s}.$ The union of how many seatings fully covers $K_{g},$ including the edges?  --Lambiam 07:57, 22 February 2023 (UTC)