In a party, there are $n$ guests attending where $3$ guests can seat around a table. What is the maximum number of ways in which they can be seated so that no $2$ guests sit together more than once?
Method $1$: This can be solved by considering a polygon with $n$ sides and connected diagonals (or a fully-connected graph with $n$ nodes) and determining the max. number of triangles possible with no common edge (or max. no. of $3$-edged cyclic paths such that there are no path overlaps). By doing this, I got the answer $n-3$, albeit not with a definite proof.
Method $2$: It can also be proved by finding all the $3$-element subsets of the set $\{1,2,...,n\}$ such that intersection of any $2$ subsets will give an empty set or $1$-element set.
This is what I figured out as of now. But, I am unable to conclusively get an answer for both the methods. How to prove the results and solve for the original question with both of the above methods? Also, I am interested in knowing other interpretations of the problem other than Methods 1&2.
An upper bound
Denote the integer part of a number $x$ by $\{x\}$.
Each guest can be seated in at most $\{\frac{n-1}{2}\}$ combinations. Then $n\{\frac{n-1}{2}\}$ counts each combination three times and so the maximum number of combinations is $\{\frac{n\{\frac{n-1}{2}\}}{3}\}$.
An example, $n=8$
The above formula gives an upper bound of $8$. This can be attained since if we number the guests from $1$ to $8$, the following combinations can be made.
$123, 145, 167$
$825, 847, 863$
$246, 357$.
The upper bound is attained if $n=6k+1$ or $6k+3$
In this case the formula simplifies to $\frac {n(n-1)}{6}$ and T. Skolem has proved that this upper bound is always attained.
Reference - T. Skolem. Some remarks on the triple systems of Steiner. Math. Scand. 6 (1958), 273–280.
https://www.mscand.dk/article/view/10551
The upper bound is attained if $n=6k$ or $6k+2$
In this case the formula simplifies to $\frac {n(n-2)}{6}$ and the proof that this can be attained follows from Skolem's solution for $n+1$ people.
This has $\frac {n(n+1)}{6}$ combinations and each person is in $\frac {n}{2}$ of them. The number of combinations not including a given person is therefore $$\frac {n(n+1)}{6}-\frac {n}{2}=\frac{n(n-2)}{6}.$$