Link to Problem: HERE
If a set has \(2n\) elements, show that it has more subsets with \(n\) elements than with any other number of elements.
First, we can refer to Theorem 3.7, the binomial theorem and binomial expansion. That is, given some value \(x\), the coefficients of the binomial expansion from \(0\) to \(x\) will be the number of combinations made of that many elements when selecting from \(x\) elements. Furthermore, the expansion yield’s Pascal’s triangle. The first few lines of the expansion are below:
\((a+b)^0 = 1\)
\((a + b)^1 = a + b\)
\((a + b)^2 = a^2 + 2ab + a^2\)
\((a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^2\)
In Pascal’s Triangle the values grow larger the closer you get to the center of the triangle, or as the number of elements being selected tends towards half of \(x\). This can be seen in the above expansion. It can also be seen that even powered expanions contain an odd number of elements garunteeing a single largest coefficient.
Putting all of these elements together we can state that given a set of \(2n\) elements that the largest subset will contain \(n\) elements. As \(n\) is half of \(2n\) it will sit at the center of Pascal’s Triangle (if \(n\) is odd) or just off center (if \(n\) is even). This location corresponds with the largest coefficient in that row of the Triangle and thus the largest number of subsets.
Let’s do an example. Intuitively, the value made up of \(n\) elements has the most subsets. If the number of elements is too small, then there aren’t enough pieces to make combinations (consider the subset where the number of elements is 0). Conversely, if the number of elements is too large, then we are required to use too many pieces and do not have the flexibility to create new combinations (consider the subset where the number of elements is \(2n\)).
When \(2n=6\) then \(n=3\)
\({6 \choose 0}=\frac{6!}{0!(6-0)!}=1\)
\(\emptyset\)
\({6 \choose 1}=\frac{6!}{1!(6-1)!}=6\)
\(\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}\)
\({6 \choose 2}=\frac{6!}{2!(6-2)!}=15\)
\(\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{1,6\}, \{2,3\}, \{2,4\}, \{2,5\}, \{2,6\}, \{3,4\}, \{3,5\}, \{3,6\}, \{4,5\}, \{4,6\}, \{5,6\}\)
\({6 \choose 3}=\frac{6!}{3!(6-3)!}=20\)
\(\{1,2,3\}, \{1,2,4\}, \{1,2,5\}, \{1,2,6\}, \{1,3,4\}, \{1,3,5\}, \{1,3,6\}, \{1,4,5\}, \{1,4,6\}, \{1,5,6\}, \{2,3,4\}, \{2,3,5\}, \{2,3,6\}, \{2,4,5\}, \{2,4,6\}, \{2,5,6\}, \{3,4,5\}, \{3,4,6\}, \{3,5,6\}, \{4,5,6\}\)
\({6 \choose 4}=\frac{6!}{4!(6-4)!}=15\)
\(\{1,2,3,4\}, \{1,2,3,5\}, \{1,2,3,6\}, \{1,2,4,5\}, \{1,2,4,6\}, \{1,2,5,6\}, \{1,3,4,5\}, \{1,3,4,6\}, \{1,3,5,6\}, \{1,4,5,6\}, \{2,3,4,5\}, \{2,3,4,6\}, \{2,3,5,6\}, \{2,4,5,6\}, \{3,4,5,6\}\)
\({6 \choose 5}=\frac{6!}{5!(6-5)!}=6\)
\(\{1,2,3,4,5\}, \{1,2,3,4,6\}, \{1,2,3,5,6\}, \{1,2,4,5,6\}, \{1,3,4,5,6\}, \{2,3,4,5,6\}\)
\({6 \choose 6}=\frac{6!}{6!(6-6)!}=1\)
\(\{1,2,3,4,5,6\}\)
choose(6, 0:6)## [1] 1 6 15 20 15 6 1