Ytukyg

I have $2n$ elements, $n$ of which are blue and the other $n$ are orange. Other than sharing a colour, they are distinct, i.e. each of those $2n$ objects is different and recognizable from any other.

How many partitions are there such that in each subset there’s at least one blue element and there are at least two elements total?

So, for example, a good partition would be {blue_1, blue_2} or {blue_1, orange_1} or {blue_5, orange_1, orange_3, orange_7} and a bad (i.e. the one I don’t want counted) one {blue_1} (because there’s only one element), or {orange_3, orange_11} (because there’s no blue one).

I tried to approach this first by starting with Bell number and subtracting, but that lead me nowhere. Then I started anew, trying to get a recurrence relation.

Obviously, $X_2 = 1$, because the only partition one can get is {blue_1, orange_1}.

Then, if I already had $X_{2n - 2}$ partitioned, I could:

1. Keep things as-is and add a new pair as another subset—one option for each previous partition.


2. Add {blue_n, orange_n}, as a pair, to any pre-existing subset—the number of subsets for each partition; but I don’t know how many those are.


3. Add {blue_n} to one subset and {orange_n} to another—and again, while I know it’s $binom{x}{2}$ for each partition with $x$ subset, I don’t know how to write that in a useful way.


4. Some other solutions, created by taking blue_n and adding pre-existing oranges to it (because now it can create a valid partition)—but here I am not even sure how much that would be, maybe somewhere around $B_{2n - 2}$?

I have created a small Python script to calculate a few first values. It shows $X_2 = 1, X_4 = 3, X_6 = 28, X_8 = 433, X_5 = 9461$. Unfortunatelly, there’s no such sequence on OEIS.

The recurrence relation you describe won't quite work, for the reasons you describe above -- you don't know the size of each case. Instead you can consider the following cases: One set has exactly one blue element, and each set has at least 2 blue elements. To make it easy, first we'll say that the sets of the partition are distinguishable, then divide by 2 at the end (this way was more intuitive for me, but the direct counting works as well; you just have to be careful in the third step below). Call the sets Set $A$ and Set $B$.

If set $A$ has exactly one blue element, there are $2^n - 1$ ways to choose orange elements for set $A$ (we can choose any nonempty subset). There are $n$ ways to choose the blue element, for a total of $n(2^n-1)$ instances in this case. Note that set $B$ is determined by the contents of set $A$.

Similarly, there are $n(2^n-1)$ ways for set $B$ to have exactly one blue element.

In the other case, each set has at least $2$ blue elements. We need to choose somewhere between $2$ and $n-2$ blue elements to go in set $A$. There are $2^n - 2 - 2n$ such subsets (we can choose any subset, except for the empty set, the entire set, any singleton set, or any set of size $n-1$). Then we can choose any subset of the orange elements in $2^n$ ways, for a total of $2^n(2^n - 2 - 2n)$ ways.

Summing these, we have $2n(2^n - 1) + 2^n(2^n - 2 - 2n)$ such partitions; we need to divide by $2$ to account for ordering the sets $A$ and $B$ to get: $n(2^n-1) + 2^n(2^{n-1} - 1 - n) = 2^{2n-1} - 2^n - n$.