One of my students made some experiments on partitions of sets. He found some results and I asked him, if he can prove some statements. After two weeks he had no result, so maybe one of you can help.
He computed $f(m):=\left|\left\{(S,T,U) ~ : ~ \begin{array}{l} S,T,U\subseteq G=\{g_1,\ldots,g_m\}\\ |S| \geq |T| \geq |U| \geq 1\\ S\cap T=T\cap U = S\cap U=\emptyset \end{array} \right\}\right|$ up to $m=16$ and he had the idea that $f(m)\leq 4^{m-1}$ or $4^{m-2}$. But he couldn't prove any upper bound.
Here is a table of some computed values (the program constructs and counts all such partitions): $\begin{array}{rrr} m & \mathrm{computed~}f(m)\\\hline 3 & 6\\ 4 & 36\\ 5 & 170\\ 6 & 780\\ 7 & 3437\\ 8 & 14476\\ 9 & 59838\\ 10 & 245280\\ 11 & 995357\\ 12 & 4008576\\ 13 & 16084081\\ 14 & 64360933\\ 15 & 256908836\\ 16 & 1023951196 \end{array}$
It is obvious, that $ \begin{eqnarray*} f(m)&=&\sum_{\substack{s\geq t\geq u\geq 1\\s+t+u\leq m}} \binom{m}{s}\binom{m-s}{t}\binom{m-s-t}{u}\\ &=&\sum_{x=3}^m \sum_{\substack{s\geq t\geq u\geq 1\\s+t+u=x}} \frac{m!}{s!t!u!(m-x)!} = \sum_{x=3}^m\left[ \binom{m}{x}\sum_{\substack{s\geq t\geq u\geq 1\\s+t+u=x}} \frac{x!}{s!t!u!}\right]. \end{eqnarray*} $
The first answer cites to [Kao, R. C. & Zetterberg, L. H., ’An Identity for the Sum of Multinomial Coefficients’, The American Mathematical Monthly, vol. 64, no. 2, 1957, pp. 96-100]. It seems helpful, but it only gives a solution for $ \sum_{\substack{s\geq1,~ t\geq1, ~ u\geq 1\\s+t+u=x}} \frac{x!}{s!t!u!}, $ so it ignores the condition $s\geq t\geq u \geq 1$. Maybe someone can help from this point.