Problem:
Let be the largest possible number of elements in a 2-separable -configuration of a set with elements (). Find a closed-form expression (i.e. an expression not involving any sums or products with a variable number of terms) for .
Solution
Solution:
First, a lemma: For any with , . (By convention, we set when .)
Proof: We may assume , since otherwise we can replace with . Now we prove the result by induction on . For the base case, if , then the lemma states that , which is trivial. If the lemma holds for some , then by the familiar identity,
(since ), so , giving the induction step. The lemma follows.
Now suppose that the elements of are labeled such that elements of the set receive the number 1 and elements receive the number 2. Then the -configuration can include all -element subsets of except those contained among the elements numbered 1 or the elements numbered 2. Thus, we have at most elements in the -configuration, and by the lemma, this is at most
On the other hand, we can achieve via the recipe above—take all the -element subsets of , except those contained entirely within the first elements or entirely within the last elements. Then, labeling the first elements with the number 1 and the last elements with the number 2 shows that the configuration is 2-separable. So,