Count the number of divisions of a set recursively 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.

Let's take a stab at the recurrence... define the exponential generating function $\hat{K}(z) = \sum_{n \ge 0} K_n \frac{z^n}{n!}$ (to compensate for the $n - 1$ factor), and write:
$$
K_{n + 1} = K_n + n K_{n - 1} \qquad K_0 = K_1 = 1
$$
Using properties of exponential generating functions:
$$
\hat{K}'(z) = \hat{K}(z) + z \frac{d}{dz} \int \hat{K}(z) dz
$$
Thus:
$$
\int_1^\hat{K} \frac{d \hat{K}'}{\hat{K}} = \int_0^z (1 + z) dz
$$
and so:
$$
\hat{K}(z) = e^{z + z^2/2}
$$
so that $K_n = 1, 1, 2, 4, 5, \ldots$
