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.