Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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 Coefficients’, The American Mathematical Monthly, vol. 64, no. 2, 1957, pp. 96-100.

share|improve this answer
    
What I have given is an estimate, because you asked for an upper bound. Obviously it is not an exact formula. Sandeep –  Sandeep Murthy Aug 24 '12 at 22:06
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.