Counting problems where unlabeled is easier than labeled I was encouraged to post this question by Jim Propp during a meeting of the Cambridge Combinatorics and Coffee Club. It is a counterpoint to the MathOverflow question "Counting Problems where Labeled is Known but Unlabeled is Not" which asks for examples where it is known how to count labeled objects but not known how to count unlabeled objects. 
I think the general expectation in enumerative combinatorics is that it should be easier to count labeled objects as opposed to unlabeled objects. For instance, we have much nicer formulas for the number of labeled trees, labeled graphs, labeled connected graphs on $n$ vertices than for the corresponding unlabeled objects. (Here labeled means the vertices are labeled.)
Nevertheless I am asking for counterexamples to this general trend. That is, I am looking for examples of counting problems where the unlabeled objects have a nicer formula than the labeled objects. I know of two such examples.


*

*Semiorders. A semiorder, also known as a unit interval order, is a poset that avoids $2+2$ and $3+1$ as induced subposets. The number of semiorders on $n$ unlabeled elements is the $n$th Catalan number $C_n := \frac{1}{n+1}\binom{2n}{n}$. The number of labeled semiorders is sequence A006531 in the OEIS. Labeled semiorders on $n$ elements have an exponential generating function of $C(1-e^{-x})$ where $C(x) = \frac{1-\sqrt{1-4x}}{2x}$ is the ordinary generating function for the Catalan numbers.

*Threshold graphs. A threshold graph is a graph $G=(V,E)$ for which there is some threshold function $\omega\colon V\to\mathbb{R}$ on the vertices such that $\{i,j\}\in E$ iff $\omega(i)+\omega(j) > 0$. The number of threshold graphs on $n$ unlabeled vertices is $2^{n-1}$ (because there is a simple recursive construction of these graphs). The number of labeled threshold graphs is sequence A005840 in the OEIS. Labeled threshold graphs on $n$ vertices have an exponential generating function $\frac{e^x(1-x)}{(2-e^x)}$.
Does anyone know other examples like these? Interestingly, for both semiorders and threshold graphs we have an associated hyperplane arrangement; see Stanley's notes. 
 A: A good example is self-complementary graphs. It's not hard to count unlabeled self-complementary graphs using Burnside's lemma, but there seems to be no reasonable formula for counting labeled self-complementary graphs. 
Unlabeled self-complementary graphs are counted by sequence A000171 in the OEIS. A paper on counting labeled self-complementary graphs is Shinsei Tazawa, A new counting methods, including the issue of counting labelled self-complementary graphs, arXiv:0909.2314 [math.CO]. This paper computes the number of labeled self-complementary graphs on $n$ vertices for $n$ up to 9.
A: A generalization of Per Alexandersson's comment is to take the isomorphism class of any graph (or digraph) $G$.  There is exactly one such unlabelled graph, so it is obviously harder to count the labelled objects.  
For Per Alexandersson's comment, $G$ is a directed path with $n$ vertices, in which case there are $n!$ labelled versions of $G$.  If $G$ is a cycle with $n$ vertices, there are $\frac{(n-1)!}{2}$ labelled versions of $G$.  If $G$ is $K_{n,n}$, there are $\frac{1}{2}\binom{2n}{n}$ labelled versions of $G$. These examples are quite structured, making it fairly easy to count the labelled versions, but for a random graph $G$ on $n$ vertices, it will likely be difficult to count the number of labeled versions of $G$.  
