1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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