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 setthe very subset containing $s_1,s_2$, say $A$, into two non-empty subsets, $B$ and $C$, such that $A=B\cup C$ and $B\cap C=\emptyset$. The randomness of partition means that, $B$ and $C$ are random.
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: when $n$ is small.
(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 possible situations when performing the first partition:
(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 due to the randomness. 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?