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?