# What is the largest number of k-element subsets of a given n-element set S such that…

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?

• I can do the case k=2 ;-) – Mike F May 28 '13 at 22:34

To every $k-$subset, associate the $k \choose 2$ subsets of pairs of elements. From the conditions in the question, every 2 $k-$subsets must have distinct pairs, hence there are at most $\frac{n\choose2} {k \choose 2} = \frac{n(n-1)}{k(k-1)}$ such sets. Note that this need not be an integer.
To get much better bounds, you will need to start to know what $n$ and $k$ are. For example, with $k=2$, we can get $\frac {n(n-1)}{2(1) }$ subsets easily. With $k> \frac{n}{2}$, we can only get 1 set, even though the above gives us a bound of $\approx 4$ if $k$ is close to $\frac{n}{2}$, and a bound of 1 if $k$ is close to $n$.