Counting equivalence relations with marked classes

Question

The number of equivalence relations on a set of $n$ elements is the Bell number $B_n$.

If we wish to count the number of equivalence classes on a set of $n$ elements where one of the classes is marked, and the marked class is allowed to be empty, we get $B_{n+1}$.

Now, if two classes are marked (with identical markers), and as before, the markers can be attached to empty classes) we get $(B_{n+2} - B_{n+1} + B_n)/2$ partitions; the idea is to introduce two new elements (markers) to the set with $n$ elements, and then correct for the fact that we are using indistinguishable markers, and that the markers can not occur in the same equivalence class.

For equivalence relations with three marked parts (identical markers, marked classes can be empty) I got $(B_{n+3} - 3B_{n+2} + 5B_{n+1} + 2B_n)/6$ using similar techinques.

Is there a general theory to count the number of equivalence classes on a set of size $n$, with $k$ marked classes, the markings being identical and the marked classes being allowed to be empty? The leading term should be $B_{n+k}/k!$.

Answer 1

If $B_{n,t}$ is the number of partitions of a set of size $n$, with $t$ parts marked (hopefully as desired, though I find the description unclear), then $$ \sum_{n=0}^\infty \sum_{t=0}^\infty \frac{B_{n,t}}{n!} x^n y^t = \frac{\exp((1+y)(e^x-1))}{1-y}. $$ Now you can expand with respect to $y$ to look at a particular number of marks. The value $y=0$ gives the Bell numbers.