Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
How many 2-subsets of $\{1,\ldots, n\}$ containing $n$ are there? HTH, AB, martini. –  martini Feb 8 '12 at 7:19
    
There are $n-1$ 2-subsets of $\{1,\dots,n\}$ containing $n$. –  Robert S. Barnes Feb 8 '12 at 7:27
5  
Look at set with $n$ people. Either you make $n$ a bachelor, in which case there are $K_{n-1}$ ways to split the rest. Or you choose one of the $n-1$ people to marry $n$, and then divide up the remaining $n-2$. That immediately yields the recursion. –  André Nicolas Feb 8 '12 at 7:35
    
Thanks, Andre - I get it now. You should write your answer as an answer so that I can upvote it and accept it. –  Robert S. Barnes Feb 8 '12 at 7:42
1  
@AndréNicolas: Thanks for this (implicit) support for the cause of marriage disregarding questions of gender! –  Marc van Leeuwen Feb 8 '12 at 8:19

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
1  
Thanks for a very clear answer. –  Robert S. Barnes Feb 8 '12 at 9:09

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.