# 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.

-
I gather that first and third lines specifies a incomplete ordered partition (def 2.1), and that the second line is the constraint (not only a size constraint). –  leonbloy Aug 24 '12 at 11:14

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.
Hi @sandeep-murthy, thanks for your hint and the cited paper. I updated the problem description to point what, why I can't use the cited result. Also I see some minor problems: You speak of $G$ as group. You work with $G\setminus 1$. The solution $\mathcal O(4^{n-1})$ is not strong enough: The multiplicative factor could be $4$, so this gives the trivial upper bound $4^m$. Therefore I hope, that an exact solution will be possible. –  Ivo Aug 26 '12 at 0:06