I'm trying to understand the reasoning behind the answer to the following question from an old exam.
Given a set $S_n = \{ 1, 2, 3,\dots n\}$ find how many divisions, $K_n$, there are of the set using only subsets of 1 or 2 members. For example, $\{ \{1,4\}, 6 , 2, \{5,3\} \}$ is one possible division of $S_6$.
Find a recursive definition of $K_n$.
So the first thing I did was to calculate a few terms combinatorially:
$K_1 = \binom{1}{1} = 1$
$K_2 = \binom{2}{2} + \binom{2}{2} = 2$
$K_3 = \binom{3}{3} + \binom{3}{2} = 4$
$K_4 = \binom{4}{4} + \binom{4}{2} + \frac{\binom{4}{2}}{2!} = 10$
$K_5 = \binom{5}{5} + \binom{5}{2} + \frac{\binom{5}{2}\binom{3}{2}}{2!} = 26$
$K_6 = \binom{6}{6} + \binom{6}{2} + \frac{\binom{6}{2}\binom{4}{2}}{2!} + \frac{\binom{6}{2}\binom{4}{2}}{3!} = 76$
And so on. The recursive definition given was $K_n = K_{n-1} + (n-1)\cdot K_{n-2}$
I understand the first half of the definition. You take the number $n$ and add it as a set of 1 to each of the sets in $K_{n-1}$ giving you $K_{n-1}$ new sets in $K_n$. However I'm completely at a loss as to the reasoning behind the second half of the definition.