4
$\begingroup$

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.

  • 1
    @AndréNicolas: Thanks for this (implicit) support for the cause of marriage disregarding questions of gender!2012-02-08

2 Answers 2

5

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.

  • 1
    Thanks for a very clear answer.2012-02-08
0

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$