Lesson 7

For \(k=2\), an explicit formula can be found: \(S(n,2)=2^{n-1}-1\). To derive this, consider one of the two sets containing the element \(n\); each of the remaining \(n-1\) elements can be placed either in the same set or in the other set. This yields \(2^{n-1}\) options, but one of these options places all elements in the set containing \(n\), leaving the other set empty. To account for this, we subtract one. (This is again the method of a distinguished element.)