# The number of good partitions

This was also posted in stackexchange. However, I have no idea how difficult it is. All hints or references are appreciated!

Consider a set $S$ of $n$ red balls and $m$ blue balls. It is well known that the number of partitions of this set is the Bell number $B_{n+m}$.

We say that a partition $P \subset \mathcal{P}(S)$ of $S$ is good if it has the following property: If there are at least two red (blue) balls in $A \in P$, there also is at least one blue (red) ball in $A$. Let $\xi_{n+m} \leq B_{n+m}$ be the number of good partitions of $S$.

Is there a chance for obtaining a closed form for the number $\xi_{n+m}$? Alternatively, is it possible to construct an algorithm to calculate it for large $n$ and $m$?

What happens if we introduce other colors and alter the definition of a good partition: We say that a partition $P \subset \mathcal{P}(S)$ of $S$ is good if it has the following property: If there are at least two balls of the same color in $A \in P$, there also is at least one ball in $A$ with a different color.

EDIT: In a related post, https://math.stackexchange.com/questions/289016/partitions-and-bell-numbers, they find an expression for partitions of an $n$-element set with no singletons. I'm not sure, however, if this problem can be solved as an application of that.

## 1 Answer

There is no simple closed form expression for $B_{m+n}$, so why should we expect one in this situation? However, an explicit generating function can be given as a routine application of the exponential formula. Let $X$ be the set of all pairs $(n,m)$ where we are allowed to have a block with $n$ red balls and $m$ blue balls. Thus $$X=\mathbb{N}\times\mathbb{N}-\{(0,0)\}-\{(n,0)\,:\,n\geq 2\}- \{(0,m)\,:\,m\geq 2\},$$ where $\mathbb{N}=\{0,1,2,\dots\}$. Let \begin{eqnarray*} F(x,y) & = & \sum_{(n,m)\in X}\frac{x^ny^m}{n!\,m!}\\ & = & e^{x+y}-1-(e^x-1-x)-(e^y-1-y)\\ & = & e^{x+y}-e^x-e^y+x+y+1. \end{eqnarray*} If $g(n,m)$ denotes the number of good partitions with $n$ red balls and $m$ blue balls, then by the exponential formula, $$\sum_{m,n\geq 0}g(n,m)\frac{x^ny^m}{n!\,m!} = e^{F(x,y)}.$$ This technique works just as well if we introduce other colors.