I met a problem which can be formulated as set partition.

Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set partition operations. Each set partition operation *randomly* partitions a set, say $A$, into two *non-empty* subsets, $B$ and $C$, such that $A=B\cup C$ and $B\cap C=\emptyset$. I want to calculate or approximate the expectation of partition time, $E(n)$, to separate $s_1$ and $s_2$.

Let see two simple cases:

(1) $n=2$:

In this case, $S=\{s_1,s_2\}$. The only feasible partition will separate $S=\{s_1,s_2\}$ as $\{s_1\}$ and $\{s_2\}$. So, $E(2) = 1$.

(2) $n=3$:

In this case, $S=\{s_1,s_2,s_3\}$. There are two situations:

(a) if the first partition is $\{s_1\},\{s_2,s_3\}$ or $\{s_2\},\{s_1,s_3\}$, then 1 partition is ok!

(b) if the first partition is $\{s_1,s_2\},\{s_3\}$, then I need a second partition making $\{s_1,s_2\}$ into $\{s_1\},\{s_2\}$. So the partition time is 2.

The possibility of situation (a) is 2/3 and situation (b) 1/3. So the $E(3)=1*(2/3)+2*(1/3)=4/3$.

I tried using recursive formula but it seems to be a non-closed form. I also wonder whether or not $E(n)$ can be approximated by some other continuous functions?