1
$\begingroup$

I have a homework assignment to find a recursive function for $k(n)$ where $k(n)$ is the number of ways to split the set $\{1,2,3,4....n\}$ while not having any subset contain more than two elements. for example $\{\{1,2\},\{3\},\{4\},\{5,6\}\}$ is an acceptable split of $k(6)$

I can't seem to figure out the recursive function for this.

Can someone please help me out?

Thanks.

1 Answers 1

5

Either $n$ goes in a one-element set or a two-element set. In the first case, how many ways can you partition the other $n-1$ elements? In the second case, how many possibilities are there for what the remaining $n-2$ elements are, and how many ways are there of partitioning them?

  • 0
    Yep I think that's right - thanks for your help2011-10-09