Let $f(n)$ be the number of ways to order $n$ objects by the following relations: $<$ and $=$. For example, for objects $a, b$ we have $f(2)=3$ because $a<b, b<a, a=b$.
For example, $f(3)=13$ because:
What is the recurrence relation that represents the problem of finding $f(n)$?
I'm not really sure how to work out the recursive formula. It seems like for $k$'s recursion call we're choosing $k$ out of $n$ object.
What you want are the ordered Bell numbers. The Wikipedia article lists the following recurrence:
$$ f(n) = \sum_{i=1}^{n}\binom{n}{i}f(n-i) $$
which is easy enough to derive, but perhaps not as nice and uniform as you'd hoped for. There doesn't seem to be anything much nicer available, though.
There are also other formulas available that are not recurrences.