Calculate unique combinations for unique guests per table contraint

Question

I'm working on this application that generates a table layout based on some criteria. The criteria consists of these things

• A list of guests
• The amount of tables
• The amount of dinner courses
• The type of algorithm
  1. Place guests at table at random
  2. Place guests at a unqiue table each course
  3. Place guests at a table with other unmet/unique guests each course

Right now I'm looking for the formula to calculate the constraint for the last algorithm (nr 3). After spending some time googling I found a formula for combinations/permutations, though it only works when the maximum amount of guest per table is less then three.

$$ \frac{n!}{r!(n − r)!} $$

In my cause I use r as the amount of guests and n as the amount of guest per table
( e.g. ceil( guest count / table count ) )

For example, With 4 guests and 3 tables, n=4 and r=2, the formula returns 6. Which matches my calculations

12 23 34
13 24
14

Same for 6 guests and 3 tables, n=6 and r=2, the formula returns 15. This also matches the calculations

12 23 34 45 56
13 24 35 46
14 25 36
15 26
16

But when the guests per table increases, the formula returns unwanted results. For example, n=7 and r=3, returns 35. But my calculation comes down to 7 combinations

123 246 356
145 257 347
167

I was hoping if someone could help me find or alter this formula so it matches these three calculations. Thus honoring the constraint:
maximum amount of combinations where each number can only be returned once in combination with the other numbers.

Thank you for your time

Answer 1

Let $n\ge r\ge 2$. Denote by $f(n,r)$ the maximum amount of combinations of $r$ numbers from $n$ numbers where each number can only be returned once in combination with the other numbers.

Given a required system of $f(n,r)$ combinations, let $N$ be a total number of pairs of numbers participated in some of these combinations. Each of combinations of the system has ${r\choose 2}$ pairs, and all pairs are mutually distinct, so $N={r\choose 2} f(n,r)$. On the other hand, there can be at most ${n\choose 2}$ pairs in total, so $f(n,r)\le \frac {n(n-1)}{r(r-1)}.$

Ot the other hand, if there exists a Steiner system $S(2,r,n) $ then it yields an exact answer with $f(n,r)=\frac {n(n-1)}{r(r-1)}$. In particular, we have it when $n$ has a form $6k+1$ or $6k+3$ for some $k$ and $r=3$, or $n=q^2$ and $r=q$ or $n=q^2+q+1$ and $r=q+1$, where $q$ is a power of a prime number (we still cannot construct respective Steiner systems for other $q$). Also see pictures for $n=7$ and $r=3$ and $n=13$ and $r=4$ here. Finally I remark that the above examples provide an asymptotic lower bound for $f(r^2,r)$.