Number of partitions of a set with size constraints 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 Coeﬃcients’, 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.
 A: Let $X$ be a finite nonempty set. Let $C_{l_1,...,l_k}^{|X|}$ denote the multinomial coefficient of degree $|X|$, i.e. the number of ways of partitioning  $X$ into $k$ (possibly empty) subsets of sizes $l_1,...,l_k$ - so these subsets are all pairwise disjoint, and $l_1 + \cdots + l_k = |X|$ where $l_i \geq 0$.  
Let $G$ be a group of order $n$, and $S,T,U \subseteq G$ fixed subsets of sizes $m=|S|,p=|T|,q=|U|$ respectively, satisfying $m\geq p\geq q\geq 2$ and $S \cap T = T \cap U = S \cap U = \{1\}$.  Let $\mu(G)$ denote the number of such triples.  Then $\mu(G)$ cannot exceed the number $\sigma(G)$ of unordered triples of nonempty proper subsets of $G$ which have trivial pairwise intersections.  We can estimate $\sigma(G)$ using multinomial coefficient sums in the following way.
If $R = G \backslash (S \cup T \cup U)$ is the "remainder" set, then it is of size $0 \leq r = n + 2 - (m + p + q) \leq n - 3$.  There is a fourfold partition of $G \backslash \{1\}$ by the sets $S \backslash \{1\}$, $T \backslash \{1\}$, $U \backslash \{1\}$, $R$, and this can arise in $C_{m-1,p-1,q-1,r}^{n-1} = \frac{(n-1)!}{(m-1)!(p-1)!(q-1)!r!}$ ways.  So $\sigma(G)$ is a sum $\sigma(G) = \sum C_{m-1,p-1,q-1,r}^{n-1}$ running over all $(m,p,q,r)$ subject to $2 \leq q \leq p \leq m \leq n-1$, $0 \leq r \leq n-3$, $m+p+q+r-2 = n$.  The $\sigma(G)$ is less than the multinomial coefficient sum $\sum C_{l_1,...,l_4}^{n-1}$ over all unordered 4-fold proper partitions of the integer $n-1$, and this sum is given by $\frac{\sum_{i=0}^3 (-1)^i \binom{4}{i}(4-i)^{n-1}}{4!} = \mathcal O(4^{n-1})$.  
Note: by 'proper' I mean that the summands $l_i$ are all positive.  The last sum formula comes from the general formula $\sum C_{l_1,...,l_k}^{n} = \frac{\sum_{i=0}^{k-1} (-1)^i \binom{k}{i}(k-i)^n}{k!}$ for the sum, over all unordered $k$-fold proper partitions of a fixed positive integer $n$, of the multinomial coefficients $C_{l_1,...,l_k}^n$.  I think you can refer here to the following paper: Kao, R. C. & Zetterberg, L. H., ’An Identity for the Sum
of Multinomial Coeﬃcients’, The American Mathematical Monthly,
vol. 64, no. 2, 1957, pp. 96-100.
