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.
 A: A group of $n$ people arrives at a hotel. We want to  select $0$ or more pairs of them. Paired people will share a room. Unpaired people, if any, will get single rooms.  Let $K_n$ be the number of ways to do this. 
We concentrate on what happens to person $n$. Either (i) (s)he gets a single room, or (ii) (s)he gets paired with someone to share a room.
In case (i), we have $n-1$ people left to deal with, and the number of ways they can be split is by definition $K_{n-1}$.
In case (ii), person $n$'s roommate can be chosen in $n-1$ ways. For each of these ways, the $n-2$ people who remain can by definition be split in $K_{n-2}$ ways. So the number of ways to do a case (ii) splitting is $(n-1)K_{n-2}$.
We have shown that of the $K_n$ ways of splitting $n$ people, $K_{n-1}$ are of type (i), and $(n-1)K_{n-2}$ are of type (ii). That accounts for all the ways of splitting a group of $n$, and therefore
$$K_n=K_{n-1}+(n-1)K_{n-2}.\qquad\qquad(\ast)$$
It is clear that $K_1=1$ and $K_2=2$. Now we can use the recurrence $(\ast)$ to compute, mechanically, $K_3$, $K_4$, $K_5$, and so on.
Remark: We used a strategy that is quite common.  Here is another example. We want to climb an $n$-stair staircase. At any time, we are allowed to go up by a single stair (small step), or by two stairs (big step). In how many different ways can we get to the top?  Let the number of ways be $W_n$.
The $n$-th (and last) stair was either (i) reached from the $(n-1)$-th stair, by taking a small step, or (ii) it was reached directly from the $(n-2)$-th stair, by taking a big step.   
In case (i), we had to first reach stair $n-1$, and by definition this can be done in $W_{n-1}$ ways.
In case (ii), we had to reach stair $n-2$ before
 taking our terminal big step. This can be done in $W_{n-2}$ ways.
It follows that
$$W_n=W_{n-1}+W_{n-2},$$
and we have obtained the familiar Fibonacci recurrence.  
A: 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$
