For the lower bound, consider the family
\(\cgF\) of all
\(k\) element subset of
\([n]\) that contain
\(1\text{.}\)
For the upper bound, let
\(\cgF\) be a family of subsets of
\([n]\) satisfying the two constraints. We show that
\(|\cgF|\le\binom{n-1}{k-1}\text{.}\) To accomplish this, we consider a circle in the Euclidean plane with
\(n\) points
\(p_1\text{,}\) \(p_2,\dots,p_n\) equally spaced points around its circumference. Then there are
\(n!\) different ways (one for each permutation
\(\sigma\) of
\([n]\)) to place the integers in
\([n]\) at the points in
\(\{p_1,p_2,\dots,p_n\}\) in one to one manner.
For each permutation
\(\sigma\) of
\([n]\text{,}\) let
\(\cgF(\sigma)\) denote the subfamily of
\(\cgF\) consisting of all sets
\(S\) from
\(\cgF\) whose elements occur in a consecutive block around the circle. Then let
\(t=\sum_\sigma|\cgF(\sigma)|\text{.}\)
Our first claim is that
\(t\le kn!\text{.}\) To prove this, let
\(\sigma\) be a permutation and suppose that
\(|\cgF(\sigma)|=s \ge 1\text{.}\) Then the union of the sets from
\(\cgF(\sigma)\) is a set of points that form a consecutive block of points on the circle. Note that since
\(n\ge 2k\text{,}\) this block does not encompass the entire circle. Accordingly there is a set
\(S\) whose elements are the first
\(k\) in a clockwise sense within this block. Since each other set in
\(\cgF\) represents a clockwise shift of one of more positions, it follows immediately that
\(|\cgF|\le k\text{.}\) Since there are
\(n!\) permutations, the claim follows.
We now claim that for each set
\(S\in\cgF\text{,}\) there are exactly
\(n k!(n-k)!\) permutations
\(\sigma\) for which
\(S\in\cgF(\sigma)\text{.}\) Note that there are
\(n\) positions around the circle and each can be used as the first point in a block of
\(k\) consecutive positions in which the elements of
\(S\) can be placed. Then there are
\(k!\) ways to order the elements of
\(S\) and
\((n-k)!\) ways to order the remaining elements. This proves our claim.
To complete the proof of the theorem, we note that we have
\begin{equation*}
|\cgF| n k! (n-k)!\le t\le k n!,
\end{equation*}
and this implies that \(|\cgF|le\binom{n-1}{k-1}\text{.}\)
