Given a set of n elements, find the maximum number of ordered k-tuples possible such that every pair of k-tuples has at least one element in common.
For example, if $n=3$ and $k=2$, the set of ordered 2-tuples is: $\{(1,2),(1,3),(2,3),(3,2),(3,1),(2,1)\}$
Here every pair of tuples has at least one common element, hence answer is 6.
Note: $(1,2)$ and $(2,1)$ are different tuples.
Best Answer
As Calvin Lin observed, for every subset of size $k$, there are $k!$ k-tuples. So I'll focus on those subsets first. We'll just have to multiply our answer by $k!$ afterwards.
There are two distinct cases, depending on whether $k$ is greater than $\frac{n}{2}$.
This is because if $k > \frac{n}{2}$, for any given subset of size $k$, it's impossible to construct a second subset of that same size that doesn't contain at least one element of the first subset.
This means the answer for these cases is equal to the total number of subsets, which is $n \choose k$.
Now if $k \le \frac{n}{2}$, I think we need to choose one element to be in all subsets, or it would be possible to construct a second, disjoint subset. So after having picked 1 such element, there are ${n-1}\choose{k-1}$ subsets that can be created containing that element.
So, remembering that we have to multiply by $k!$, the maximum number $m$ of ordered k-tuples is $$ m(n,k)=\cases { \begin{align} {{n}\choose{k}} \cdot & k! & \text{if } k > \tfrac{n}{2}\cr \\ {{n-1}\choose{k-1}} \cdot & k! & \text{if } k \le \tfrac{n}{2} \end{align}} $$